collections/interval_tree_utils library

Interval tree for overlap (stabbing) queries — roadmap #494.

Answers "which intervals contain this point?" and "which intervals overlap this range?" in O(log n + k) (k = matches) instead of the O(n) linear scan a plain list needs. Distinct from IntervalSchedulingUtils (which picks a maximum non-overlapping subset) and weightedIntervals (a DP optimizer): this is the lookup index for spatial/temporal overlap — calendar conflicts, IP-range matching, genomic ranges, gap detection.

Built once from a fixed set of intervals (the tree is balanced by median split and not mutated afterward). Bounds are num and inclusive on both ends, so [10, 20] contains both 10 and 20.

Classes

IntervalEntry<T>

One inclusive interval [low, high] carrying a value.

IntervalTree<T>

An immutable, balanced interval tree over a fixed set of IntervalEntrys.