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