Given a pile of intervals and a point q, which intervals containq? Scanning all of them is O(n). An interval tree does better by augmenting a balanced BST: order the intervals by their low endpoint, and at each node store the maximum endpoint anywhere in its subtree. That one extra number lets a “stabbing” query prune whole subtrees — if a subtree’s max endpoint is already below q, nothing in it can reach q, so skip it entirely. Answering takes O(log n + k) for k hits. Fire a query point and watch subtrees get skipped.
O(log n + k) stabbing query · BST by low endpoint + subtree-max augmentation · prune what can’t overlap
interval
A range [lo, hi]. It contains a point q when lo ≤ q ≤ hi.
BST by low
Nodes ordered by their low endpoint, so a right subtree’s lows are all ≥ the node’s.
subtree max
Each node stores the largest hi anywhere in its subtree — the augmentation.
stabbing query
Find every interval containing a point q. The max lets it prune subtrees.
interval-tree.js — the max prunes the search
Ready
Intervals stored in a BST by low endpoint. Each node shows [lo, hi] and its subtree’s max endpoint. To find all intervals containing a point q, we walk the tree, using max to skip subtrees that can’t reach q. Step the query.
–
query q
0
nodes visited
0
found
How it works
The two augmentation facts do all the pruning. First, because the tree is ordered by low endpoint, an entire right subtree has lows greater than the current node’s low — so if q is below the current node’s low, no interval on the right can start early enough to contain q, and the whole right subtree is skipped. Second, each node caches its subtree’s maximum high endpoint — so if that max is below q, no interval in the subtree extends far enough to contain q, and the whole subtree (usually the left one) is skipped. Between these two, a stabbing query only descends into subtrees that could genuinely hold a match, giving O(log n + k).
1
Order by low, augment with max
Build a balanced BST keyed by each interval’s low endpoint. At every node, store the maximum high endpoint found anywhere in its subtree.
2
Prune the left via max
At a node, if its left child exists and that child’s subtree max ≥ q, the left subtree might contain q — search it. If the left max < q, nothing there reaches q; skip it entirely.
3
Test the node, prune the right via low
Check whether the node’s own interval contains q. Then, only if q ≥ the node’s low, search the right subtree — since all right-subtree lows are ≥ this node’s low, a smaller q rules them all out.
✓
Report all hits in O(log n + k)
Every visited node either reports a hit or guides the pruning. The search touches only O(log n) guiding nodes plus the k matches, for O(log n + k) total.
Stabbing query
O(log n + k)
Build
O(n log n)
Space
O(n)
Augment
subtree max
The code
# interval tree: report all intervals containing point qdef stab(node, q, out):
if node isNone: returnif node.left and node.left.max >= q: # left could reach q
stab(node.left, q, out)
if node.lo <= q <= node.hi: # this interval contains q
out.append((node.lo, node.hi))
if q >= node.lo and node.right: # right lows are >= node.lo
stab(node.right, q, out)
# each node also caches: max = max(hi, left.max, right.max)
Quick check
1. What augmentation makes an interval tree fast?
The key augmentation is the subtree maximum endpoint. If that max is below the query point q, no interval in the subtree can reach q, so the whole subtree is pruned.
2. Why can the right subtree be skipped when q < node.lo?
Ordering by low endpoint means all right-subtree lows are ≥ the node’s low. If q is below that low, every right interval starts after q, so none can contain it — skip the whole right subtree.
3. What is the query time of an interval tree?
A stabbing query visits O(log n) guiding nodes plus the k nodes it reports, for O(log n + k) total — far better than scanning all n intervals when k is small.
FAQ
What is an interval tree?
A balanced BST that stores intervals keyed by low endpoint, with each node augmented to hold the maximum high endpoint in its subtree. That lets it answer "stabbing" queries (which intervals contain a point) in O(log n + k), pruning subtrees whose max can’t reach the query.
What is a stabbing query?
Given a point q, which stored intervals contain q (lo ≤ q ≤ hi)? The point "stabs" through the intervals. Interval trees answer these efficiently, and also support the related query of which intervals overlap a given query interval.
How does an interval tree differ from a segment tree?
An interval tree stores intervals and answers "which contain this point / overlap this interval". A geometry segment tree is built over fixed endpoints storing intervals on covering nodes (good for stabbing counts). Note "segment tree" in competitive programming usually means the array-range aggregate structure — different entirely.
Where are interval trees used?
Overlap queries against a set of ranges: genomics (genes overlapping a region), scheduling/calendars (events covering a time), computational geometry and windowing, network packet classification and firewall rules, and database range indexing — anywhere you repeatedly ask "what covers this?"