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. One hit costs O(log n); listing all k hits costs O(k log n), never more than n. Fire a query point and watch subtrees get skipped.
O(k log n) 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) for one hit and O(k log n) for all of them.
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(k log n)
Every visited node either reports a hit or guides the pruning. Each hit costs at most one path down the tree, so one hit is O(log n) and k hits are O(k log n), never more than n. The O(log n + k) bound belongs to other structures: a centered interval tree, or a segment tree that stores lists of intervals.
Stabbing query
O(k log n)
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?
Each reported interval can cost one path down the tree, so one hit is O(log n) and k hits are O(k log n), never more than n. O(log n + k) needs a different structure, such as a centered interval tree or a segment tree with lists. Still 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) finding one hit in O(log n) and all k hits in O(k log n), 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?"
The picture: what the query never looks at
The tree is ordered by low endpoint and each node stores the largest high endpoint in its subtree. The stabbing query q = 13 reports the three highlighted intervals, visits one more node that does not contain 13, and never enters the dashed subtree: the root starts at 15, so everything on its right starts later still.
Worked example, step by step
Store six closed intervals, [5,20] [10,30] [12,15] [15,20] [17,19] [30,40], in a balanced tree keyed by low endpoint. At each visited node the query asks three questions in a fixed order: can the left subtree reach q (its max ≥ q), does this interval contain q, and is q ≥ lo so that the right subtree might start early enough. Rows are in visiting order; the parenthesis shows the left child’s max.
Query
Node
Subtree max
Left max ≥ q?
Contains q?
Search right?
q = 18
[15, 20]
max 40
yes (30)
yes, report
yes
q = 18
[10, 30]
max 30
yes (20)
yes, report
yes
q = 18
[5, 20]
max 20
no left child
yes, report
no right child
q = 18
[12, 15]
max 15
no left child
no
no right child
q = 18
[30, 40]
max 40
yes (19)
no
no right child
q = 18
[17, 19]
max 19
no left child
yes, report
no right child
q = 13
[15, 20]
max 40
yes (30)
no
no, skip right
q = 13
[10, 30]
max 30
yes (20)
yes, report
yes
q = 13
[5, 20]
max 20
no left child
yes, report
no right child
q = 13
[12, 15]
max 15
no left child
yes, report
no right child
q = 35
[15, 20]
max 40
no (30)
no
yes
q = 35
[30, 40]
max 40
no (19)
yes, report
no right child
The three queries tell different stories. For 18 four intervals contain the point and six of six nodes are visited, so nothing is pruned: when every node is a hit the work is proportional to the output. For 13 two of the six nodes are skipped, and they are skipped together as one subtree, [30,40] and its child. For 35 the root’s left max is 30, which is below 35, so the entire left side is skipped, and the search goes straight to [30,40]: two nodes, one hit. Pruning does not depend on how many intervals are stored, only on how many could contain the point.
Complexity and trade-offs
Case
Time
Space
Why
Interval tree (BST + subtree max)
O(log n) for one hit, O(k log n) for k hits, never worse than O(n)
O(n)
Measured on a balanced tree of 1,023 intervals: a point with no hit visited 10 nodes, and a point inside 51 intervals visited 58 or 61, close to k plus the depth.
Same tree, built unbalanced
O(n)
O(n)
Inserting 1,000 intervals in sorted order makes a chain; a one-hit query at the far end visited 1,000 nodes, against 9 on the balanced tree.
Linear scan of a list
O(n) per query
O(n)
Always checks every interval. Perfectly fine for dozens of intervals, and the baseline everything else must beat.
Centered interval tree
O(log n + k)
O(n)
Splits at a median point and keeps two sorted lists per node. Its query bound is output-sensitive, but it is a static structure and harder to update.
Segment tree with lists
O(log n + k)
O(n log n)
Stores each interval on several covering nodes, which costs memory but answers stabbing counts and lists quickly.
Building from sorted input costs O(n log n) for the sort and O(n) for the tree. The main trade-off against the centered tree is that the augmented BST is dynamic: inserting or deleting an interval keeps the tree balanced and repairs max along one path, in O(log n). The price is the k log n factor in the worst case, and the dependence on balance, which is the most common way to lose the speed-up.
Common mistakes
Letting max go stale
Each node's max must cover its whole subtree, not just its own interval. A tree that stores only each interval's own high endpoint prunes wrongly: with the intervals [1,50] [2,3] [4,5] [6,7] [8,9], a query at 40 returns nothing instead of [1,50], because the root's left child looked too short to matter. After every insert, delete or rotation, recompute max on the path back up.
Using strict inequalities on closed intervals
With lo < q < hi instead of lo ≤ q ≤ hi, touching endpoints vanish. On this page’s six intervals, a query at 15 should report four intervals; the strict version reports two, and a query at 30 reports none instead of [10,30] and [30,40].
Skipping the right subtree when q equals lo
The right subtree can hold intervals whose low equals the node’s low. Searching it only when q > lo drops them: on [10,12] [10,15] [10,20], a query at 10 returns two intervals instead of three. The test is q ≥ lo.
Checking only the query’s endpoints for overlap
Two intervals overlap when lo ≤ qhi and qlo ≤ hi. Testing whether the stored interval contains qlo or qhi misses an interval inside the query: the stored [4,6] against the query [3,8] does overlap, but neither 3 nor 8 lies in it.
Forgetting to balance
The pruning argument bounds the work by the depth of the tree. Insert sorted data into a plain BST and the depth is n: a one-hit query visited 1,000 nodes on 1,000 intervals, against 9 when balanced. Use a self-balancing tree or build from sorted input by splitting at the median.
Where this shows up
Calendars and scheduling
“Which meetings overlap 2 to 3 pm?” is an interval overlap query, and conflict detection when adding a booking is one query before the insert.
Genomics and annotation
Finding every gene, peak or variant region that overlaps a coordinate range is the standard use, since the data is a large static set of intervals queried many times.
Network and rule matching
Address ranges and port ranges are intervals, so “which rules cover this address?” can be answered by a stabbing query rather than a scan of the rule list.
Geometry and windowing
Finding which horizontal spans cross a vertical line, or which objects lie under a cursor along one axis, reduces to the same stabbing query.
SOLVE IT YOURSELF
Solve it: find every overlapping interval
"Which meetings clash with 2–3pm?" Scanning every booking is O(n) per query. Store the intervals in a BST keyed by start, augment each node with the largest endpoint in its subtree, and whole branches can be skipped without ever looking inside them. Python or TypeScript.
YOUR TASK
Implement IntervalTree with insert(lo, hi) and overlapping(lo, hi), returning every stored interval that overlaps the query. Intervals are closed — touching endpoints count as an overlap.
HINTS — 8 IDEAS
Order the tree by interval start, exactly like a normal BST. That alone cannot answer overlap queries, which is why the augmentation exists.
Each node also stores max: the largest end anywhere in its subtree. Refresh it on the way back out of every insert.
Two closed intervals overlap when a.lo <= b.hiandb.lo <= a.hi. Thinking of it as "not disjoint" is the same test and is easier to get right.
First pruning rule: if a node's max is below the query's start, nothing in that entire subtree reaches the query. Skip it without recursing.
Second pruning rule: if a node's own start is past the query's end, everything in its right subtree starts even later — skip that side too.
Those two checks turn an O(n) scan into O(log n) for one hit and O(k log n) for k reported hits. Without max you would have to visit every node.
A nested interval — a long one that swallows the query — is exactly the case a naive "search by start" misses. The max field is what keeps it reachable.
This version does not rebalance, so an adversarial insert order can degrade it; production implementations augment a red-black tree.