The idea: a search tree of intervals with one extra number

A calendar asks "which meetings clash with 10:00 to 11:00?". A genome browser asks "which genes touch positions 18 to 25?". Both are overlap queries on a set of intervals. An interval tree answers them without scanning every interval.

It is a binary search tree keyed by the low end of each interval [lo, hi]. Each node also stores max: the largest high end anywhere in its subtree. That one extra number (the augmentation) tells the search when a whole subtree ends too early to matter.

The page's starting tree with ten intervals. Root 16–21 with max 30; left 8–9 max 23, right 25–30 max 30; then 5–8 max 10, 15–23 max 23, 17–19 max 20, 26–26 max 26; leaves 0–3, 6–10 and 19–20. Below, the same ten intervals drawn as bars on a 0 to 30 line, one row each, sorted by low end.
The starting tree (CLRS Figure 14.4): sorted by lo left to right, and each max is the latest end in that subtree. The bars are the same intervals on a line.

On the canvas each node shows its interval on top and its max below. Under the tree, a timeline draws every interval as a bar, one row each in key order, and a search draws the query as a blue band. A node and its bar always have the same colour.

When do two intervals overlap?

Closed intervals [a, b] and [c, d] overlap when each one starts before the other ends: a ≤ d and c ≤ b. They miss each other in only two ways: one ends before the other starts, or starts after the other ends.

A query band from 10 to 20. Four green bars overlap it: 5–12, 12–16, 7–25 and 18–26. Two red bars do not: 2–8 ends before 10, and 22–28 starts after 20.
Four ways to overlap, two ways to miss: ends too early (hi < q.lo) or starts too late (lo > q.hi).

Insert keeps every max correct

Insert walks down by lo as in any BST. Every node it passes gets the new interval somewhere below it, so its max becomes max(max, new hi). The new node becomes a leaf with max = its own hi. That is all: one path, O(height) (Demo: insert [10, 27], max goes up: [8, 9] and [15, 23] both go from 23 to 27).

Find one overlap: left or right?

At each node, if the node overlaps the query, stop. Otherwise go to one child:

  • if the left child exists and its max ≥ q.lo, go left;
  • otherwise go right.

Going right is clearly safe: every interval on the left ends before q.lo. Going left looks risky, since an answer might be on the right. It is not: some interval on the left ends at max ≥ q.lo. If it still does not overlap, it must start after q.hi. Every interval on the right starts at least as late, so none of them can overlap either. Either way one path settles it (Demo: find any overlap with [22, 25] finds [15, 23]; Demo: find any overlap with [11, 14], none goes left at the root and correctly reports none).

Find all overlaps: two pruning rules

To report every overlap, visit nodes from the root and skip whole subtrees with two rules:

Rule 1: at node 8–9 for query 18 to 25, the left subtree has max 10, less than 18, so it is skipped, while the right subtree 15–23 with max 23 is visited. Rule 2: at node 26–26, 26 is greater than 25, so the right subtree is skipped and only the left one may be visited.
Skip a subtree whose max < q.lo (it all ends too early), and a right subtree when the node's lo > q.hi (it all starts too late).

For k answers this costs O(k · log n) in a balanced tree, and often much less: Demo: find all overlaps with [18, 25] compares 7 of 10 intervals and finds 5, while Demo: find all overlaps with [27, 29], pruning compares only 2 and skips 8.

Where it is used

UseIntervalsQuery
Calendars, room bookingmeetings [start, end]does a new meeting clash?
Genome browsersgenes, reads [from, to]features in a window
Memory allocators, kernelsmapped address rangeswhich mapping holds this address?
Databases, schedulerslocked key ranges, time slotsconflicting locks or bookings

A segment tree is a different tool: it splits a fixed range of positions into halves and stores a value per segment (sums, minimums). An interval tree stores a changing set of intervals and asks which ones overlap. For choosing non-overlapping intervals, see interval scheduling; for 2-D boxes, the R-tree on KD-trees and R-trees uses the same "skip a box that cannot meet the query" idea.

What the page leaves out

The tree here is a plain BST, so sorted inserts make it tall. Real interval trees are balanced, usually as a red-black tree: a rotation changes two subtrees, so it recomputes max = max(hi, left.max, right.max) at the two nodes it moves, still O(1) per rotation. The page also leaves out delete (max is recomputed up the path), half-open intervals, the centered interval tree (Edelsbrunner's variant with sorted lists per node), and stabbing queries for a single point (a query [p, p]).