An interval tree is an augmented balanced search tree that stores intervals and efficiently answers the question "which stored intervals overlap a given point or query interval?" It is the standard data structure for managing a dynamic set of ranges — one that changes as intervals are inserted and deleted — and it appears everywhere from operating-system kernels to game engines and calendar software.
The core problem it solves: given n intervals, find any (or all) that overlap a query, faster than the O(n) scan a plain list would require. An interval tree answers a single overlap query in O(\log n) time.
max FieldThe most common implementation augments a self-balancing binary search tree (typically a Red-Black Tree). Each node x stores:
The max field is the trick that makes search efficient. Because it summarizes the whole subtree, a query can decide which branch might contain an overlap and prune the other entirely — turning a linear scan into a logarithmic descent. The max value is maintained during the same rotations the balanced tree already performs, so it costs nothing asymptotically.
| Operation | Complexity |
|---|---|
| Space | O(n) |
| Insertion / Deletion | O(\log n) |
| Single overlap search | O(\log n) |
| Report all k overlaps | O(k \log n) |
Two intervals [a, b] and [c, d] overlap if and only if a \le d and c \le b. To find some interval overlapping a query i, descend from the root:
max \ge i.low, an overlap (if any) must be on the left — go left.The correctness rests on the max invariant: if the left subtree's maximum endpoint is still below i.low, no interval there can reach i, so it is safe to skip the entire left side.
def interval_search(root, i):
# i is the query interval [low, high]
current = root
while current is not None and not overlaps(current.interval, i):
if current.left is not None and current.left.max >= i.low:
current = current.left
else:
current = current.right
return current # an overlapping interval, or None
To report all overlapping intervals rather than just one, recurse into both children whenever their max permits, collecting every match — O(k \log n) for k results.
low like an ordinary BST, rebalance, and update max on the path back to the root (each node's max is the larger of its own high and its children's max).max along the affected path during rebalancing rotations.low and building a balanced tree bottom-up gives an O(n \log n) construction — though for static data a segment tree or a simple sorted array may be simpler.Both handle intervals, but they target different query shapes. Choosing the wrong one is a common mistake.
| Feature | Augmented Interval Tree | Segment Tree |
|---|---|---|
| Best for | Overlap queries over a dynamic set of intervals | Point-in-interval and range aggregate queries (min / max / sum) |
| Space | O(n) — highly memory efficient | O(n \log n), or O(n) with coordinate compression |
| Dynamic updates | Native via BST rotations | Awkward; often needs rebuilding or lazy propagation |
| Aggregates over a range | Not its strength | Built for it |
A rough rule: if intervals are added and removed frequently and you ask "what overlaps this?", reach for an interval tree. If the set is mostly static and you want aggregate statistics over ranges, a segment tree (or Fenwick/BIT) often fits better. For multidimensional ranges (rectangles in 2-D+), neither suffices — that is the domain of R-trees and k-d trees.
max. A missed update on insertion, deletion, or rotation silently breaks pruning and produces wrong answers — not crashes — so test overlap correctness explicitly.What is an interval tree used for? Efficiently finding which stored intervals overlap a given point or range, in a set that changes over time — used in memory management, collision detection, scheduling, and genomics.
What is the time complexity of an interval tree? O(\log n) for insertion, deletion, and a single overlap query; O(k \log n) to report all k overlapping intervals; O(n) space.
Interval tree vs. segment tree — which should I use? Use an interval tree for overlap queries over a dynamic interval set; use a segment tree for range-aggregate (min/max/sum) and point-in-interval queries on mostly static data.
How does the max field make search fast?
It records the largest endpoint in each subtree, letting a query prune an entire branch when that branch cannot reach the query — reducing a linear scan to a logarithmic descent.