On this page

Spatial Trees: Interval Trees, k-d Trees, Quadtrees & R-trees

A binary search tree answers questions about a line: is 42 present, what is the smallest key at least 42, how many keys lie in [10, 50]. The moment your keys stop being single numbers — a meeting that occupies 09:00–10:30, a restaurant at a latitude and a longitude, a building footprint that is a rectangle, a particle in three-dimensional space — the BST's one comparison per node no longer splits the data in a way that matches the question. "Which meetings overlap 10:00–11:00?" is not a key lookup. "Which restaurant is closest to me?" is not a range of one coordinate.

Spatial trees restore the BST's trick in these settings: every node carries a cheap summary of everything below it (a maximum endpoint, a splitting plane, a bounding box), and a query compares itself against that summary to throw away whole subtrees unseen. This lesson builds the four you will meet most often — interval trees, k-d trees, quadtrees/octrees and R-trees — proves the pruning rules, measures where they stop working, and connects them to PostGIS, SQLite, Lucene, game engines and map tile servers.

It leans on two earlier lessons: the augmented binary search tree (an interval tree is one) and the segment tree (which beats an interval tree on some interval problems; we will say exactly which).

Why this exists

In 1974 Raphael Finkel and Jon Bentley published the quadtree to retrieve records by two keys at once, and in 1975 Bentley published the k-d tree ("multidimensional binary search tree") in Communications of the ACM. Both answered a database question: separate indexes on age and salary cannot efficiently answer "age between 30 and 40 and salary between 50k and 70k", because each returns a huge candidate set whose intersection is small. A structure that partitions on both keys at once can.

Around 1980 computational geometers (Edelsbrunner, McCreight) designed interval trees to report which segments a query point or window touches, a core step in VLSI design checking and hidden-surface removal. In 1984 Antonin Guttman published the R-tree: a B-tree whose keys are rectangles. Balanced, page-oriented and dynamic like a B-tree, it won the database world and is still the core of PostGIS, SQLite's R*Tree module and MySQL's InnoDB spatial indexes.

Physics and graphics took the space-partitioning side. In 1986 Josh Barnes and Piet Hut used an octree to approximate the gravity of distant star clusters, turning an N-body simulation into . Game engines use quadtrees, octrees and bounding-volume hierarchies to avoid testing every pair of objects for collision; web maps cut the world into a quadtree of tiles. Same idea every time: summarise a region cheaply, and refuse to look inside regions the query cannot touch.

The system-design view — geohash, S2, H3 and PostGIS from an architect's point of view — is in Spatial Indexing. This page is the algorithmic layer underneath.

Pattern triggers

If the problem says or has…Think of…
"intervals", "bookings", "reservations", and a query "does anything overlap [a, b]?" with inserts mixed ininterval tree (augmented BST keyed on start, storing max end)
"report all intervals containing point x" (stabbing), static setsegment tree on intervals or centered interval tree
"how many intervals cover x", "maximum overlap", "covered length" with updatessegment tree with lazy add over compressed coordinates
"nearest point", "closest restaurant", "k nearest neighbours", low dimension (2–10)k-d tree
"points inside a rectangle", "orthogonal range query" on 2-D pointsk-d tree (or range tree for guaranteed bounds)
"embedding", "vectors of dimension 128/768", "similar images/text"not a k-d tree — approximate nearest neighbour (HNSW, IVF)
"image", "grid", "compress uniform regions", "sparse 2-D occupancy"region quadtree
"collision detection", "which objects might touch", "broad phase"quadtree/octree, uniform grid, or AABB tree (BVH)
"N-body", "gravity", "far-field approximation"Barnes–Hut octree
"polygons", "rectangles", "bounding boxes", "on disk", "database index"R-tree (R*-tree, STR bulk load)
"geohash", "nearby within radius", "key-value store", "prefix"space-filling curve (geohash, S2) over an ordinary 1-D index
"2-D range count with updates", grid of cells2-D Fenwick tree or 2-D prefix sums (not a spatial tree at all)

Intuition & first principles

One idea: bound, then prune

Each node stores a bound : a cheap description of a region guaranteed to contain everything in its subtree. If we can test "could anything inside satisfy query ?" in , then every no skips a whole subtree. The bound must be conservative: false positives (maybe, but nothing matches) cost time; false negatives would cost correctness and are impossible by design. Everything else is engineering to make false positives rare.

StructureWhat a node splits onBound stored per nodeQuery test that prunes
Interval tree (augmented BST)interval start (BST key)max end in subtreesubtree.max < query.lo → nothing here can reach the query
k-d treeone coordinate at the median, cycling axesthe splitting plane (implicitly a box)distance from query to the plane ≥ best distance so far
Point/PR quadtreeboth coordinates at a point or the cell centrethe cell squarecell does not intersect query region
R-treegroups of nearby objectsminimum bounding rectangle (MBR)MBR does not intersect query region

Four ways to partition

The structures differ in who decides where the boundaries go.

  • Key-driven (interval tree): BST order on the start; the end is folded into a subtree summary. Works because intervals live on a line.
  • Data-driven space partition (k-d tree): hyperplanes placed at the data's median. Disjoint regions, balanced counts.
  • Space-driven partition (quadtree/octree): split at the cell centre regardless of data. Grid-aligned cells are easy to name (map tiles), but skewed data makes deep, thin branches.
  • Object-driven grouping (R-tree): group objects into pages and store each page's bounding rectangle. Rectangles may overlap — the price of never cutting an object, and why R-trees handle polygons.

Most design questions ("why does PostGIS use an R-tree?", "why do k-d trees fail on embeddings?") come down to which partition style fits.

Mechanics

Interval trees

Problem. Maintain a dynamic set of closed intervals . Support insert, delete, "find any interval overlapping " and "report all intervals overlapping ".

Two closed intervals overlap exactly when each starts no later than the other ends:

(The Intervals lesson proves this and discusses half-open variants.)

Structure (CLRS §14.3). Take any balanced BST — red-black, AVL, treap — keyed on (ties broken by ). Augment every node with

the largest right endpoint anywhere in 's subtree. This is a classic augmentation: it depends only on the node and its two children, so it can be recomputed in after any local change. A rotation changes the children of exactly two nodes; recompute their max bottom-up and the invariant holds. Insert and delete therefore stay on a balanced tree. (Balanced BSTs covers the rotations.)

Here is the tree built from ten intervals (the example set from CLRS Figure 14.4), as a perfectly balanced BST on start:

flowchart TD
    A["[15,23] max 30"] --> B["[5,8] max 10"]
    A --> C["[19,20] max 30"]
    B --> D["[0,3] max 3"]
    B --> E["[6,10] max 10"]
    E --> F["[8,9] max 9"]
    C --> G["[16,21] max 21"]
    C --> H["[25,30] max 30"]
    G --> I["[17,19] max 19"]
    H --> J["[26,26] max 26"]

Left children have smaller starts; right children have larger starts. [6,10] has [8,9] as its right child, and [16,21] has [17,19] as its right child.

Finding one overlap (CLRS INTERVAL-SEARCH). Start at the root. While the current node does not overlap the query:

  • if the left child exists and left.max >= a, go left;
  • otherwise go right.

Stop when you find an overlap or fall off the tree. One root-to-leaf path: .

The rule looks too greedy. Going left when the left subtree might hold an overlap seems to risk missing one on the right. The Correctness section proves it cannot: if the left subtree has no overlap, the right subtree has none either.

Reporting all overlaps. Recurse, pruning on two facts:

  1. If v.max < a, no interval in 's subtree ends late enough to reach the query. Skip the subtree.
  2. If v.lo > b, then and every node in its right subtree start after the query ends. Skip and its right subtree (the left subtree may still contain overlaps).
report(v, a, b):
    if v is nil or v.max < a: return            # rule 1
    report(v.left, a, b)
    if v.lo <= b and a <= v.hi: emit v
    if v.lo <= b: report(v.right, a, b)          # rule 2

Because it is an in-order traversal, the output comes out sorted by start.

Trace: report all overlaps with [22, 25] on the tree above (computed by script):

StepNodenode.maxRule-1 test (max < 22?)Overlaps [22,25]?Action
1[15,23]30noyes (15 ≤ 25, 22 ≤ 23)recurse left; report; 15 ≤ 25 so recurse right
2[5,8]10yes—prune whole subtree ([5,8], [0,3], [6,10], [8,9])
3[19,20]30nono (20 < 22)recurse left; 19 ≤ 25 so recurse right
4[16,21]21yes—prune subtree ([16,21], [17,19])
5[25,30]30noyes (25 ≤ 25, 22 ≤ 30)no left child; report; 25 ≤ 25 so recurse right
6[26,26]26nono (26 > 25)no children; rule 2 would skip the right side anyway

Output: [15,23], [25,30]. Six nodes touched, four never touched ([0,3], [6,10], [8,9], [17,19]).

Trace: find one overlap with [11, 14] (an empty answer, which is where the single-path rule is interesting):

StepNodeleft.maxDecision
1[15,23] (no overlap: 15 > 14)1010 < 11 → go right
2[19,20] (no overlap)2121 ≥ 11 → go left
3[16,21] (no overlap)nonego right
4[17,19] (no overlap)nonego right → nil, answer: none

At step 2 the search committed to the left subtree and never came back to [25,30] and [26,26]. That is safe: [16,21] starts at 16, so everything in the right subtree starts at 16 or later — after the query's end, 14.

Output-sensitive cost. The single-overlap search is . Reporting all overlaps on an augmented BST costs : every touched node lies on the search boundary for or has a reported interval below it (CLRS Exercise 14.3-4).

The interval tree. That bound belongs to a different structure with the same name, the centered interval tree (Edelsbrunner 1980; de Berg et al., chapter 10). For a static set, pick , the median of all endpoints; intervals entirely left of it go left, entirely right go right, and intervals containing stay at the node, stored twice: sorted by ascending and by descending. A stabbing query at knows every stored interval reaches past , so it reports the prefix of the by- list with and stops at the first failure; symmetric for . One root-to-leaf path: time, space. Window queries need secondary structures and cost (de Berg et al., §10.1–10.2).

In interviews, "interval tree" almost always means the augmented BST; in a geometry course it means the centered tree.

Segment trees on intervals vs interval trees

A segment tree can store intervals too, in a different way. Compress all endpoints into sorted elementary slots, build a segment tree over the slots, and insert each interval into the canonical nodes whose ranges exactly tile it (the same nodes a range update would touch). Each node keeps a list (or just a count) of the intervals assigned to it.

  • A stabbing query at walks the path to 's slot and reports every list on it: , because every interval containing has exactly one canonical node on that path. Space .
  • With cover counts per node, the same tree maintains the total length covered by a union of intervals under add and remove — the sweep-line structure behind area-of-union-of-rectangles problems.
NeedBetter toolWhy
Dynamic inserts/deletes, "does anything overlap [a,b]?"Augmented BST interval tree per operation, no coordinate compression, no need to know endpoints in advance
Static set, stabbing queries, output-sensitiveCentered interval tree or segment tree with lists; the centered tree uses space
Counting coverage, max overlap depth, covered lengthSegment tree with lazy add over compressed coordinatesaggregates without listing intervals; supports range add
Endpoints are small integersSegment tree directly on the coordinate range, or a difference array if there are no interleaved queriesno compression needed
"My Calendar"-style bookingsOrdered map (TreeMap, std::map) of disjoint bookingsthe stored intervals never overlap each other, so neighbours suffice

The last row matters: if the stored intervals are pairwise disjoint, checking the predecessor and successor by start is enough, and any ordered map does that in .

k-d trees

Problem. Store points in dimensions. Answer nearest-neighbour ("closest point to "), -nearest, and orthogonal range ("all points in this box") queries.

Construction by median splits. At depth , split on axis . Choose the point with the median coordinate on that axis as the node; points with smaller coordinates go left, larger go right (ties may go either way, as long as left split right holds). Recurse.

flowchart TD
    R["(7,2) split on x"] -->|"x < 7"| A["(5,4) split on y"]
    R -->|"x >= 7"| B["(9,6) split on y"]
    A -->|"y < 4"| C["(2,3) split on x"]
    A -->|"y >= 4"| D["(4,7) split on x"]
    B -->|"y < 6"| E["(8,1) split on x"]

These are the six points . The root's line halves the plane, halves the left half, and so on; each node implicitly owns an axis-aligned box.

Median splits give height . Build is with linear-time medians (std::nth_element; see Quickselect & Order Statistics), if you sort per level as the Python code below does.

Nearest-neighbour search. Keep the best point found so far and its squared distance .

  1. At node with split axis and split value , update with itself.
  2. Let . The near child is the side falls on (left if ), the far child the other side.
  3. Search the near child first.
  4. Then search the far child only if — that is, only if the ball of radius around crosses the splitting plane.

Searching the near side first matters. It usually finds a close point quickly, which shrinks , which makes step 4 prune more.

flowchart TD
    S["visit node v"] --> U["update best with v.point"]
    U --> N["diff = q[axis] - v.point[axis]"]
    N --> NEAR["recurse into near child"]
    NEAR --> T{"diff squared < best?"}
    T -->|"yes: ball crosses the plane"| FAR["recurse into far child"]
    T -->|"no"| P["prune far subtree"]
    FAR --> R["return"]
    P --> R

Trace: nearest neighbour of on the tree above (computed by script; distances are squared):

StepNodeAxisbest after (point, )Action
1(7,2)x18(7,2), 184 − 7 = −3near = left
2(5,4)y2(5,4), 25 − 4 = 1near = right
3(4,7)x4(5,4), 24 − 4 = 0near = right (empty)
4back at (4,7)x—(5,4), 2far side is empty
5back at (5,4)y—(5,4), 2visit far (left)
6(2,3)x8(5,4), 24 − 2 = 2no children
7back at (7,2)x—(5,4), 2prune right subtree

Answer: at squared distance 2. Four of six nodes visited. Step 5 shows a far side that had to be checked (the plane is 1 unit away, closer than ) and did not help. Step 7 shows the payoff: the plane is 3 units away, farther than , so the whole right half of the plane is discarded.

Range search. For "all points in box ": report the node's point if it is in ; recurse left if 's lower bound on the split axis is , right if its upper bound is . Worst case in 2-D for reported points, in dimensions (Lee and Wong, 1977; de Berg et al., §5.2). The counts cells a vertical line can cross: every two levels it enters at most two of four grandchildren, so .

Expected vs worst case for nearest neighbour. Friedman, Bentley and Finkel (1977) showed that for well-behaved distributions in fixed low dimension a query visits nodes in expectation. Adversarial data (all points on a circle, query at its centre) forces nearly every node, so the worst case is . The expected bound also hides a constant exponential in — the next topic.

The curse of dimensionality

The pruning test asks whether the query ball crosses a splitting plane. In two dimensions most planes are far away compared to the nearest neighbour. In high dimensions this stops being true, for two reasons:

  • Distances concentrate. For random points, the gap between the nearest and the farthest neighbour shrinks relative to the distances themselves as grows. The nearest neighbour is barely nearer than a typical point, so the query ball is large.
  • Each split uses one axis. A tree of height splits each axis only about times. With points () and , each axis is cut about once: every cell spans roughly half the range on almost every axis, and a ball that is not tiny crosses almost every plane.

A common rule of thumb (it appears, for example, in the Wikipedia article on k-d trees; the scikit-learn documentation gives a similar warning for dimensions above roughly 20) is that a k-d tree is efficient only when . Here is what that looks like, measured by a script on uniform random points in the unit cube, averaged over 20–40 random queries (exact nearest neighbour, node visits counted):

Dimension Nodes visited, Fraction of treeNodes visited,
2220.1%23
4650.3%—
89784.9%1,442 (0.7%)
12about 13,30067%—
1619,52897.6%184,807 (92%)
20about 19,94099.7%—

At with twenty thousand points the tree is a linear scan with pointer-chasing overhead. Ten times more data helps a little, as the rule predicts. Hence the usual statement that k-d trees degrade somewhere between 10 and 20 dimensions: for realistic (up to about ), fails around there. Weber, Schek and Blott (1998) showed the same for the whole family of tree-based similarity indexes.

For text and image embeddings (128 to 1,536 dimensions), production systems give up exactness and use approximate nearest neighbour (ANN) indexes: graph-based HNSW (Malkov and Yashunin, arXiv:1603.09320), inverted-file and product quantisation (as in FAISS), locality-sensitive hashing. Remember why a k-d tree is the wrong answer here.

Quadtrees and octrees

A quadtree splits a square cell into four equal quadrants (NW, NE, SW, SE); an octree splits a cube into eight. The split positions come from the cell geometry, not from the data. There are three variants worth distinguishing.

  • Point quadtree (Finkel and Bentley, 1974): each node stores one data point and splits its cell at that point into four unequal quadrants — a 2-D generalisation of a BST. The shape depends on insertion order.
  • PR (point-region) quadtree: points live in leaves; a leaf holding more than a capacity (often 1 or a small bucket like 8) splits at its centre into four equal children. The shape depends only on the set of points, not their order. The depth is not bounded by : two points very close together force many splits. If the root square has side and the closest pair is at distance , the depth is at most (de Berg et al., Lemma 14.1).
  • Region quadtree: represents a 2-D image or occupancy grid. A cell whose pixels are all the same colour is a leaf; otherwise it splits. A grid with large uniform areas compresses to far fewer leaves than pixels.
flowchart TD
    ROOT["root cell 0..8 x 0..8<br/>mixed"] --> NW["NW: all white<br/>leaf"]
    ROOT --> NE["NE: mixed"]
    ROOT --> SW["SW: all black<br/>leaf"]
    ROOT --> SE["SE: all white<br/>leaf"]
    NE --> NE1["NW: black leaf"]
    NE --> NE2["NE: white leaf"]
    NE --> NE3["SW: white leaf"]
    NE --> NE4["SE: black leaf"]

That tree describes a 64-pixel image with seven leaves. Only the mixed regions pay for detail.

Collision detection (broad phase). Checking every pair of moving objects is . Insert each object's bounding box into the quadtree (octree in 3-D) cells it overlaps; only objects sharing a cell go on to the exact test. Objects straddling a split line are stored at the smallest cell that contains them, or a loose quadtree enlarges cells so each object fits in one. Many physics engines use a dynamic AABB tree instead — a bounding-volume hierarchy, the R-tree's in-memory cousin (Box2D's b2DynamicTree).

Image compression. A region quadtree stores one value per uniform block, which pays off on images with large flat areas (maps, scans, masks). Lossy variants merge blocks whose variance is below a threshold; video codecs such as HEVC partition each coding tree unit with a quadtree of coding blocks for the same reason.

Barnes–Hut N-body simulation. Each octree cell stores the total mass and centre of mass of its bodies. For the force on body , walk from the root: if a cell of side at distance has (typically ), treat it as one point mass; otherwise open it. Distant clusters collapse to one interaction each, giving per step for reasonably distributed bodies. is the exact quadratic algorithm.

Quadtrees also give space a name: a cell's root path, two bits per level, is an address and a position on a Z-order curve. Bing Maps calls it a quadkey, and the web-map tile scheme (z/x/y, tiles at zoom ) is a quadtree of tiles. That link returns in space-filling curves.

R-trees

An R-tree (Guttman, 1984) is a height-balanced tree with fan-out between and (), like a B-tree. Leaves hold (MBR, object id), the minimum bounding rectangle being the smallest axis-aligned box around the object; internal entries hold (MBR, child) covering the whole child. Sibling MBRs may overlap, and each object is stored once.

flowchart TD
    ROOT["root: R1, R2"] --> R1["R1 MBR 0..5 x 0..4"]
    ROOT --> R2["R2 MBR 4..10 x 0..3"]
    R1 --> L1["leaf: a, b, c"]
    R1 --> L2["leaf: d, e"]
    R2 --> L3["leaf: f, g, h"]
    R2 --> L4["leaf: i, j"]

Note that R1 and R2 overlap in the strip , . A query window there must descend into both.

Search. Descend into every child whose MBR intersects the query window; at leaves, test entry MBRs, then exact geometry outside the index — the filter-and-refine pattern. Nearest-neighbour search is best-first with a priority queue keyed by minimum distance to each MBR (Hjaltason and Samet, 1999).

Insertion. Insert at the leaf level, splitting upward like a B-tree.

flowchart TD
    I["insert object with MBR E"] --> C["ChooseLeaf: from root, pick child needing least area enlargement to cover E"]
    C --> L["add E to that leaf"]
    L --> O{"leaf has more than M entries?"}
    O -->|"no"| A["AdjustTree: enlarge MBRs on the path up"]
    O -->|"yes"| S["split leaf into two nodes"]
    S --> P["add new node entry to parent"]
    P --> O2{"parent overflows?"}
    O2 -->|"yes"| S
    O2 -->|"no"| A
    A --> R{"root was split?"}
    R -->|"yes"| G["new root: tree grows by one level"]
    R -->|"no"| D["done"]

ChooseLeaf with least enlargement. At each internal node, choose the child whose MBR would grow the least in area if it had to include the new entry; break ties by smallest area. Example: children (area 16) and (area 12), new point . Covering it, becomes (area 20, enlargement 4) and becomes (area 15, enlargement 3). Choose . The heuristic keeps MBRs small, and small MBRs mean fewer false-positive descents.

Quadratic split (Guttman). When a node overflows with entries, split them into two groups of at least :

  1. PickSeeds: for every pair compute the wasted area . The pair with the largest waste — the two entries that least belong together — seed the two groups. .
  2. PickNext: for each remaining entry compute , the enlargement each group's MBR would need to take it. Pick the entry with the largest (the one with the strongest preference) and add it to the group needing less enlargement (ties: smaller area, then fewer entries).
  3. If one group needs all remaining entries to reach , give them to it.

Worked example (, , computed by script). Five rectangles : , , , , . PickSeeds: the pair wastes , the maximum. PickNext round 1: is for , for , for ; has the largest difference (77) and joins group 1, whose MBR becomes . Round 2: is , is ; (difference 74) joins group 1, MBR . Now group 2 has one entry and one remains, so goes to group 2 to reach . Result: with MBR and with MBR — two tight, disjoint boxes.

Guttman also gave a cheaper linear split that produces worse trees.

R*-tree (Beckmann, Kriegel, Schneider and Seeger, 1990), what most production systems mean by "R-tree", changes three things:

  • ChooseSubtree minimises overlap enlargement when choosing among children that point to leaves, since overlap is what forces queries down several paths.
  • Split picks the axis minimising the sum of margins (perimeters) over candidate distributions, then the distribution with least overlap; small perimeters favour square-ish boxes.
  • Forced reinsertion: on the first overflow at a level, remove the 30% of entries farthest from the node's centre and reinsert them from the top, letting early entries migrate to better nodes. This is the main reason R*-trees beat Guttman's original.

Bulk loading with STR. When the data is known in advance, building all at once beats one-by-one insertion. Sort-Tile-Recursive (Leutenegger, Lopez and Edgington, 1997) packs leaves nearly full with little overlap:

  1. Let be the number of leaves and .
  2. Sort all rectangles by the of their centres and cut the sorted list into vertical slices of rectangles each.
  3. Sort each slice by and cut it into runs of : each run is a leaf.
  4. Repeat on the leaves' MBRs to build the next level, until one node remains.

STR costs a few sorts, . The Hilbert R-tree (Kamel and Faloutsos, 1994) sorts by Hilbert curve value instead. Shapely's and JTS's STRtree use STR, and PostgreSQL (14 and later) can build a GiST index by presorting when the operator class supports it.

No worst-case guarantee. Because MBRs overlap, a point query may visit every leaf in the worst case. R-trees are fast because real data and good heuristics keep overlap low, not because of a theorem; the priority R-tree (Arge, de Berg, Haverkort and Yi, 2004) has a provable window-query bound but is rarely used.

Space-filling curves: geohash, S2 and H3

A different approach: build no spatial tree at all. Map each point to a 1-D number so nearby points usually get nearby numbers, and store the numbers in an ordinary sorted index (B-tree, LSM tree, Redis sorted set, DynamoDB sort key).

  • Geohash interleaves the bits of longitude and latitude (a Z-order or Morton curve) and encodes them in base 32. Each character adds 5 bits, so a prefix names a quadtree-like cell, and "points in this cell" becomes a key-prefix range scan.
  • S2 (Google) projects the sphere onto a cube and walks each face's quadtree with a Hilbert curve, which never jumps between distant cells; cell IDs are 64-bit integers with levels 0 to 30. A query region is approximated by a covering of a few cells at mixed levels, each of which is a contiguous ID range.
  • H3 (Uber) uses a hierarchy of hexagons on an icosahedron. Hexagons have six equidistant neighbours, which suits movement and aggregation; the cost is that child hexagons only approximately tile their parent, and each resolution contains 12 pentagons.

Each is a quadtree (or hextree) in disguise with numbered cells. Against an R-tree: cell systems reuse any 1-D index and shard trivially, but a curve must jump somewhere, so radius queries need the cell plus neighbours and an exact-distance post-filter. Spatial Indexing covers precision tables, Redis GEOSEARCH, DynamoDB key design and how to choose between them.

The ladder: brute force → better → optimal

Two canonical problems, two ladders.

Problem A: interval overlap queries. intervals, queries "report everything overlapping ", with inserts mixed in.

  1. Brute force: scan everything with the two-comparison test. per query, insert; right for in the hundreds.
  2. Better: sort by start, binary-search the cutoff , scan that prefix checking . Prunes one side only — one long early interval forces scanning everything before — so still worst case, with sorted-array inserts.
  3. Optimal for dynamic data: augmented balanced BST. max adds the missing pruning on the other side: insert/delete/any-overlap.
  4. Optimal for static stabbing: centered interval tree or segment tree with lists, .

Problem B: nearest neighbour among points in the plane.

  1. Brute force: every distance. per query; vectorises well and often wins below a few thousand points.
  2. Better: uniform grid of cell side , searching rings outward from the query's cell. Excellent for uniform density, terrible for clustered data.
  3. Optimal in practice: k-d tree. build, expected query in low dimension, and the medians adapt to clustering.
ApproachBuildQueryUpdateHandlesWeakness
Linear scananythingslow for large
Sorted by start + binary search worstintervalsprunes one side only
Augmented BST interval tree any, allintervals1-D only
Centered interval tree stabbingstaticintervalsrebuild on change
Uniform grid to points, boxesskewed data
k-d treeexpected NN, range in 2-Drebalancing is awkwardpointshigh dimension, deletes
Quadtree / octreesimilar to k-d in practicepoints, regionsdepth unbounded by
R*-tree bulkno worst-case bound; fast in practice amortisedrectangles, polygonsoverlap; complex code

Correctness

The interval-tree pruning rule

Claim. In the single-overlap search, at a node that does not overlap the query :

  1. If the search goes right (because the left child is nil or left.max < a), the left subtree contains no interval overlapping .
  2. If the search goes left (because left.max >= a) and the left subtree contains no interval overlapping , then the right subtree contains none either.

Proof. (1) If the left child is nil, trivial. Otherwise every interval in the left subtree has , so ends before starts: no overlap.

(2) left.max is the right endpoint of some interval in the left subtree, so . By assumption does not overlap ; since , the only way for the overlap test to fail is . Every interval in the right subtree has a start at least , and by the BST order (left subtree keys node key right subtree keys). So : starts after ends. No overlap.

By induction down the path, if an overlap exists in 's subtree, one exists in the chosen child's subtree, so falling off the tree means there is none (CLRS Theorem 14.2). Report-all skips only intervals with (rule 1) or (rule 2), all of which fail the overlap test.

Maintaining max. It depends only on a node and its children, so by CLRS Theorem 14.1 red-black insert and delete keep their cost: recompute max for the two rotated nodes, lower first, and along the path to the root.

k-d tree nearest-neighbour pruning

Claim. At node with split axis and split value , if , the far subtree contains no point strictly closer to than the current best.

Proof. Suppose , so the far subtree is the left one. Every point there has (construction invariant). Then

The first inequality drops non-negative terms; the second uses . The case is symmetric with .

The bound uses one axis only, which is why it is loose (and why high dimension hurts). Tighter implementations track the full distance from to the far cell's box; the proof keeps more terms.

Right answer at termination. Every point is either compared to or lies in a subtree pruned when no point there could beat the of that moment, and only decreases. Ties go to whichever equal point was found first, so the tests below compare distances, not points.

R-tree search completeness

Invariant: each internal entry's MBR contains every MBR in its child. AdjustTree enlarges MBRs along the insertion path, splits recompute both halves, and deletes only shrink. A search skips a child only when its MBR misses the query, and any object intersecting the query lies inside MBRs that also intersect it. There is no efficiency invariant: nothing bounds how many children intersect. The quadtree argument is identical with disjoint cells; Barnes–Hut, by contrast, is a controlled approximation, not an exact algorithm.

Complexity

OperationInterval tree (augmented RB)Centered interval treek-d tree (balanced, fixed)PR quadtreeR*-tree
Build with linear-time median bulk (STR)
Space worst
Insert / deleterebuild but unbalances node visits, amortised
Point / stabbing query one, all exact matchno guarantee
Range queryas above with secondary structuresno guarantee, good in practiceno guarantee
Nearest neighbour——expected , worst expected on uniform databest-first, no guarantee

Constants and cache behaviour. Pointer-based trees take a likely cache miss per level once they outgrow cache. So production k-d trees are stored implicitly in an array (median at mid, halves on either side, recursively) with leaf buckets of 10–40 points scanned linearly; and R-trees use page-sized nodes of 50–200 entries, so a lookup touches about pages — height about 5 for a billion rectangles. For a few thousand points, a vectorised brute-force scan often beats any tree; measure first (Benchmarks).

Implementation

Two canonical implementations, each self-checking against brute force on fixed data. Both use the same deterministic generator (the MINSTD linear congruential generator, x = x * 48271 mod (2^31 - 1)) so the random tests are identical in all four languages.

1. Interval tree: any-overlap and all-overlaps queries. A static, perfectly balanced augmented BST built from intervals sorted by start. A dynamic version keeps the same max field inside a red-black or AVL tree and recomputes it after each rotation; the queries do not change.

class Node:
    __slots__ = ("lo", "hi", "max", "left", "right")

    def __init__(self, lo: int, hi: int):
        self.lo, self.hi, self.max = lo, hi, hi
        self.left: "Node | None" = None
        self.right: "Node | None" = None


def build(intervals: list[tuple[int, int]]) -> Node | None:
    a = sorted(intervals)

    def rec(l: int, r: int) -> Node | None:
        if l > r:
            return None
        m = (l + r) // 2
        n = Node(*a[m])
        n.left, n.right = rec(l, m - 1), rec(m + 1, r)
        for c in (n.left, n.right):
            if c is not None and c.max > n.max:
                n.max = c.max
        return n

    return rec(0, len(a) - 1)


def any_overlap(root: Node | None, lo: int, hi: int) -> tuple[int, int] | None:
    """CLRS INTERVAL-SEARCH: one root-to-leaf path, O(log n)."""
    n = root
    while n is not None and not (n.lo <= hi and lo <= n.hi):
        n = n.left if n.left is not None and n.left.max >= lo else n.right
    return None if n is None else (n.lo, n.hi)


def all_overlaps(root: Node | None, lo: int, hi: int) -> list[tuple[int, int]]:
    out: list[tuple[int, int]] = []

    def rec(n: Node | None) -> None:
        if n is None or n.max < lo:      # nothing below ends late enough
            return
        rec(n.left)
        if n.lo <= hi and lo <= n.hi:
            out.append((n.lo, n.hi))
        if n.lo <= hi:                   # right subtree starts >= n.lo
            rec(n.right)

    rec(root)
    return out


def brute(ivs, lo, hi):
    return sorted(iv for iv in ivs if iv[0] <= hi and lo <= iv[1])


def main() -> None:
    clrs = [(16, 21), (8, 9), (25, 30), (5, 8), (15, 23),
            (17, 19), (26, 26), (0, 3), (6, 10), (19, 20)]
    t = build(clrs)
    assert all_overlaps(t, 22, 25) == [(15, 23), (25, 30)]
    assert any_overlap(t, 22, 25) == (15, 23)
    assert all_overlaps(t, 11, 14) == [] and any_overlap(t, 11, 14) is None
    assert all_overlaps(t, 8, 8) == [(5, 8), (6, 10), (8, 9)]
    assert all_overlaps(t, 0, 30) == sorted(clrs)

    seed = 12345
    def nxt() -> int:
        nonlocal seed
        seed = seed * 48271 % 2147483647
        return seed

    ivs = []
    for _ in range(300):
        lo = nxt() % 1000
        ivs.append((lo, lo + nxt() % 50))
    t = build(ivs)
    for _ in range(300):
        a = nxt() % 1000
        b = a + nxt() % 100
        expect = brute(ivs, a, b)
        assert all_overlaps(t, a, b) == expect
        got = any_overlap(t, a, b)
        assert (got is None) == (not expect)
        assert got is None or (got[0] <= b and a <= got[1])
    print("interval tree: all checks passed")


main()
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class IntervalTree {
    static final class Node {
        final int lo, hi;
        int max;
        Node left, right;
        Node(int lo, int hi) { this.lo = lo; this.hi = hi; this.max = hi; }
    }

    static final Comparator<int[]> BY_START =
        Comparator.<int[]>comparingInt(iv -> iv[0]).thenComparingInt(iv -> iv[1]);

    static Node build(List<int[]> intervals) {
        int[][] a = intervals.toArray(new int[0][]);
        Arrays.sort(a, BY_START);
        return build(a, 0, a.length - 1);
    }

    private static Node build(int[][] a, int l, int r) {
        if (l > r) return null;
        int m = (l + r) >>> 1;
        Node n = new Node(a[m][0], a[m][1]);
        n.left = build(a, l, m - 1);
        n.right = build(a, m + 1, r);
        if (n.left != null) n.max = Math.max(n.max, n.left.max);
        if (n.right != null) n.max = Math.max(n.max, n.right.max);
        return n;
    }

    static int[] anyOverlap(Node n, int lo, int hi) {
        while (n != null && !(n.lo <= hi && lo <= n.hi))
            n = (n.left != null && n.left.max >= lo) ? n.left : n.right;
        return n == null ? null : new int[] {n.lo, n.hi};
    }

    static List<int[]> allOverlaps(Node root, int lo, int hi) {
        List<int[]> out = new ArrayList<>();
        collect(root, lo, hi, out);
        return out;
    }

    private static void collect(Node n, int lo, int hi, List<int[]> out) {
        if (n == null || n.max < lo) return;
        collect(n.left, lo, hi, out);
        if (n.lo <= hi && lo <= n.hi) out.add(new int[] {n.lo, n.hi});
        if (n.lo <= hi) collect(n.right, lo, hi, out);
    }

    static List<int[]> brute(List<int[]> ivs, int lo, int hi) {
        List<int[]> out = new ArrayList<>();
        for (int[] iv : ivs) if (iv[0] <= hi && lo <= iv[1]) out.add(iv);
        out.sort(BY_START);
        return out;
    }

    static boolean same(List<int[]> x, List<int[]> y) {
        if (x.size() != y.size()) return false;
        for (int i = 0; i < x.size(); i++) if (!Arrays.equals(x.get(i), y.get(i))) return false;
        return true;
    }

    static void check(boolean ok, String msg) { if (!ok) throw new AssertionError(msg); }

    static long seed = 12345;
    static int next() { seed = seed * 48271 % 2147483647L; return (int) seed; }

    public static void main(String[] args) {
        int[][] clrs = {{16, 21}, {8, 9}, {25, 30}, {5, 8}, {15, 23},
                        {17, 19}, {26, 26}, {0, 3}, {6, 10}, {19, 20}};
        List<int[]> data = Arrays.asList(clrs);
        Node t = build(data);
        check(same(allOverlaps(t, 22, 25), List.of(new int[] {15, 23}, new int[] {25, 30})), "22-25");
        check(Arrays.equals(anyOverlap(t, 22, 25), new int[] {15, 23}), "any 22-25");
        check(allOverlaps(t, 11, 14).isEmpty() && anyOverlap(t, 11, 14) == null, "11-14");
        check(same(allOverlaps(t, 8, 8),
                   List.of(new int[] {5, 8}, new int[] {6, 10}, new int[] {8, 9})), "8-8");
        check(same(allOverlaps(t, 0, 30), brute(data, 0, 30)), "0-30");

        List<int[]> ivs = new ArrayList<>();
        for (int i = 0; i < 300; i++) {
            int lo = next() % 1000;
            ivs.add(new int[] {lo, lo + next() % 50});
        }
        t = build(ivs);
        for (int i = 0; i < 300; i++) {
            int a = next() % 1000;
            int b = a + next() % 100;
            List<int[]> expect = brute(ivs, a, b);
            check(same(allOverlaps(t, a, b), expect), "random all");
            int[] got = anyOverlap(t, a, b);
            check((got == null) == expect.isEmpty(), "random any existence");
            check(got == null || (got[0] <= b && a <= got[1]), "random any overlaps");
        }
        System.out.println("interval tree: all checks passed");
    }
}
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <memory>
#include <optional>
#include <stdexcept>
#include <utility>
#include <vector>

using Interval = std::pair<int, int>;

struct Node {
    int lo, hi, max;
    std::unique_ptr<Node> left, right;
    Node(int l, int h) : lo(l), hi(h), max(h) {}
};

std::unique_ptr<Node> buildRange(const std::vector<Interval>& a, int l, int r) {
    if (l > r) return nullptr;
    int m = l + (r - l) / 2;
    auto n = std::make_unique<Node>(a[m].first, a[m].second);
    n->left = buildRange(a, l, m - 1);
    n->right = buildRange(a, m + 1, r);
    if (n->left) n->max = std::max(n->max, n->left->max);
    if (n->right) n->max = std::max(n->max, n->right->max);
    return n;
}

std::unique_ptr<Node> build(std::vector<Interval> a) {
    std::sort(a.begin(), a.end());
    return buildRange(a, 0, static_cast<int>(a.size()) - 1);
}

std::optional<Interval> anyOverlap(const Node* n, int lo, int hi) {
    while (n && !(n->lo <= hi && lo <= n->hi))
        n = (n->left && n->left->max >= lo) ? n->left.get() : n->right.get();
    if (!n) return std::nullopt;
    return Interval{n->lo, n->hi};
}

void collect(const Node* n, int lo, int hi, std::vector<Interval>& out) {
    if (!n || n->max < lo) return;
    collect(n->left.get(), lo, hi, out);
    if (n->lo <= hi && lo <= n->hi) out.emplace_back(n->lo, n->hi);
    if (n->lo <= hi) collect(n->right.get(), lo, hi, out);
}

std::vector<Interval> allOverlaps(const Node* root, int lo, int hi) {
    std::vector<Interval> out;
    collect(root, lo, hi, out);
    return out;
}

std::vector<Interval> brute(const std::vector<Interval>& ivs, int lo, int hi) {
    std::vector<Interval> out;
    for (auto& iv : ivs) if (iv.first <= hi && lo <= iv.second) out.push_back(iv);
    std::sort(out.begin(), out.end());
    return out;
}

void check(bool ok, const char* msg) { if (!ok) throw std::runtime_error(msg); }

std::uint64_t seed = 12345;
int nextRand() { seed = seed * 48271 % 2147483647ULL; return static_cast<int>(seed); }

int main() {
    std::vector<Interval> clrs = {{16, 21}, {8, 9}, {25, 30}, {5, 8}, {15, 23},
                                  {17, 19}, {26, 26}, {0, 3}, {6, 10}, {19, 20}};
    auto t = build(clrs);
    check(allOverlaps(t.get(), 22, 25) == std::vector<Interval>{{15, 23}, {25, 30}}, "22-25");
    check(anyOverlap(t.get(), 22, 25) == Interval{15, 23}, "any 22-25");
    check(allOverlaps(t.get(), 11, 14).empty() && !anyOverlap(t.get(), 11, 14), "11-14");
    check(allOverlaps(t.get(), 8, 8) == std::vector<Interval>{{5, 8}, {6, 10}, {8, 9}}, "8-8");
    check(allOverlaps(t.get(), 0, 30) == brute(clrs, 0, 30), "0-30");

    std::vector<Interval> ivs;
    for (int i = 0; i < 300; i++) {
        int lo = nextRand() % 1000;
        int hi = lo + nextRand() % 50;
        ivs.emplace_back(lo, hi);
    }
    t = build(ivs);
    for (int i = 0; i < 300; i++) {
        int a = nextRand() % 1000;
        int b = a + nextRand() % 100;
        auto expect = brute(ivs, a, b);
        check(allOverlaps(t.get(), a, b) == expect, "random all");
        auto got = anyOverlap(t.get(), a, b);
        check(got.has_value() == !expect.empty(), "random any existence");
        check(!got || (got->first <= b && a <= got->second), "random any overlaps");
    }
    std::cout << "interval tree: all checks passed\n";
}
type Interval = [number, number];

interface ITNode {
  lo: number;
  hi: number;
  max: number;
  left: ITNode | null;
  right: ITNode | null;
}

const byStart = (x: Interval, y: Interval): number => x[0] - y[0] || x[1] - y[1];

function build(intervals: Interval[]): ITNode | null {
  const a = [...intervals].sort(byStart);
  const rec = (l: number, r: number): ITNode | null => {
    if (l > r) return null;
    const m = (l + r) >> 1;
    const n: ITNode = { lo: a[m][0], hi: a[m][1], max: a[m][1], left: null, right: null };
    n.left = rec(l, m - 1);
    n.right = rec(m + 1, r);
    if (n.left) n.max = Math.max(n.max, n.left.max);
    if (n.right) n.max = Math.max(n.max, n.right.max);
    return n;
  };
  return rec(0, a.length - 1);
}

function anyOverlap(root: ITNode | null, lo: number, hi: number): Interval | null {
  let n = root;
  while (n && !(n.lo <= hi && lo <= n.hi)) {
    n = n.left && n.left.max >= lo ? n.left : n.right;
  }
  return n ? [n.lo, n.hi] : null;
}

function allOverlaps(root: ITNode | null, lo: number, hi: number): Interval[] {
  const out: Interval[] = [];
  const rec = (n: ITNode | null): void => {
    if (!n || n.max < lo) return;
    rec(n.left);
    if (n.lo <= hi && lo <= n.hi) out.push([n.lo, n.hi]);
    if (n.lo <= hi) rec(n.right);
  };
  rec(root);
  return out;
}

function brute(ivs: Interval[], lo: number, hi: number): Interval[] {
  return ivs.filter(([s, e]) => s <= hi && lo <= e).sort(byStart);
}

function check(ok: boolean, msg: string): void {
  if (!ok) throw new Error(msg);
}

const eq = (x: Interval[], y: Interval[]): boolean => JSON.stringify(x) === JSON.stringify(y);

let seed = 12345;
const next = (): number => (seed = (seed * 48271) % 2147483647);

const clrs: Interval[] = [[16, 21], [8, 9], [25, 30], [5, 8], [15, 23],
  [17, 19], [26, 26], [0, 3], [6, 10], [19, 20]];
let t = build(clrs);
check(eq(allOverlaps(t, 22, 25), [[15, 23], [25, 30]]), "22-25");
check(eq([anyOverlap(t, 22, 25)!], [[15, 23]]), "any 22-25");
check(allOverlaps(t, 11, 14).length === 0 && anyOverlap(t, 11, 14) === null, "11-14");
check(eq(allOverlaps(t, 8, 8), [[5, 8], [6, 10], [8, 9]]), "8-8");
check(eq(allOverlaps(t, 0, 30), brute(clrs, 0, 30)), "0-30");

const ivs: Interval[] = [];
for (let i = 0; i < 300; i++) {
  const lo = next() % 1000;
  ivs.push([lo, lo + (next() % 50)]);
}
t = build(ivs);
for (let i = 0; i < 300; i++) {
  const a = next() % 1000;
  const b = a + (next() % 100);
  const expect = brute(ivs, a, b);
  check(eq(allOverlaps(t, a, b), expect), "random all");
  const got = anyOverlap(t, a, b);
  check((got === null) === (expect.length === 0), "random any existence");
  check(got === null || (got[0] <= b && a <= got[1]), "random any overlaps");
}
console.log("interval tree: all checks passed");

2. Two-dimensional k-d tree: nearest neighbour. Median-split construction, near-side-first search with plane pruning. The tests compare the squared distance to brute force, because equidistant points make "which point" ambiguous.

import math


class KDNode:
    __slots__ = ("p", "axis", "left", "right")

    def __init__(self, p, axis, left, right):
        self.p, self.axis, self.left, self.right = p, axis, left, right


def build(points: list[tuple[int, int]], depth: int = 0) -> KDNode | None:
    if not points:
        return None
    axis = depth % 2
    pts = sorted(points, key=lambda p: p[axis])
    m = len(pts) // 2
    return KDNode(pts[m], axis, build(pts[:m], depth + 1), build(pts[m + 1:], depth + 1))


def dist2(a, b) -> int:
    return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2


def nearest(root: KDNode | None, q: tuple[int, int]) -> tuple[tuple[int, int] | None, float]:
    best_p, best_d = None, math.inf

    def rec(n: KDNode | None) -> None:
        nonlocal best_p, best_d
        if n is None:
            return
        d = dist2(n.p, q)
        if d < best_d:
            best_p, best_d = n.p, d
        diff = q[n.axis] - n.p[n.axis]
        near, far = (n.left, n.right) if diff < 0 else (n.right, n.left)
        rec(near)
        if diff * diff < best_d:         # query ball crosses the splitting plane
            rec(far)

    rec(root)
    return best_p, best_d


def main() -> None:
    pts = [(2, 3), (5, 4), (9, 6), (4, 7), (8, 1), (7, 2)]
    t = build(pts)
    assert t.p == (7, 2)
    assert nearest(t, (9, 2)) == ((8, 1), 2)
    assert nearest(t, (4, 5)) == ((5, 4), 2)
    assert nearest(t, (4, 7)) == ((4, 7), 0)
    assert nearest(None, (0, 0)) == (None, math.inf)

    seed = 12345
    def nxt() -> int:
        nonlocal seed
        seed = seed * 48271 % 2147483647
        return seed

    pts = []
    for _ in range(400):
        x = nxt() % 1000
        pts.append((x, nxt() % 1000))
    t = build(pts)
    for _ in range(300):
        x = nxt() % 1000
        q = (x, nxt() % 1000)
        p, d = nearest(t, q)
        assert d == min(dist2(r, q) for r in pts) and dist2(p, q) == d
    print("k-d tree: all checks passed")


main()
import java.util.Arrays;
import java.util.Comparator;

public class KdTree {
    record Node(int[] p, int axis, Node left, Node right) {}

    static final class Best {
        long d = Long.MAX_VALUE;
        int[] p = null;
    }

    static Node build(int[][] pts) { return build(pts.clone(), 0, pts.length, 0); }

    private static Node build(int[][] pts, int lo, int hi, int depth) {   // pts[lo, hi)
        if (lo >= hi) return null;
        int axis = depth % 2;
        Arrays.sort(pts, lo, hi, Comparator.comparingInt(p -> p[axis]));
        int m = (lo + hi) >>> 1;
        return new Node(pts[m], axis, build(pts, lo, m, depth + 1), build(pts, m + 1, hi, depth + 1));
    }

    static long dist2(int[] a, int[] b) {
        long dx = a[0] - b[0], dy = a[1] - b[1];
        return dx * dx + dy * dy;
    }

    static Best nearest(Node root, int[] q) {
        Best best = new Best();
        search(root, q, best);
        return best;
    }

    private static void search(Node n, int[] q, Best best) {
        if (n == null) return;
        long d = dist2(n.p(), q);
        if (d < best.d) { best.d = d; best.p = n.p(); }
        long diff = q[n.axis()] - n.p()[n.axis()];
        Node near = diff < 0 ? n.left() : n.right();
        Node far = diff < 0 ? n.right() : n.left();
        search(near, q, best);
        if (diff * diff < best.d) search(far, q, best);
    }

    static void check(boolean ok, String msg) { if (!ok) throw new AssertionError(msg); }

    static long seed = 12345;
    static int next() { seed = seed * 48271 % 2147483647L; return (int) seed; }

    public static void main(String[] args) {
        int[][] pts = {{2, 3}, {5, 4}, {9, 6}, {4, 7}, {8, 1}, {7, 2}};
        Node t = build(pts);
        check(Arrays.equals(t.p(), new int[] {7, 2}), "root");
        Best b = nearest(t, new int[] {9, 2});
        check(b.d == 2 && Arrays.equals(b.p, new int[] {8, 1}), "q=(9,2)");
        b = nearest(t, new int[] {4, 5});
        check(b.d == 2 && Arrays.equals(b.p, new int[] {5, 4}), "q=(4,5)");
        check(nearest(t, new int[] {4, 7}).d == 0, "q=(4,7)");
        check(nearest(null, new int[] {0, 0}).p == null, "empty");

        int[][] many = new int[400][];
        for (int i = 0; i < 400; i++) {
            int x = next() % 1000;
            many[i] = new int[] {x, next() % 1000};
        }
        t = build(many);
        for (int i = 0; i < 300; i++) {
            int x = next() % 1000;
            int[] q = {x, next() % 1000};
            long expect = Long.MAX_VALUE;
            for (int[] r : many) expect = Math.min(expect, dist2(r, q));
            b = nearest(t, q);
            check(b.d == expect && dist2(b.p, q) == expect, "random query");
        }
        System.out.println("k-d tree: all checks passed");
    }
}
#include <algorithm>
#include <array>
#include <cstdint>
#include <iostream>
#include <limits>
#include <memory>
#include <stdexcept>
#include <vector>

using Point = std::array<int, 2>;

struct Node {
    Point p;
    int axis;
    std::unique_ptr<Node> left, right;
};

std::unique_ptr<Node> build(std::vector<Point>& pts, std::size_t lo, std::size_t hi, int depth) {
    if (lo >= hi) return nullptr;
    int axis = depth % 2;
    std::size_t m = lo + (hi - lo) / 2;
    // linear-time median: left <= pts[m] <= right on this axis
    std::nth_element(pts.begin() + lo, pts.begin() + m, pts.begin() + hi,
                     [axis](const Point& a, const Point& b) { return a[axis] < b[axis]; });
    auto n = std::make_unique<Node>();
    n->p = pts[m];
    n->axis = axis;
    n->left = build(pts, lo, m, depth + 1);
    n->right = build(pts, m + 1, hi, depth + 1);
    return n;
}

std::unique_ptr<Node> build(std::vector<Point> pts) { return build(pts, 0, pts.size(), 0); }

long long dist2(const Point& a, const Point& b) {
    long long dx = a[0] - b[0], dy = a[1] - b[1];
    return dx * dx + dy * dy;
}

struct Best {
    long long d = std::numeric_limits<long long>::max();
    Point p{};
    bool found = false;
};

void search(const Node* n, const Point& q, Best& best) {
    if (!n) return;
    long long d = dist2(n->p, q);
    if (d < best.d) { best.d = d; best.p = n->p; best.found = true; }
    long long diff = q[n->axis] - n->p[n->axis];
    const Node* nearSide = diff < 0 ? n->left.get() : n->right.get();
    const Node* farSide = diff < 0 ? n->right.get() : n->left.get();
    search(nearSide, q, best);
    if (diff * diff < best.d) search(farSide, q, best);
}

Best nearest(const Node* root, const Point& q) {
    Best best;
    search(root, q, best);
    return best;
}

void check(bool ok, const char* msg) { if (!ok) throw std::runtime_error(msg); }

std::uint64_t seed = 12345;
int nextRand() { seed = seed * 48271 % 2147483647ULL; return static_cast<int>(seed); }

int main() {
    std::vector<Point> pts = {{2, 3}, {5, 4}, {9, 6}, {4, 7}, {8, 1}, {7, 2}};
    auto t = build(pts);
    check(t->p == Point{7, 2}, "root");
    auto b = nearest(t.get(), {9, 2});
    check(b.d == 2 && b.p == Point{8, 1}, "q=(9,2)");
    b = nearest(t.get(), {4, 5});
    check(b.d == 2 && b.p == Point{5, 4}, "q=(4,5)");
    check(nearest(t.get(), {4, 7}).d == 0, "q=(4,7)");
    check(!nearest(nullptr, {0, 0}).found, "empty");

    std::vector<Point> many;
    for (int i = 0; i < 400; i++) {
        int x = nextRand() % 1000;
        int y = nextRand() % 1000;
        many.push_back({x, y});
    }
    t = build(many);
    for (int i = 0; i < 300; i++) {
        int x = nextRand() % 1000;
        int y = nextRand() % 1000;
        Point q{x, y};
        long long expect = std::numeric_limits<long long>::max();
        for (auto& r : many) expect = std::min(expect, dist2(r, q));
        b = nearest(t.get(), q);
        check(b.d == expect && dist2(b.p, q) == expect, "random query");
    }
    std::cout << "k-d tree: all checks passed\n";
}
type Point = [number, number];

interface KDNode {
  p: Point;
  axis: number;
  left: KDNode | null;
  right: KDNode | null;
}

function build(points: Point[], depth = 0): KDNode | null {
  if (points.length === 0) return null;
  const axis = depth % 2;
  const pts = [...points].sort((a, b) => a[axis] - b[axis]);
  const m = pts.length >> 1;
  return {
    p: pts[m],
    axis,
    left: build(pts.slice(0, m), depth + 1),
    right: build(pts.slice(m + 1), depth + 1),
  };
}

const dist2 = (a: Point, b: Point): number => (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2;

function nearest(root: KDNode | null, q: Point): { p: Point | null; d: number } {
  let bestP: Point | null = null;
  let bestD = Infinity;
  const rec = (n: KDNode | null): void => {
    if (!n) return;
    const d = dist2(n.p, q);
    if (d < bestD) {
      bestD = d;
      bestP = n.p;
    }
    const diff = q[n.axis] - n.p[n.axis];
    const [near, far] = diff < 0 ? [n.left, n.right] : [n.right, n.left];
    rec(near);
    if (diff * diff < bestD) rec(far);
  };
  rec(root);
  return { p: bestP, d: bestD };
}

function check(ok: boolean, msg: string): void {
  if (!ok) throw new Error(msg);
}

let seed = 12345;
const next = (): number => (seed = (seed * 48271) % 2147483647);

const six: Point[] = [[2, 3], [5, 4], [9, 6], [4, 7], [8, 1], [7, 2]];
let t = build(six);
check(t !== null && t.p[0] === 7 && t.p[1] === 2, "root");
let r = nearest(t, [9, 2]);
check(r.d === 2 && JSON.stringify(r.p) === "[8,1]", "q=(9,2)");
r = nearest(t, [4, 5]);
check(r.d === 2 && JSON.stringify(r.p) === "[5,4]", "q=(4,5)");
check(nearest(t, [4, 7]).d === 0, "q=(4,7)");
check(nearest(null, [0, 0]).p === null, "empty");

const many: Point[] = [];
for (let i = 0; i < 400; i++) {
  const x = next() % 1000;
  many.push([x, next() % 1000]);
}
t = build(many);
for (let i = 0; i < 300; i++) {
  const x = next() % 1000;
  const q: Point = [x, next() % 1000];
  const expect = Math.min(...many.map((p) => dist2(p, q)));
  r = nearest(t, q);
  check(r.d === expect && r.p !== null && dist2(r.p, q) === expect, "random query");
}
console.log("k-d tree: all checks passed");

Variants worth having in your fingers

  • k nearest neighbours. A max-heap of size replaces best; prune against its top once full (heaps).
  • Radius query. Same recursion with a fixed in place of .
  • Higher . Use depth % k, or split on the axis of greatest spread.
  • Leaf buckets of 8–32 points scanned linearly: the production norm.
  • Dynamic interval tree. Put max in your treap or red-black tree and update it in the rotation helper.

Real-world uses

  • PostGIS and PostgreSQL GiST. CREATE INDEX ... USING GIST (geom) builds an R-tree-shaped index on the Generalized Search Tree framework (Hellerstein, Naughton and Pfeffer, 1995): GiST supplies the balanced tree, the PostGIS operator class supplies box union, penalty (enlargement) and pick-split. The index holds bounding boxes; && is answered by it, and ST_Intersects/ST_DWithin use it as the filter step before exact geometry. PostgreSQL's SP-GiST ships quad_point_ops (quadtree) and kd_point_ops (k-d tree) for its point type, and GiST on range types answers interval overlap (&&) from SQL. See Spatial Indexing and Indexing Deep Dive.
  • SQLite R*Tree module. CREATE VIRTUAL TABLE demo USING rtree(id, minX, maxX, minY, maxY); creates an R*-tree in ordinary SQLite pages. It is compiled into most builds — so it is on most phones — and its documentation is the shortest readable description of a production R-tree. MySQL InnoDB SPATIAL indexes are R-trees too.
  • Lucene and Elasticsearch. Since Lucene 6, numeric and geo-point fields use BKD trees (block k-d trees; Procopiuc et al., 2003): k-d splits, disk-block leaves, updates by merging segments as an LSM tree does (Storage Engines).
  • The Linux kernel. include/linux/interval_tree_generic.h builds interval trees on the augmented red-black tree; the memory manager uses one (i_mmap) to find every mapping of a file range — an all-overlaps query. See Virtual Memory.
  • Genomics. "Which genes overlap this read?" runs billions of times, via interval trees, nested containment lists, or the UCSC binning scheme (also in the BAM/tabix indexes), a fixed-depth segment tree over chromosome coordinates.
  • Scientific Python. scipy.spatial.KDTree and scikit-learn's KDTree/BallTree drive nearest-neighbour classifiers, DBSCAN and point-cloud work in low dimension.
  • Games, physics, graphics. Octrees for level-of-detail and voxels, dynamic AABB trees (Box2D b2DynamicTree, Bullet btDbvt) for broad-phase collision, bounding-volume hierarchies for ray tracing, including GPU hardware ray tracing.
  • Map tiles. Slippy maps (OpenStreetMap, Google, Bing, Mapbox) serve tiles addressed z/x/y, a quadtree of the Web Mercator square; Bing exposes the path as a quadkey.
  • Ride-hailing and delivery. H3/S2/geohash cells for matching and aggregation, PostGIS R-trees for polygon geofences (Spatial Indexing).

Pitfalls & edge cases

  • Open vs closed intervals. The code is closed, so [5,8] and [8,9] overlap. Calendars want half-open [start, end): the test becomes lo < b && a < hi and the prune becomes max <= a. Mixing conventions gives boundary-only bugs.
  • Stale max after rotations or deletes. BST-order tests still pass while queries silently miss intervals. Recompute max in the rotation helper, child first.
  • > instead of >= in left.max >= a. Misses an interval ending exactly at the query start.
  • Distance overflow. Squared distances of 32-bit coordinates need 64 bits.
  • Mixing squared and unsquared distances in the prune test.
  • Duplicate split coordinates. Median by position still works: the invariant is left split right and the proof allows ties on both sides.
  • k-d inserts and deletes unbalance the tree; libraries rebuild periodically or keep static trees of sizes (the logarithmic method BKD indexes use).
  • Latitude/longitude are not a plane. A degree of longitude shrinks with latitude and the antimeridian splits neighbours: project, use a sphere-aware index, or use haversine with wrap-around boxes.
  • Duplicate points in a capacity-1 PR quadtree recurse forever. Cap depth or use buckets.
  • Long diagonal objects have huge MBRs that overlap everything; split linestrings before indexing.

Variations

  • Range tree. A BST on whose nodes hold sorted -structures of their subtrees: 2-D range queries in (or with fractional cascading) at space. Guaranteed, unlike a k-d tree, but bigger.
  • Priority search tree (McCreight, 1985). Heap on , BST on : three-sided queries in , space.
  • 2-D Fenwick tree / segment tree of segment trees. Counting points in rectangles with updates on a grid; see Fenwick Trees.
  • Ball tree, vantage-point tree. Metric trees partitioning by distance to pivots, so any metric works; better than k-d trees in moderate dimension, still cursed eventually.
  • BVH, R+-tree, X-tree. A binary R-tree built top-down for ray tracing; R-trees that clip objects to forbid overlap; R-trees with "supernodes" for higher dimension.
  • Z-ordering in columnar stores. Delta Lake-style Z-ordering clusters files along a space-filling curve so multi-column filters skip files.

Practice ladder

Easy to hard: geometric tests, then interval structures, then sweeps and counts over compressed coordinates.

  1. Rectangle Overlap (LeetCode 836) — do two axis-aligned rectangles share positive area? The MBR test every R-tree node runs.
Hint

Projections must overlap on both axes, strictly.

  1. K Closest Points to Origin (LeetCode 973) — the points nearest the origin. The bounded max-heap of k-NN search.
Hint

One query: a size- heap or quickselect beats building a tree. Trees pay off over many queries.

Solution
import heapq

def k_closest(points: list[list[int]], k: int) -> list[list[int]]:
    # max-heap of size k on squared distance (negated for heapq)
    heap: list[tuple[int, int, int]] = []
    for x, y in points:
        d = x * x + y * y
        if len(heap) < k:
            heapq.heappush(heap, (-d, x, y))
        elif -heap[0][0] > d:
            heapq.heapreplace(heap, (-d, x, y))
    return [[x, y] for _, x, y in heap]

assert sorted(k_closest([[1, 3], [-2, 2]], 1)) == [[-2, 2]]
assert sorted(k_closest([[3, 3], [5, -1], [-2, 4]], 2)) == [[-2, 4], [3, 3]]

time, space.

  1. My Calendar I (LeetCode 729) — accept a half-open booking only if it overlaps none accepted. Disjoint stored intervals, so neighbours suffice.
Hint

Sorted by start, a new [s, e) can only collide with its predecessor or successor.

Solution
import bisect

class MyCalendar:
    def __init__(self) -> None:
        self.starts: list[int] = []
        self.ends: list[int] = []

    def book(self, s: int, e: int) -> bool:
        i = bisect.bisect_right(self.starts, s)
        if i > 0 and self.ends[i - 1] > s:          # predecessor runs into us
            return False
        if i < len(self.starts) and self.starts[i] < e:  # successor starts inside us
            return False
        self.starts.insert(i, s)
        self.ends.insert(i, e)
        return True

cal = MyCalendar()
assert [cal.book(10, 20), cal.book(15, 25), cal.book(20, 30)] == [True, False, True]
assert cal.book(5, 10) is True and cal.book(9, 11) is False

to search; list insertion is in Python. A TreeMap (Java) or std::map (C++) makes the whole operation .

  1. My Calendar II (LeetCode 731) — allow double but reject triple bookings. A second set of overlaps to query.
Hint

Reject if the booking hits any stored pairwise overlap; otherwise record its intersections with existing bookings as new overlaps.

  1. Construct Quad Tree (LeetCode 427) — build the region quadtree of a binary grid.
Hint

Recurse on quadrants; merge four same-valued leaves into one.

Solution
class Node:
    def __init__(self, val, isLeaf, topLeft=None, topRight=None, bottomLeft=None, bottomRight=None):
        self.val, self.isLeaf = val, isLeaf
        self.topLeft, self.topRight = topLeft, topRight
        self.bottomLeft, self.bottomRight = bottomLeft, bottomRight

def construct(grid: list[list[int]]) -> Node:
    def rec(r: int, c: int, size: int) -> Node:
        if size == 1:
            return Node(grid[r][c] == 1, True)
        h = size // 2
        kids = [rec(r, c, h), rec(r, c + h, h), rec(r + h, c, h), rec(r + h, c + h, h)]
        if all(k.isLeaf for k in kids) and len({k.val for k in kids}) == 1:
            return Node(kids[0].val, True)
        return Node(True, False, *kids)
    return rec(0, 0, len(grid))

def leaves(n: Node) -> int:
    if n.isLeaf:
        return 1
    return sum(leaves(k) for k in (n.topLeft, n.topRight, n.bottomLeft, n.bottomRight))

g = [[1, 1, 0, 0], [1, 1, 0, 0], [1, 1, 1, 1], [1, 1, 1, 1]]
root = construct(g)
assert not root.isLeaf and leaves(root) == 4
assert construct([[1, 1], [1, 1]]).isLeaf
assert leaves(construct([[0, 1], [1, 0]])) == 4

time: each level does constant work per cell of the level below, and the levels shrink geometrically.

  1. Queries on Number of Points Inside a Circle (LeetCode 1828) — count points in each circle. Filter-and-refine.
Hint

Brute force passes. For many points, binary-search the -strip or run a k-d radius query.

  1. Data Stream as Disjoint Intervals (LeetCode 352) — maintain a stream's union as disjoint intervals. Ordered map with merge-on-insert.
Hint

The new value extends a neighbour, merges two, or starts a new interval.

  1. Range Module (LeetCode 715) — add, remove and query tracked half-open ranges. Interval maintenance under deletion.
Hint

Sorted disjoint intervals with binary-searched splices, or a lazily created segment tree with set-covered tags.

  1. My Calendar III (LeetCode 732) — report maximum simultaneous bookings after each booking. Range add plus global max.
Hint

Each booking adds 1 on [s, e); a sorted difference map rescanned per booking suffices at these sizes.

  1. Falling Squares (LeetCode 699) — track the tallest stack of dropped squares. Range max then range assign.
Hint
Compress edges; each drop reads the range max and assigns `max + side` with a lazy segment tree.
  1. Count of Range Sum (LeetCode 327) — count subarrays with sum in [lower, upper]. A dominance count via prefix sums and merge sort.
Hint
Count pairs `i < j` with `P[j] - upper <= P[i] <= P[j] - lower`; in merge sort two pointers do it.
Solution
```python
def count_range_sum(nums: list[int], lower: int, upper: int) -> int:
    pre = [0]
    for x in nums:
        pre.append(pre[-1] + x)

    def sort_count(a: list[int]) -> tuple[list[int], int]:
        if len(a) <= 1:
            return a, 0
        m = len(a) // 2
        left, cl = sort_count(a[:m])
        right, cr = sort_count(a[m:])
        cnt, lo, hi = cl + cr, 0, 0
        for r in right:                     # count left values in [r - upper, r - lower]
            while lo < len(left) and left[lo] < r - upper:
                lo += 1
            while hi < len(left) and left[hi] <= r - lower:
                hi += 1
            cnt += hi - lo
        return sorted(left + right), cnt   # sorted() on two runs is linear (Timsort)

    return sort_count(pre)[1]

assert count_range_sum([-2, 5, -1], -2, 2) == 3
assert count_range_sum([0], 0, 0) == 1
assert count_range_sum([], 0, 0) == 0
```

<span class="math" data-tex="O(n \log n)"></span> time, <span class="math" data-tex="O(n)"></span> space. The pointers `lo` and `hi` only move forward because `right` is sorted.
  1. Rectangle Area II (LeetCode 850) — area of a union of rectangles. Sweep line plus covered length.
Hint
Between consecutive edge <span class="math" data-tex="x"></span> values the covered <span class="math" data-tex="y"></span>-length is constant; multiply by the strip width.
Solution
```python
def rectangle_area(rects: list[list[int]]) -> int:
    events = []
    for x1, y1, x2, y2 in rects:
        events.append((x1, 1, y1, y2))
        events.append((x2, -1, y1, y2))
    events.sort()
    active: list[tuple[int, int]] = []
    total, prev_x = 0, events[0][0]

    def covered() -> int:
        length, cur_end = 0, -1
        for lo, hi in sorted(active):
            lo = max(lo, cur_end)
            if hi > lo:
                length += hi - lo
                cur_end = hi
        return length

    for x, kind, y1, y2 in events:
        total += covered() * (x - prev_x)
        prev_x = x
        if kind == 1:
            active.append((y1, y2))
        else:
            active.remove((y1, y2))
    return total % (10**9 + 7)

assert rectangle_area([[0, 0, 2, 2], [1, 0, 2, 3], [1, 0, 3, 1]]) == 6
assert rectangle_area([[0, 0, 1000000000, 1000000000]]) == 49
```

<span class="math" data-tex="O(n^2 \log n)"></span>: fine for <span class="math" data-tex="n \le 200"></span>. Replacing `covered()` with a segment tree over compressed <span class="math" data-tex="y"></span> coordinates that stores, per node, a cover count and the covered length gives <span class="math" data-tex="O(n \log n)"></span>.
  1. Forest Queries II (CSES 1739) — toggle grid cells and count rectangles. The 2-D Fenwick tree.
Hint
Nested Fenwick loops; four prefix queries by inclusion–exclusion, <span class="math" data-tex="O(\log^2 n)"></span>.
  1. Nested Ranges Count (CSES 2169) — for each range, count ranges it contains and that contain it. Containment as dominance counting.
Hint
Sort by start ascending, end descending; containers of <span class="math" data-tex="i"></span> are earlier ranges with end <span class="math" data-tex="\ge"></span> end<span class="math" data-tex="_i"></span>, counted with a Fenwick tree over compressed ends.

Common mistakes & interview follow-ups

  • Writing a segment tree when asked for an interval tree (or vice versa). Ask which operations matter: dynamic insert + any-overlap → augmented BST; static stabbing or counting → segment tree.
  • "Intervals arrive as a stream?" The augmented balanced BST is already dynamic. If accepted intervals are disjoint, an ordered map suffices.
  • "Delete an interval?" BST delete by (lo, hi), recompute max up the path; duplicates need a count or id in the key.
  • "k nearest, not one?" Bounded max-heap of size ; prune against its top once full.
  • "Points move every frame?" Rebuild per frame if is small; otherwise a uniform grid, loose quadtree, or dynamic AABB tree with fattened boxes.
  • "Data does not fit in memory?" STR-loaded R-tree or BKD tree with page-sized nodes, or a space-filling-curve key in an existing B-tree/LSM store.
  • "512-dimensional embeddings?" Not a k-d tree: explain the curse, name HNSW/IVF, accept approximate answers measured by recall.
  • "Why do databases prefer R-trees?" Balanced, page-oriented and dynamic like B-trees, and they index rectangles and polygons without cutting them; k-d trees are binary and hard to rebalance, quadtree depth depends on the data.

Quick quiz

  1. In the interval tree, the search is at node , which does not overlap the query , and x.left.max >= a. Why is it safe to never look at 's right subtree if the left subtree turns out to have no overlap?
Answer

x.left.max belongs to some interval in the left subtree with . Since does not overlap the query, . Every interval in the right subtree starts at or after , so none of them overlap either.

  1. A k-d tree NN search is at a node splitting on , the query is and the best squared distance so far is 16. Does it search the far side? What if the best were 9?
Answer

, . With best 16: , so yes — the ball of radius 4 crosses the plane. With best 9: , so no; a point on the far side is at distance at least 3, which cannot beat 3 strictly.

  1. Why is a k-d tree a poor choice for nearest-neighbour search over 768-dimensional text embeddings, and what is used instead?
Answer

With the rule is hopeless: each axis is split at most once or twice, distances concentrate, and the query ball crosses almost every splitting plane, so the search visits nearly the whole tree (measured above at 97% already for , ). Production systems use approximate nearest-neighbour indexes such as HNSW graphs or IVF/product quantisation.

  1. An R-tree node with children and receives the point . Which child does Guttman's ChooseLeaf pick, and why might an R*-tree pick differently in general?
Answer

Area enlargement for is ; for it is ; Guttman picks . The R*-tree, at the level above the leaves, minimises overlap enlargement with sibling MBRs instead of area enlargement, because overlap is what makes queries descend multiple paths.

Further reading / sources

  • Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (3rd ed.), §14.1–14.3 "Augmenting Data Structures" and "Interval trees" (Theorems 14.1 and 14.2, Exercise 14.3-4).
  • de Berg, Cheong, van Kreveld, Overmars, Computational Geometry: Algorithms and Applications (3rd ed.), ch. 5 "Orthogonal Range Searching" (k-d trees, range trees), ch. 10 "More Geometric Data Structures" (interval trees, priority search trees, segment trees), ch. 14 "Quadtrees".
  • H. Samet, Foundations of Multidimensional and Metric Data Structures, 2006.
  • J. L. Bentley, "Multidimensional binary search trees used for associative searching", Communications of the ACM 18(9), 1975.
  • R. A. Finkel and J. L. Bentley, "Quad trees: a data structure for retrieval on composite keys", Acta Informatica 4, 1974.
  • J. H. Friedman, J. L. Bentley, R. A. Finkel, "An algorithm for finding best matches in logarithmic expected time", ACM Transactions on Mathematical Software 3(3), 1977.
  • A. Guttman, "R-trees: a dynamic index structure for spatial searching", SIGMOD 1984.
  • N. Beckmann, H.-P. Kriegel, R. Schneider, B. Seeger, "The R*-tree: an efficient and robust access method for points and rectangles", SIGMOD 1990.
  • S. T. Leutenegger, M. A. Lopez, J. Edgington, "STR: a simple and efficient algorithm for R-tree packing", ICDE 1997.
  • J. Barnes and P. Hut, "A hierarchical O(N log N) force-calculation algorithm", Nature 324, 1986.
  • R. Weber, H.-J. Schek, S. Blott, similarity search in high-dimensional spaces, VLDB 1998.
  • Yu. A. Malkov, D. A. Yashunin, "Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs", arXiv:1603.09320.
  • SQLite: The R*Tree Module; PostgreSQL: GiST Indexes and SP-GiST Indexes; PostGIS: Spatial Indexing.
  • Wikipedia: k-d tree, R-tree.
  • Archon: Spatial Indexing, Indexing Deep Dive, Intervals, Segment Trees in Depth, Binary Search Trees, Advanced Data Structures.

Module 3 navigation. Previous: Heavy-Light & Centroid Decomposition. Next: Capstone: A Range-Query Engine. Module overview: Trees. Related in this module: Balanced BSTs, Fenwick Trees, Treaps, Splay Trees & Skip Lists, Trees (Overview). Course home: DSA: Zero to Mastery.