Sparse Table

A sparse table answers static range queries on an immutable array. Most associative folds take O(log n) per query; for range minimum / maximum (idempotent ops) it answers in O(1).

Drawback: if any A[i] changes, rebuild the whole structure (O(n log n)).

This lesson follows CP-Algorithms — Sparse Table.

Related: Binary Search, MEX.

Intuition

Any positive length decomposes into ≤ ⌈log₂ length⌉ decreasing powers of two — same idea as binary digits. So any interval is a union of O(log n) dyadic blocks.

Precompute the answer for every range of length 2^i. Answer a query by combining a few (or two overlapping) precomputed blocks.

Precomputation

Store st[i][j] = answer on [j, j + 2^i − 1]. Layout (K+1) × MAXN with K ≥ ⌊log₂ MAXN⌋ (often K = 25). Put the MAXN dimension second for cache-friendly scans.

// st[0][j] = A[j]
for (int i = 1; i <= K; i++)
    for (int j = 0; j + (1 << i) <= N; j++)
        st[i][j] = f(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);

Each length-2^i block is the fold of two halves of length 2^{i−1}. Build time O(N log N).

f is + for sums, min for RMQ, etc.

Range sum — O(log n)

Disjoint cover: from the largest 2^i ≤ remaining length, add st[i][L] and advance L.

long long sum = 0;
for (int i = K; i >= 0; i--) {
    if ((1 << i) <= R - L + 1) {
        sum += st[i][L];
        L += 1 << i;
    }
}

Range minimum — O(1)

min is idempotent: processing an index twice does not change the answer. Cover [L,R] with two overlapping blocks of length 2^i where i = ⌊log₂(R−L+1)⌋:

min( st[i][L], st[i][R − 2^i + 1] )

Example: [1,6] → [1,4] ∪ [3,6].

Precompute lg[x] = ⌊log₂ x⌋:

lg[1] = 0;
for (int i = 2; i <= MAXN; i++)
    lg[i] = lg[i / 2] + 1;

int i = lg[R - L + 1];
int minimum = min(st[i][L], st[i][R - (1 << i) + 1]);

(__builtin_clzll / std::bit_width also work; a lg[] array can be slower from cache misses.)

This O(1) trick needs an idempotent semigroup (min, max, gcd, AND, OR, …). Sums / products need the disjoint O(log n) cover (or a Disjoint Sparse Table / Sqrt Tree for O(1) associative queries).

🧪 Sparse table RMQ + range sum

Check: sparse table

Quiz

Sparse table

1 / 4

Sparse tables assume the array is…

Pick an answer to see if you are right.

Practice drills

Activity: Floor log2

Input: positive integer x. Print ⌊log₂ x⌋ (largest i with 2^i ≤ x).

Practice problems

From CP-Algorithms:

• SPOJ RMQSQ, THRBL
• CSES Static Range Minimum Queries
• Codeforces 475D — CGCDSSQ
• Codechef MSTICK, SEAD; more RMQ / GCD-range tasks listed in the article

Cheat sheet

Topic	Takeaway
st[i][j]	Fold on [j, j+2^i−1]
Build	O(n log n) DP from halves
Sum / assoc.	Disjoint peel O(log n)
Min / max / gcd	Two overlaps O(1)
Updates	Rebuild everything
Related	Disjoint sparse table, Sqrt tree