Visualize & Master
Algorithms & Data Structures
Explore classic & modern sorting algorithms, efficient searching techniques, and interactive data structure visualizations — all with real-time step-by-step animation, comparisons, swaps, and Big-O metrics.
About A sparse table is a static (immutable) structure for idempotent range queries — min, max, gcd — that answers any range query in O(1)
A sparse table is a static (immutable) structure for idempotent range queries — min, max, gcd — that answers any range query in O(1).
It precomputes st[k][i] = the aggregate over the interval [i, i + 2^k − 1] for every power-of-two length, using O(n log n) space and time.
Because overlapping is safe for min/max/gcd, two O(1) lookups cover any interval.
How It Works
Row 0 holds the array itself.
Each higher row halves the work: st[k][i] = min(st[k−1][i], st[k−1][i + 2^(k−1)]).
To answer RMQ(l, r): let k = floor(log2(r − l + 1)); the answer is min(st[k][l], st[k][r − 2^k + 1]) — two intervals of length 2^k that overlap and together cover [l, r].
The table is immutable: updates are impossible, which is why it is ideal for static data with many queries.
Time & Space Complexities
| Operation | Time | Space |
|---|---|---|
| Build | O(n log n) | O(n log n) |
| Range min/max/gcd query | O(1) | O(1) |
| Point update | Not supported (static) | — |
| Range query over idempotent ops | Yes — overlap safe | — |
| Sum queries | Not O(1) (no overlap) | — |
Best Use Cases
- RMQ with a large number of static queries (competitive programming staple)
- LCA via Euler tour + RMQ on depths
- Static min/max/gcd queries in text and sequence processing
- Any read-heavy workload where the array never changes
Worked Example
Build and answer RMQ(2,6) on [4, 2, 5, 1, 3, 6, 0, 7]
Input: array = [4, 2, 5, 1, 3, 6, 0, 7]; query min over [2,6] (0-indexed)- 1 Row 0 holds the array: [4, 2, 5, 1, 3, 6, 0, 7].
- 2 Row 1 holds mins over length-2 intervals; row 2 over length-4; row 3 over the full length-8.
- 3 The table stores st[k][i] = min over [i, i+2^k−1] for every power-of-two length.
- 4 Query min(2,6): length = 5, so k = floor(log2 5) = 2; the answer covers [2,5] and [3,6] with two overlapping 2² intervals.
- 5 min(st[2][2], st[2][3]) = min(min(5,1,3,6), min(1,3,6,0)) = min(1, 0) = 0.
- 6 Two O(1) lookups answer any range because overlapping is safe for min/max/gcd.
Pseudocode
K = floor(log2(n))
st[0] = arr
for k in 1..K:
for i with i + 2^k - 1 < n:
st[k][i] = min(st[k-1][i],
st[k-1][i + 2^(k-1)]) function query(l, r):
len = r - l + 1
k = floor(log2(len))
return min(st[k][l], st[k][r - 2^k + 1]) Build
Precompute every interval min for lengths 1, 2, 4, 8… so any range min is two O(1) lookups.