Sparse Tables

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.

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