Sparse Table
A static range-query structure that turns immutable RMQ-style queries into O(1) lookups.
Sparse Table
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
The sparse table is the cleanest tool for static range queries on an immutable array. It preprocesses answers on power-of-two intervals and then recombines those precomputed pieces during queries.
Its best-known use is range minimum query in \(O(1)\) time, but the real lesson is more general: if the array never changes, it is often worth paying more preprocessing to make every query almost free.
When to Use It
Use it when:
the array is static,
you have many queries,
the operation is associative,
and ideally idempotent if you want the \(O(1)\) overlap trick.
Range minimum, maximum, and gcd are the classic fits. Range sum does not get the same \(O(1)\) trick because overlapping intervals would double-count values.
Core Idea
Precompute answers for every interval of length \(2^k\): \[ \texttt{st[k][i]} = \text{answer on } [i, i + 2^k - 1]. \]
Then a larger interval can be described using powers of two. For example, length \(13\) can be built from \(8 + 4 + 1\), which already suggests an \(O(\log n)\) query method.
For idempotent operations such as \(\min\), there is an even better trick: any interval \([l, r]\) can be covered by two overlapping blocks of equal length \(2^k\), where \(k = \lfloor \log_2(r - l + 1) \rfloor\): \[ [l, l + 2^k - 1] \quad\text{and}\quad [r - 2^k + 1, r]. \]
Key Insight
The phrase I keep in mind is: static data lets you precompute aggressively.
The second key fact is the idempotent overlap trick:
for \(\min\), \(\max\), or \(\gcd\), combining two overlapping blocks is safe,
for \(\sum\), the overlap would count some positions twice, so that shortcut breaks.
That is why sparse tables feel magical for RMQ but much less magical for sums.
Operations / Main Technique
The two main phases are:
build: fill level \(0\) with the array, then build larger powers of two from smaller ones,
query: either decompose the interval into powers of two, or for idempotent operations use the two-block trick.
Worked example.
To answer \(\min\) on a length-\(13\) interval, take \(k = 3\), so the block size is \(8\). Then query the left block of length \(8\) and the right block of length \(8\), and take the minimum of those two answers. The overlap is harmless because taking \(\min\) twice does not change the result.
Correctness Intuition
Each table entry is correct by construction: it is built from two correct halves of equal length.
For the \(O(1)\) RMQ trick, the queried interval is fully covered by the two chosen blocks. Because the operation is idempotent, elements that appear in both blocks do not cause trouble: \[ \min(x, x) = x, \qquad \gcd(x, x) = x. \]
So combining the two block answers gives the same result as combining the entire interval directly.
Complexity Analysis
preprocessing: \(O(n \log n)\),
RMQ / idempotent query: \(O(1)\),
associative but non-idempotent query by decomposition: \(O(\log n)\),
memory: \(O(n \log n)\).
That memory cost is the main reason not to use sparse tables casually on very large dynamic data.
Implementation
The reference code implements the standard RMQ version:
precomputed floor logs,
table levels by powers of two,
\(O(1)\) range minimum query.
I like this as a baseline because the min version makes the idempotent requirement completely explicit.
Common Pitfalls
Using sparse tables on arrays that change between queries.
Forgetting that the \(O(1)\) query trick assumes idempotence.
Getting the right block start wrong in \(\texttt{st[k][r - (1 << k) + 1]}\).
Building too many columns or using the wrong maximum log.
Choosing a sparse table when a prefix sum or Fenwick tree would be simpler and lighter.
Variants / Extensions
sparse table for range max or range gcd,
sparse table over any associative operation with \(O(\log n)\) queries,
disjoint sparse table for \(O(1)\) queries on more general associative operations,
RMQ as a subroutine for LCA after Euler tour reduction.
The disjoint sparse table is worth knowing exists, even if the ordinary sparse table is still the one I use most.
Practice Problems
Static range minimum or gcd queries.
LCA reductions that rely on RMQ over an Euler tour.
Problems with many queries and no updates, where a segment tree would be unnecessary.
References
Code
Contest-ready reference implementation for the idea explained above.
struct SparseTable {
int n, lg;
vector<int> log2_floor;
vector<vector<int>> st;
SparseTable() : n(0), lg(0) {}
explicit SparseTable(const vector<int>& values) { build(values); }
void build(const vector<int>& values) {
n = (int)values.size();
log2_floor.assign(n + 1, 0);
for (int i = 2; i <= n; ++i) {
log2_floor[i] = log2_floor[i >> 1] + 1;
}
lg = log2_floor[n];
st.assign(lg + 1, vector<int>(n));
st[0] = values;
for (int k = 1; k <= lg; ++k) {
int len = 1 << k;
for (int i = 0; i + len <= n; ++i) {
st[k][i] = min(st[k - 1][i], st[k - 1][i + (len >> 1)]);
}
}
}
int range_min(int left, int right) const {
int k = log2_floor[right - left + 1];
return min(st[k][left], st[k][right - (1 << k) + 1]);
}
};
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.