Sparse table & RMQ
Scenario
You are building an algorithm to find the Lowest Common Ancestor (LCA) of nodes in a massive, static DOM tree or organizational hierarchy with 10^6 nodes. You must answer 10^7 queries for the minimum element in a given range. A Segment Tree takes O(log N) per query, which will result in 200 million operations—too slow.
How can you achieve true O(1) instant responses for Range Minimum Queries?
Why it exists
While Segment Trees offer O(log N) queries, in algorithmic problem solving and low-latency systems, processing millions of RMQ queries with an O(log N) overhead can still cause timeouts. Unlike Segment Trees, which allow dynamic updates in O(log N) time, Sparse Tables are strictly static. They trade O(N log N) memory/precomputation time for the absolute theoretical limit of O(1) query time.
Mental model
If you want to find the minimum across a 12-foot span, you don't need a 12-foot ruler. You can take two 8-foot rulers, lay them down so they overlap in the middle, and just ask: 'What is the minimum of the left ruler, and the minimum of the right ruler?' Because minimums can overlap without altering the answer, two overlapping segments can cover any arbitrary range.
A Sparse Table is a static data structure used to answer Range Minimum Queries (RMQ) in true `O(1)` time after `O(N log N)` precomputation. It exploits the fact that idempotent operations (like `min` or `max`) allow overlapping ranges to be queried instantly using powers of 2.
Explanation
**1. The Precomputation (O(N log N)):**
We create a 2D array `st[N][K]`, where `st[i][j]` stores the minimum of a subsegment starting at index `i` with length `2^j`.
We build this table dynamically: a segment of length `2^j` is just two segments of length `2^{j-1}` glued together.
`st[i][j] = min(st[i][j-1], st[i + (1 << (j-1))][j-1])`.
Because `K` only goes up to `log N` (about 20 for 1,000,000), building the table takes `O(N log N)` time and memory.
**2. The O(1) Query:**
To answer a query for the range `[L, R]`, we calculate the length of the range: `len = R - L + 1`.
We find the largest power of 2 that fits inside `len`. Let's call its exponent `j`. (We can find `j` instantly using `__builtin_clz` or `log2`).
The range `[L, R]` can be completely covered by two overlapping segments of length `2^j`: one starting at `L`, and one ending at `R`.
**3. The Overlap Trick:**
We simply take the minimum of those two precomputed segments:
`ans = min(st[L][j], st[R - (1 << j) + 1][j])`.
Because it's a `min` operation, the overlapping elements in the middle are evaluated twice, but `min(X, X) == X`, so it doesn't corrupt the answer. This returns the exact minimum in exactly one O(1) operation.
Code examples
Sparse Table RMQ
const int K = 20; // log2(N)
int st[1000000][K]; // st[i][j] covers length 2^j
void build(int N, const vector<int>& a) {
for (int i = 0; i < N; i++) st[i][0] = a[i];
for (int j = 1; j < K; j++) {
for (int i = 0; i + (1 << j) <= N; i++) {
st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
}
}
int query(int L, int R) {
// Find the largest power of 2 that fits in the range
int len = R - L + 1;
// __builtin_clz counts leading zeros of a 32-bit int.
// 31 - clz yields the floor of log2(len)
int j = 31 - __builtin_clz(len);
return min(st[L][j], st[R - (1 << j) + 1][j]);
}Once `build()` is called, `query()` runs in absolute O(1) time. This is the fastest possible way to answer RMQs in C++.
Key points
- Idempotent operations only: The O(1) query relies on overlapping ranges. It only works for Min, Max, and GCD.
- Strictly Static: If the underlying array changes, you cannot use a Sparse Table.
Common mistakes
- Using Sparse Table for Sum Queries: Sparse Tables only offer O(1) queries for *idempotent* operations—operations where overlapping elements don't change the result (like `min`, `max`, or `gcd`). If you use the overlap trick for a Range Sum Query, the elements in the overlapped middle section will be added twice, ruining the sum.
Recall questions
- What is the time complexity to build a Sparse Table, and what is the time complexity to query it for RMQ?
- Why does the Sparse Table O(1) overlap trick work for Minimum queries but not for Sum queries?
- What does `st[i][j]` represent in a Sparse Table?
Questions & answers
You deploy a Sparse Table to handle 10^7 Range Minimum Queries. An hour later, the product manager asks you to support a feature where the values in the array can be updated dynamically. What must you change?
You must completely scrap the Sparse Table and replace it with a Segment Tree. Sparse Tables are strictly static. Updating a single element in a Sparse Table requires recalculating up to `O(N)` states, destroying its performance.
Approach: Recognize the limitation of static precomputation tables versus dynamic tree structures.
A developer implements a Sparse Table for Range Minimum Query. They test it heavily on an array of length 15 and it works perfectly. In production on an array of length 200,000, it occasionally segfaults. What likely happened?
They likely hardcoded the column dimension `K` (the max power of 2) to a small number like 4 (since 2^4 = 16 > 15). For N = 200,000, `K` must be at least 18 (`log2(200000)`). Querying lengths longer than 16 caused out-of-bounds array accesses.
Approach: Understand how the logarithmic depth constant `K` scales with `N`.
Continue learning
Previous: Bit manipulation tricks for CP