Chapter 8 · Data Structures on Trees
Sparse Table and RMQ
O(1) range minimum queries on idempotent operations, with the log table that makes the proof two lines.
st[j][i] = min of the 2j elements starting at i. Query [l, r]: take k = ⌊ log2 (r - l + 1) ⌋ and answer min(st[k][l], st[k][r - 2k + 1]) — two overlapping blocks.
vector<int> lg(n + 1);
for (int i = 2; i <= n; i++) lg[i] = lg[i / 2] + 1;
int K = lg[n] + 1;
vector<vector<int>> st(K, vector<int>(n));
st[0] = a;
for (int j = 1; j < K; j++)
for (int i = 0; i + (1 << j) <= n; i++)
st[j][i] = min(st[j-1][i], st[j-1][i + (1 << (j-1))]);
auto ask = [&](int l, int r) { // inclusive
int k = lg[r - l + 1];
return min(st[k][l], st[k][r - (1 << k) + 1]);
};min is idempotent (min(x,x) = min(x)) and associative, so counting an element twice changes nothing; and 2k ≤ r-l+1 < 2k+1 guarantees the two blocks cover the whole interval.
Which operations work, and which do not
- work:
min,max,gcd, bitwiseand, bitwiseor(all idempotent), - do not work:
+(double counting),xor(cancels!), parity of a count — for these use prefix sums or a segment tree, - count of minimum / "leftmost minimum": works with a custom combine that keeps
(value, tie-break); the idempotence requirement is on the whole pair, so store which side wins consistently.
Build O(n log n) time and memory: at n = 106 that is 2 × 107 ints = 80 MB — plan for it or switch to a segment tree (O(n) build, O(log n) query) or to the Cartesian-tree + Euler ±1-RMQ linear solution (LCA via Range Minimum Query) when n is huge and queries are many.
#Beyond min: three standard upgrades
Prefix sums: O(n) memory, O(1) query — strictly better than a sparse table, because + is invertible. The general rule: invertible → prefix sums; idempotent → sparse table; neither → segment tree.
"First position to the right with value > a[i]" is not an aggregate over a set but a search. Precompute nxt[i] with a monotone stack (O(n)), then binary lift over nxt for "the k-th next greater", O(log n) per query. The stack handles the structure, lifting handles the repetition — a pattern that recurs in Functional and Permutation Graphs and LCA by Binary Lifting.
st[j][i] with combine = "hash of the concatenation" and non-overlapping queries gives you substring hashes at fixed length 2j in O(1) — the standard building block for LCP queries and "count distinct rotations" problems.