SpecializedSpecialized Structures
Sparse Table (range minimum)
A precomputed table of answers over power-of-two-length blocks that answers idempotent range queries (min, max, gcd) in O(1) after O(n log n) build, for static arrays.
7
0
2
1
3
2
0
3
5
4
10
5
3
6
12
7
18
8
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
|---|---|---|---|---|---|---|---|---|---|
| k=0 (len 1) | · | · | · | · | · | · | · | · | · |
| k=1 (len 2) | · | · | · | · | · | · | · | · | · |
| k=2 (len 4) | · | · | · | · | · | · | · | · | · |
| k=3 (len 8) | · | · | · | · | · | · | · | · | · |
1/26Build a sparse table for range-minimum over 9 values. Row k, column i will hold min(a[i .. i + 2^k − 1]) — every power-of-two-length block.
Cell being computed / answerInputs (two halves / two blocks)Computed
PseudocodeLearn Sparse Table →
1sp[0][i] = a[i]2for k in 1..log n: for i while i + 2^k <= n:3 sp[k][i] = min(sp[k-1][i], sp[k-1][i + 2^(k-1)])4query(l, r): k = floor(log2(r - l + 1))5 return min(sp[k][l], sp[k][r - 2^k + 1]) # two overlapping blocksVariables
n9
K4
Complexity
access O(1)
search —
insert —
delete —
Speed