Range Minimum Query
st[i][j] = min of the 2^j elements starting at index i. For query min(L,R): find the largest k where 2^k ≤ R−L+1. Answer = min(st[L][k], st[R−2^k+1][k]). The two ranges overlap but that's fine for min/max.
How It Works
A sparse table precomputes st[i][j], the minimum of the 2^j elements starting at index i, using doubling: each entry merges two half-length entries, st[i][j] = min(st[i][j-1], st[i + 2^(j-1)][j-1]). The table has O(n log n) entries, each filled in O(1), giving an O(n log n) build.
Queries exploit that min is idempotent — counting an element twice changes nothing. For range [L, R], take k as the largest power such that 2^k fits in the range length; then min(st[L][k], st[R - 2^k + 1][k]) covers the range with two possibly overlapping blocks, answering in O(1). No comparison-based structure with updates matches that query bound: segment trees pay O(log n) per query but allow modification, while the sparse table is strictly static. The same machinery serves max, gcd, and bitwise AND/OR, and powers O(1) LCA queries via Euler tours.
Step-by-Step Visualization
Code
class SparseTable {
int[][] st;
SparseTable(int[] arr) {
int n = arr.length;
int LOG = (int)(Math.log(n) / Math.log(2)) + 1;
st = new int[n][LOG];
for (int i = 0; i < n; i++) st[i][0] = arr[i];
for (int j = 1; j < LOG; j++)
for (int i = 0; i + (1 << j) - 1 < n; i++)
st[i][j] = Math.min(st[i][j-1], st[i + (1<<(j-1))][j-1]);
}
int query(int l, int r) {
int j = (int)(Math.log(r - l + 1) / Math.log(2));
return Math.min(st[l][j], st[r - (1<<j) + 1][j]);
}
}Tips & Gotchas
Practice Problems
- 1Range Minimum Query
- 2Sliding Window Maximum
- 3Longest Common Prefix of Substrings
About the Sparse Table Pattern
Precompute answers for every power-of-2 sized range. Then any query can be answered by overlapping at most two precomputed ranges. O(n log n) build, O(1) query — but the array must be static (no updates).
If you only need prefix queries with point updates, use a BIT (simpler). If you need arbitrary range queries + range updates, use a segment tree with lazy propagation. Sparse table is O(1) query but static.
Common Range Structures Interview Problems
- Range Sum Query - Mutable
- Count of Smaller Numbers After Self
- Range Minimum Query
- Longest Increasing Subsequence (BIT approach)
Frequently Asked Questions
Why can sparse table queries overlap blocks when segment trees cannot?
Idempotent operations like min and max give the same answer no matter how many times an element is counted, so two overlapping power-of-two blocks covering [L, R] are safe. Sum is not idempotent — the overlap would be double-counted — which is why sparse tables answer range sums only via a slower O(log n) disjoint decomposition.
Sparse table or segment tree for range minimum — how do I choose?
If the array never changes, the sparse table wins: O(1) queries after O(n log n) preprocessing, with simpler code. Any updates at all favor the segment tree, since a single element change invalidates O(n log n) sparse table entries and rebuilding costs as much as construction.
How is the power k for a query computed quickly?
k = floor(log2(R - L + 1)), and the standard trick is precomputing a log table where log[x] = log[x/2] + 1 in O(n), making each query lookup O(1). Calling floating-point log2 per query risks both slowdown and precision bugs near powers of two.