Vibe Engines
YouTube

Vibe Engines is free, interactive AI engineering & system design — runs in your browser. Pick a learning path

Algorithms · Data Structures

What Contains This?

Watch the explainer

Given a pile of intervals and a point q, which intervals contain q? 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 q def stab(node, q, out): if node is None: return if 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?

2. Why can the right subtree be skipped when q < node.lo?

3. What is the query time of an interval tree?

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

[15, 20]max 40[10, 30]max 30[5, 20]max 20[12, 15]max 15[30, 40]max 40[17, 19]max 19 q = 13: right subtree skipped, since 13 < 15 (root low)
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.

QueryNodeSubtree maxLeft max ≥ q?Contains q?Search right?
q = 18[15, 20]max 40yes (30)yes, reportyes
q = 18[10, 30]max 30yes (20)yes, reportyes
q = 18[5, 20]max 20no left childyes, reportno right child
q = 18[12, 15]max 15no left childnono right child
q = 18[30, 40]max 40yes (19)nono right child
q = 18[17, 19]max 19no left childyes, reportno right child
q = 13[15, 20]max 40yes (30)nono, skip right
q = 13[10, 30]max 30yes (20)yes, reportyes
q = 13[5, 20]max 20no left childyes, reportno right child
q = 13[12, 15]max 15no left childyes, reportno right child
q = 35[15, 20]max 40no (30)noyes
q = 35[30, 40]max 40no (19)yes, reportno 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

CaseTimeSpaceWhy
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 unbalancedO(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 listO(n) per queryO(n)Always checks every interval. Perfectly fine for dozens of intervals, and the baseline everything else must beat.
Centered interval treeO(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 listsO(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
  1. Order the tree by interval start, exactly like a normal BST. That alone cannot answer overlap queries, which is why the augmentation exists.
  2. Each node also stores max: the largest end anywhere in its subtree. Refresh it on the way back out of every insert.
  3. Two closed intervals overlap when a.lo <= b.hi and b.lo <= a.hi. Thinking of it as "not disjoint" is the same test and is easier to get right.
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. This version does not rebalance, so an adversarial insert order can degrade it; production implementations augment a red-black tree.
CPython · WebAssembly

Keep going

▶  Watch it explained

Interval Tree: Time and Space Complexity, From First Principles

Finished this one? 0 / 99 Algorithms done
NextMo's Algorithm: Reorder to Win Next on the “Answering a range in log time” ladder · rung 7 of 7

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

More Algorithms