Range Trees

Imagine you have a million GPS coordinates and someone asks: "list every point with latitude between 40.4 and 40.9 and longitude between −74.1 and −73.7." This is an orthogonal range query — find all points inside an axis-aligned box.

The naive approach scans all $n$ points and takes $O(n)$ time regardless of how many points $k$ are actually inside the box. That is fine once, but not when millions of such queries arrive per second.

A range tree is a nested binary search tree that builds an index in $O(n \log^{d-1} n)$ space and answers a $d$-dimensional box query in $O(\log^d n + k)$ time — where $k$ is the number of points reported. In two dimensions that is $O(\log^2 n + k)$; with fractional cascading it drops to $O(\log n + k)$, matching the information-theoretic lower bound on the query.

The structure was described by Jon Louis Bentley in 1979 and refined by Bernard Chazelle (fractional cascading, 1986). Unlike the P vs NP family of open questions, the complexity of range search is solved: the $O(\log n + k)$ query bound is tight.

The canvas below holds a set of 2-D points. Draw a query rectangle by clicking and dragging, then compare two strategies: a linear scan that checks every point, and a range tree that prunes the search.

<p class="hint">{{hint}}</p>
<canvas id="canvas" width="480" height="300"></canvas>
<div class="stats" id="stats">{{draw_prompt}}</div>
<div class="btns">
  <button id="btnRandom" type="button">{{btn_random}}</button>
  <button id="btnClear" type="button" class="ghost">{{btn_clear}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
#canvas { display: block; border: 1px solid #cdd9e3; border-radius: 8px;
          cursor: crosshair; background: #f7f9fb; max-width: 100%; }
.stats { font-size: .9rem; margin: .55rem 0; min-height: 2.8em; line-height: 1.6; }
.stats b { color: #1d3557; }
.stats .hit  { color: #0a7d33; font-weight: 700; }
.stats .miss { color: #c92f3c; font-weight: 700; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Watch the step counter. The linear scan always touches every point; the range tree only visits the $O(\log^2 n)$ nodes needed to identify candidates, then outputs the $k$ points inside. The gap widens as $n$ grows.

How fast can orthogonal range search be, and why?

The naive baseline scans all $n$ points in $O(n)$ per query — acceptable once, catastrophic at scale.

Binary search in 1-D sorts points by $x$ and finds both endpoints in $O(\log n)$, then outputs the $k$ points in between in $O(\log n + k)$. A simple sorted array is optimal in one dimension.

Range trees in 2-D nest a second sorted structure inside each node:

1. Build a balanced BST on the $x$-coordinates (primary tree).
2. At each node $v$, store a secondary sorted array of the $y$-coordinates of all points in $v$'s subtree (fractional cascade / associated structure).
3. To query $[x_1, x_2] \times [y_1, y_2]$: find the $O(\log n)$ canonical nodes whose $x$-subtrees cover $[x_1, x_2]$, then binary-search $[y_1, y_2]$ inside each secondary structure.

Without fractional cascading this takes $O(\log^2 n + k)$: $O(\log n)$ canonical nodes, each requiring an $O(\log n)$ binary search.

With fractional cascading (Chazelle & Guibas, 1986) the secondary searches take $O(1)$ after an $O(\log n)$ initial lookup, dropping the total to $O(\log n + k)$.

Space is $O(n \log n)$ in 2-D and $O(n \log^{d-1} n)$ in $d$ dimensions — each of the $O(n)$ points appears in $O(\log n)$ secondary structures.

Lower bound: any pointer-machine data structure for orthogonal range reporting requires $\Omega(\log n / \log \log n + k)$ query time (Chazelle, 1990). So range trees with fractional cascading are essentially optimal.

This is not an open problem — it is a closed chapter of computational geometry. Compare this to sorting lower bounds, where the same style of adversary argument shows $\Omega(n \log n)$ comparisons are unavoidable.

Orthogonal range search is everywhere data has multiple numeric attributes:

• Geographic information systems (GIS): "find all restaurants within this map viewport" is a 2-D range query executed millions of times per day in mapping APIs. R-trees and kd-trees are engineering cousins of the range tree tailored for disk storage.
• Database indices: multi-column index lookups (WHERE x BETWEEN a AND b AND y BETWEEN c AND d) are orthogonal range queries. Databases use B-tree variants and bitmap indices that exploit the same nested-structure idea.
• Collision detection in games and physics: bounding-box tests in 3-D engines reduce to 3-D range queries; a range tree (or its cousin the AABB tree) prunes the search from $O(n^2)$ pairs to near $O(n \log^2 n + k)$.
• Genomics and bioinformatics: a genome browser asks "which annotated features overlap coordinates $[a, b]$?" This is an interval stabbing query, solvable in $O(\log n + k)$ with an augmented BST — the same nesting idea as a 1-D range tree.
• Time-series and financial data: "find all trades between price $p_1$ and $p_2$ between timestamps $t_1$ and $t_2$" is a 2-D range query on every trading platform.

Understanding range trees also unlocks fractional cascading as a general technique: whenever you have $m$ sorted lists to binary-search simultaneously, cascading can replace $O(m \log n)$ total work with $O(m + \log n)$.

Range trees answer one of the most natural questions in computing — "which points fall in this box?" — in time that barely grows with $n$. The key insight is deceptively simple: nest a secondary sorted structure inside each node of a primary tree, and binary-search them simultaneously.

Unlike many problems on this site, range search is a solved problem: the $O(\log n + k)$ query bound achieved with fractional cascading is provably optimal. Building on this foundation, computational geometry has developed richer structures — persistent trees, segment trees, wavelet trees — each reusing the same nesting idea at a different scale.

The next time a map app returns your local results in milliseconds, or a database executes a multi-column range predicate almost instantly, you are benefiting from this beautifully closed corner of algorithm design — a rare case where theory and practice converge on the same tight answer.