Sparse Table: range minimum in O(1)

The idea: precompute every power-of-two block

A range minimum query (RMQ) asks for min(A[l..r]). If the array never changes, you can spend O(n log n) time and memory once and then answer every query in O(1). A sparse table stores the minimum of every block whose length is a power of two: st[k][i] = min(A[i .. i + 2^k − 1]), for every k with 2^k ≤ n and every start i where the block fits.

On the canvas the array is on top and the table under it, one row per k. Cell st[k][i] sits in column i, the start of its block, so row k is 2^k − 1 cells shorter than the array. The page uses n = 16 and 0-based indices, so k runs from 0 (blocks of 1) to 4 (the whole array).

Building: row k from row k − 1

A block of length 2^k is two blocks of length 2^(k−1) side by side, so each cell comes from two cells of the row above:

for (int i = 0; i < n; i++) st[0][i] = A[i];
for (int k = 1; (1 << k) <= n; k++)
    for (int i = 0; i + (1 << k) <= n; i++)
        st[k][i] = min(st[k-1][i], st[k-1][i + (1 << (k-1))]);

For example st[2][4] = min(st[1][4], st[1][6]) = min(6, 4) = 4, the minimum of A[4..7]. Every cell costs O(1), and there are about n log₂ n of them (Demo: build the table, row k from row k − 1: 38 cells after row 0).

Query: two overlapping blocks

For A[l..r] of length len = r − l + 1, let k = ⌊log₂ len⌋, the largest power of two that fits. One block of length 2^k starts at l, another ends at r. Both lie inside the range and together they cover it, because 2 · 2^k > len. So

int k = lg[r - l + 1];
return min(st[k][l], st[k][r - (1 << k) + 1]);

lg[] is a small table filled once with lg[1] = 0, lg[i] = lg[i / 2] + 1, so the query has no loop at all. For A[2..12], len = 11 and k = 3: block 1 is A[2..9] with st[3][2] = 3, block 2 is A[5..12] with st[3][5] = 2, and the answer is min(3, 2) = 2 (Demo: min A[2..12]: two blocks of 8 overlap). When len is a power of two the two blocks are the same block (Demo: min A[4..7]: length 4 is one block).

Why min and max, but not sum

The overlap is read twice. That is harmless when the operation is idempotent: min(x, x) = x, and the same holds for max, gcd, bitwise AND and OR (Demo: max A[0..6] works the same way: max(9, 12) = 12). Sum is not: for A[2..12] the two blocks give 65 + 72 = 137, but the true sum is 91, because A[5..9] = 46 was added twice.

A sparse table can still answer a sum with disjoint blocks: split the length into powers of two, largest first. 11 = 8 + 2 + 1 gives st[3][2] + st[1][10] + st[0][12] = 65 + 13 + 13 = 91, one block per 1 bit of the length, so O(log n) (Demo: sum A[2..12]: the overlap counts twice). For static sums a prefix-sum array is simpler and O(1).

Static data only

A sparse table has no update. Changing A[7] makes every cell whose block contains index 7 wrong: 1 + 2 + 4 + 8 + 1 = 16 of the 54 cells, O(n) in general (Demo: change A[7]: 16 cells go stale). When values change, use a tree that updates O(log n) nodes.

	Sparse table	Segment tree	Fenwick tree
Build	O(n log n)	O(n)	O(n)
Range min / max	O(1)	O(log n)	not directly
Range sum	O(log n)	O(log n)	O(log n)
Point update	rebuild, O(n log n)	O(log n)	O(log n)
Memory	n log n	about 2n to 4n	n

See Segment Tree and Fenwick Tree for the structures that allow updates, and Segment Tree vs Fenwick Tree for those two side by side. Sparse tables are used for lowest common ancestor queries (RMQ over an Euler tour of the tree) and inside suffix-array LCP queries.

What the page leaves out

The page fixes n = 16 and shows one function at a time. It leaves out the disjoint sparse table (O(1) for any associative operation), the O(n)-preprocessing RMQ of Fischer and Heun with blocks of size log n, the 2D sparse table for submatrix minimum, storing the index of the minimum instead of its value, and the memory layout st[i][k] versus st[k][i] for cache behaviour.

References

cp-algorithms: Sparse Table

M. A. Bender and M. Farach-Colton, "The LCA Problem Revisited", LATIN 2000

Wikipedia: Range minimum query