Cairn
data structures · trees · O(n log n) build / O(1) range query, no updates

↩ back to Array-Backed Trees

Sparse Table (Range Minimum Query)

A segment tree answers a range-minimum query in O(log n) and can also handle point updates in O(log n). A sparse table gives up the second half of that deal entirely — the array is fixed forever once built — and in exchange gets the query down to O(1). The mechanism is precomputing the answer for every range whose length is a power of two, then answering an arbitrary range by combining just two of those precomputed ranges, letting them overlap in the middle. Letting them overlap is the whole trick, and it's also the whole catch: it only gives the right answer when the combining operation doesn't care about being asked twice.

Try it

The array below is the same 8 values Segment Tree's demo uses, so answers can be checked directly against that page. Below it is the sparse table itself: row k holds, at each starting index i, the combined value of the 2k elements starting at i — row 0 is just the array itself (length-1 ranges), row 1 holds every length-2 range, row 2 every length-4 range, row 3 the one length-8 range. Pick a query range and a combining operation and press Query, then step through to see exactly which two table cells get combined.

values (index 0..7)
sparse table — row k holds every length-2k range's combined value
Pick an operation and a range, press Query, then Step through it.

Why it works

Building row k from row k-1 is one doubling step: st[k][i] = combine(st[k-1][i], st[k-1][i + 2k-1]) — the length-2^k range starting at i is exactly the concatenation of two length-2^(k-1) ranges, one already sitting in row k-1 at i, the other right next to it at i + 2^(k-1). Row 0 needs no work (each length-1 range is just values[i]), and there are log₂ n more rows above it, so the whole table costs O(n log n) to fill: O(n) cells, and building the default array's row 2 value at i=0 costs one combine call reading two already-computed row-1 cells, same as every other cell.

Querying [l, r] means picking exactly one row and two cells from it. Let len = r - l + 1 and k = ⌊log₂ len⌋ — the largest power of two that still fits inside the range. Row k has a precomputed answer for the length- 2^k range starting at l, and another for the length-2^k range ending at r (starting at r - 2^k + 1). Together those two ranges cover all of [l, r] — with overlap in the middle whenever 2^k < len, which is every case where len isn't itself a power of two. On the default array, querying min over [1, 5]: len = 5, k = ⌊log₂ 5⌋ = 2, so the two blocks are st[2][1] (range [1,4], value 1) and st[2][2] (range [2,5], value 1) — they share indices [2,4], and min(1, 1) = 1, matching both a naive scan of [1,5] and Segment Tree's own worked example for the identical range on the identical array.

Reference implementation

One array per row, each row shorter than the last by 2k - 1 — a length- 2^k range only fits starting at indices 0 through n - 2^k:

class SparseTable {
  constructor(values, combine) {
    this.combine = combine;
    const n = values.length;
    const K = Math.floor(Math.log2(n)) + 1;
    this.st = [values.slice()];
    for (let k = 1; k < K; k++) {
      const half = 1 << (k - 1);
      const len = 1 << k;
      const row = [];
      for (let i = 0; i + len <= n; i++) {
        row.push(combine(this.st[k - 1][i], this.st[k - 1][i + half]));
      }
      this.st.push(row);
    }
  }

  query(l, r) {                          // inclusive range [l, r]
    const len = r - l + 1;
    const k = Math.floor(Math.log2(len));
    const blockSize = 1 << k;
    return this.combine(this.st[k][l], this.st[k][r - blockSize + 1]);
  }
}

const rmq = new SparseTable([5, 2, 8, 1, 9, 3, 7, 4], Math.min);
rmq.query(1, 5);                         // 1 — no rebuild, no tree walk, one array read each side

Pitfalls

The O(1) query only works for idempotent operations — overlap is invisible to them and nothing else. min(x, x) = x, so asking twice about the shared middle indices costs nothing: the demo's min mode matches a naive scan on every one of the 36 possible [l, r] ranges over the default 8-element array, checked exhaustively, not sampled. Switching the demo to sum mode reuses the identical two-block query logic — same k, same two cells, same combine call — and it is wrong on all 36 of those same ranges, not just the ones with visible overlap: even a query whose length is itself already a power of two (say [0,3], length 4) picks st[2][0] and st[2][0] again, the identical cell twice, so sum silently doubles the entire true answer instead of just double-counting a middle slice. There's no partial-credit case here — a non-idempotent combine breaks the whole two-block trick, not just the overlapping middle, which is why sum/count/product range queries need a Fenwick tree (invertible) or a segment tree (general associative, no overlap trick) instead — never a sparse table.

The array is genuinely frozen, not just "update is slow." A segment tree's update touches O(log n) nodes because only the root-to-leaf path for the changed index depends on it. In a sparse table, st[k][i] depends on every value in [i, i + 2^k - 1] — changing one value invalidates a cell in every row whose range covers it, up to O(log n) cells per row and O(log n) rows, and because each row is built from the row below, an honest single-value update still needs to re-derive part of the table bottom-up. In practice nobody patches a sparse table in place — a changed array just gets rebuilt from scratch, the full O(n log n) the constructor already costs. If updates happen at all, even rarely, that cost is the whole reason to reach for a segment tree instead.

Measuring against Segment Tree

The Complexity section below says this structure is "worth it" once queries vastly outnumber changes — true, but it doesn't say how many is "vastly," and the honest number turns out to be bigger than that phrase suggests, not smaller, and it grows as the array grows rather than staying fixed. The fair test: build both structures from the identical random array, time the build, then run the identical sequence of random range-minimum queries against both and time that too — same build-cost-amortization question Same Big-O, Different Speed asks of Binary Search against an AVL Tree, just about construction cost instead of memory layout. Timing this page's own SparseTable above against Segment Tree's own reference implementation directly (wall-clock, no synthetic benchmark library) at three sizes, one representative run each:

The multiple of n needed to break even grows as n grows, not shrinks, because the build-cost gap scales with the extra log n factor Sparse Table's own O(n log n) pays over Segment Tree's O(n), while the per-query saving stays a roughly fixed number of nanoseconds no matter how big the array gets. In plain terms: a workload needs to run more range queries against the finished structure than the array even has elements — by a factor of a few — before Sparse Table's extra build cost actually pays for itself. A one-off script that queries a handful of times and exits never clears that bar, no matter how many times it's invoked; a workload that reuses one built structure for many more queries than it has elements — the common case in, say, a competitive-programming problem with Q ≫ N — clears it easily. Try it below at the sizes measured above, or pick your own query count to find the break-even point directly.

Build cost

Total cost at the chosen query count (build once + that many queries)

Pick an array size and a query count, then press Measure — it builds both structures for real from the same random array and runs the same random range-minimum queries against both.

Complexity

Time: O(n log n) to build (log n rows, each O(n) to fill), O(1) per query — no loop, no tree walk, exactly one combine call reading two already-computed cells. Space: O(n log n), one value per (row, index) pair across all log n rows — more than a segment tree's O(n), the price of caching every power-of-two range instead of just the O(n) nodes a tree needs. Worth it once queries outnumber changes by enough to pay back that larger build — see Measuring against Segment Tree above for the real number, which is bigger than "vastly outnumber" suggests and grows with n, not shrinks. This site's guide, Space for Time, puts an actual number on the memory side of that same trade — 4.5×–11.5× more stored values than Segment Tree, growing with n — next to two other memory-for-speed structures on this site.

This site's guide, Choosing a Range Query Structure, compares this entry against the other five Array-Backed Trees structures that answer the same kind of question side by side.