A sparse table is a static lookup structure: it precomputes the answer for every interval whose length is a power of two, then answers any query in O(1) by combining two precomputed intervals that overlap and jointly cover the query range.

The Table

st[k][i] stores the aggregate over [i, i + 2^k − 1]. Row 0 is the array itself; each higher row is built from the previous one:

st[0][i] = arr[i]
st[k][i] = min(st[k−1][i], st[k−1][i + 2^(k−1)])

Building row k takes O(n), and there are O(log n) rows — O(n log n) total preprocessing.

The O(1) Query

For a range [l, r] of length len = r − l + 1:

k = floor(log2(len))
answer = min(st[k][l], st[k][r − 2^k + 1])

The two intervals [l, l + 2^k − 1] and [r − 2^k + 1, r] both have length 2^k ≤ len, overlap (because 2^k > len/2), and together cover every index of [l, r]. Overlap is fine for min, max, and gcd — taking the min twice changes nothing. This idempotence is exactly why two lookups suffice.

Worked Example: Why Overlap Is Fine

Take arr = [5, 2, 9, 1, 7, 3, 8, 4] and query the minimum of [2, 6] (indices 2…6 → values 9, 1, 7, 3, 8).

• len = 5, so k = floor(log₂ 5) = 2, and 2^k = 4.
• Interval A = [2, 2+4−1] = [2, 5] → min = min(9, 1, 7, 3) = 1.
• Interval B = [6−4+1, 6] = [3, 6] → min = min(1, 7, 3, 8) = 1.
• answer = min(A, B) = 1. ✓

The two power-of-two windows overlap on indices 3, 4, 5 — the value 1 is counted twice, but for min that’s harmless. Now contrast: if the aggregate were sum, the two lookups would give 1+7+3 = 11 and 7+3+8 = 18, and summing those double-counts the overlap (11 + 18 = 29 ≠ true sum 28). That is precisely the idempotence boundary: min, max, and gcd are idempotent (applying twice returns the same value), while sum, product, and xor are not. Idempotence is the reason two overlapping intervals can stand in for one exact interval — and the reason sparse tables can’t answer sum queries.

Where It Fits

The sparse table wins when the data is static and there are many queries — especially LCA via Euler-tour RMQ. But it cannot handle updates, and sum queries are not O(1) here because sums are not idempotent.

Practice Trajectory

1. Build the table for a small array and verify every row by hand.
2. Implement query(l, r) with Math.floor(Math.log2(len)) and confirm O(1) results on random data against a brute-force scan.
3. Switch the aggregate to max, then to gcd — nothing else changes.
4. Use it to answer LCA queries: Euler tour the tree, then RMQ on depths.
5. Solve: static RMQ and static GCD-range problems.

When It’s the Right Tool