Interval Trees

Imagine you run a conference center. You have a calendar full of bookings — each one claiming a stretch of time. A new client calls and asks whether a particular hour is free. How do you find out?

The naive answer is to scan every booking. With ten reservations that is fine. With ten million — in a hospital bed scheduler, a stock exchange, or a cloud computing cluster — scanning is unacceptably slow.

The interval tree is the data structure built for exactly this question. It stores a set of intervals (pairs of start and end times, or any two numbers $[a, b]$) and answers stabbing queries: "which intervals contain the point $x$?" in time $O(\log n + k)$, where $k$ is the number of intervals actually hit. You pay only for what you find, plus a small logarithmic overhead — no matter how many millions of intervals you store.

The same idea also handles overlap queries: "which stored intervals overlap the range $[x, y]$?" A query interval $[x, y]$ stabs anything whose left end is $\le y$ and whose right end is $\ge x$.

The result is a beautifully simple idea hiding a careful invariant — and it appears quietly in everything from database engines to graphics renderers.

The demo below shows a set of reservations (colored bars) on a time line. Drag the vertical query line to any position and the interval tree instantly reports every reservation that covers that moment — highlighted in orange.

<div class="hint">
  <b>{{hint_drag}}</b> {{hint_drag_rest}}
  {{hint_tree}}
</div>
<div id="vis-wrap">
  <canvas id="vis" width="560" height="200"></canvas>
</div>
<div class="controls">
  <button id="addBtn" type="button">{{btn_add}}</button>
  <button id="resetBtn" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div id="info" class="info"></div>
<div id="log" class="log"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: 14px 4px; }
.hint { font-size: .85rem; color: #555; margin: 0 0 .6rem; line-height: 1.4; }
#vis-wrap { overflow-x: auto; }
canvas { display: block; border: 1px solid #cdd9e3; border-radius: 8px;
         background: #f7f9fb; cursor: ew-resize; max-width: 100%; }
.controls { display: flex; gap: .5rem; margin: .6rem 0; flex-wrap: wrap; }
button { font: 600 13px system-ui; padding: .4rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.info { font-size: .9rem; font-weight: 600; min-height: 1.4em; margin-bottom: .3rem; }
.info.hit { color: #c45200; }
.info.miss { color: #555; }
.log { font-size: .78rem; font-family: ui-monospace, monospace; color: #447; line-height: 1.5;
       background: #eef2f7; border-radius: 6px; padding: .4rem .6rem; min-height: 2.4em;
       white-space: pre-wrap; word-break: break-all; }

// Code not found

Notice the pattern: the tree descends only into branches whose max endpoint is at least as large as the query point. Any subtree whose stored maximum falls below the query is pruned entirely — that is the key invariant that makes the algorithm fast.

The bottom panel shows the O(log n + k) tree traversal path. Increase the number of reservations and watch how the path length grows only logarithmically, even as the reservation count doubles.

How hard is the stabbing problem, and how close does the interval tree come to optimal?

• Lower bound. Any comparison-based data structure must use $\Omega(\log n)$ time per query in the worst case, because locating the query point among $n$ stored endpoints is equivalent to search. Reporting $k$ results obviously costs $\Omega(k)$. So $O(\log n + k)$ is provably optimal for comparison-based methods.

• The construction. Build a balanced BST (e.g. a red-black tree) keyed by the left endpoint of each interval. At each node, store also the maximum right endpoint in the entire subtree rooted there. Building the tree costs $O(n \log n)$; updating a single interval costs $O(\log n)$.

• The query. To find all intervals containing $x$:

  1. If the node's key $\le x$ and the node's right endpoint $\ge x$ — report this interval.
  2. If the left child exists and its stored max $\ge x$ — recurse left.
  3. If the right child exists and its stored max $\ge x$ — recurse right (but only if $x \ge$ this node's key). Skipping a subtree whose max is below $x$ is correct: no interval in that subtree can contain $x$.

• Space. $O(n)$ — each interval is stored exactly once.

• Status (proven). The $O(\log n + k)$ bound was established by Edelsbrunner (1980) and is a classical result in computational geometry. It is not an open problem — it is a solved, tight bound. The structure generalises to higher dimensions as segment trees and range trees, though those carry poly-logarithmic overhead.

For an even faster alternative in static settings, a sorted array + binary search with a separate sorted-by-right-endpoint list can answer stabbing queries in $O(\log n + k)$ without pointers — but it does not support dynamic insertions. The interval tree is the right choice when intervals arrive and leave at runtime.

Compare with the brute-force scan: $O(n)$ per query. For $n = 10^6$ and $10^6$ queries the scan costs $10^{12}$ operations; the tree costs roughly $20 \cdot 10^6$. That is the practical difference between "done in seconds" and "done never."

See also: P vs NP for why some problems cannot be solved this efficiently, and dynamic shortest paths for another data structure that maintains a result under insertions and deletions.

Stabbing queries appear in an enormous range of computing contexts:

• Calendar and resource scheduling: booking systems, hospital bed managers, and conference room finders must detect every conflict the moment a new reservation arrives. An interval tree over existing bookings makes conflict detection instant.

• Database query execution: when a SQL BETWEEN predicate or a temporal join is evaluated, the query engine uses an interval index (often a B+-tree variant on endpoints) to skip rows that cannot match — exactly the max-endpoint pruning of an interval tree.

• Genomics: a genome is annotated with millions of features — genes, exons, regulatory regions — each spanning a range of base pairs. Given a sequencing read that maps to position $x$, which features overlap it? Bioinformatics tools like bedtools use interval trees to answer this in milliseconds per read.

• Ray tracing and collision detection: in 3-D graphics each object occupies an axis-aligned bounding box along each axis. A ray cast along the $x$-axis stabs a set of $x$-intervals. Interval trees (and their 3-D cousin, the BVH — bounding volume hierarchy) are why modern GPU ray tracers test millions of triangles per pixel in real time.

• Network routing: IP address ranges in routing tables are intervals on the 32-bit or 128-bit integer line. A longest-prefix match is a stabbing query; hardware routers implement it with specialised interval structures.

• Operating-system memory management: the kernel tracks free and allocated memory regions as intervals. When a process requests memory, the allocator stabs the free-interval tree to find a fitting gap.

The pattern is always the same: a large static or slowly-changing collection of intervals, and a stream of point or range queries that must be answered quickly. Wherever that pattern appears, an interval tree (or one of its cousins) is the natural tool.

The interval tree is a masterpiece of augmentation. Take an ordinary balanced BST, add one extra number at each node — the maximum right endpoint in that subtree — and you gain the power to prune entire branches at query time. The result is a provably optimal $O(\log n + k)$ answer to the stabbing question, with $O(n)$ space and $O(\log n)$ updates.

Every time a calendar app highlights a booking conflict, every time a database skips a range of rows without reading them, every time a game engine skips distant objects in a collision test — an interval tree (or its direct descendant) is doing the work invisibly.

The lesson generalises: many data structures achieve their speed not by doing less work, but by keeping one carefully chosen invariant that tells them which work to skip entirely. The interval tree is one of the clearest examples of that idea.