disambiguation:
A segment tree is a DS that let’s you do things like query for range sums and range maxes in an array (dynamically). This is not at all related to what I talk about today.
An interval tree is a DS that stores some intervals, and on a query point returns the set of intervals containing that point.
Interval tree:
def build_interval_tree(intervals):
middlept = median
left_intervals = [interval I if I is completely to the left of middlept]
right_intervals = [ditto but right]
center_intervals = [intervals that touch the middlept]
store build_interval_tree(left_intervals)
store build_interval_tree(right_intervals)
store sorted list of center_intervals (keyed by left endpoint and by right endpoint).
def handle_query(interval_tree, point):
wlog let point be to the left of center
recursively handle_query(left_interval_tree, point)
list all the center_intervals with start coord before point.maybe it’s more complicated to make this dynamic?