↩ 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.

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.

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 specifically when the data is static (or rebuilt rarely) and queries vastly outnumber changes — a read-mostly workload where segment tree's per-query log n would otherwise be paid over and over for no reason.

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.