Sparse Tables: O(1) Range Minimum Queries Explained

Range minimum query (RMQ) problems show up in coding interviews and contests: given a fixed array, answer many "minimum on [l, r]" questions. If the array never changes, a sparse table answers each query in constant time.

The table

st[j][i] stores the minimum of the window starting at i with length 2^j. Row 0 is the array itself; each next row combines two halves of the previous one.

def build(a):
    n = len(a); LOG = n.bit_length()
    st = [a[:]]
    for j in range(1, LOG):
        prev, half = st[-1], 1 << (j - 1)
        st.append([min(prev[i], prev[i + half])
                   for i in range(n - (1 << j) + 1)])
    return st

def query(st, l, r):            # inclusive
    j = (r - l + 1).bit_length() - 1
    return min(st[j][l], st[j][r - (1 << j) + 1])

Why the query is O(1)

Pick the largest power of two that fits in the range, then cover [l, r] with two windows of that length: one starting at l, one ending at r. They overlap, but that's fine because min is idempotent: counting an element twice doesn't change the answer.

The idempotency catch

That overlap trick works for min, max, gcd and bitwise and/or. It does not work for sums or products. For those, you'd decompose the range into O(log n) non-overlapping power-of-two blocks, at which point a prefix sum or Fenwick tree is simpler.

Sparse table vs segment tree

• Sparse table: O(n log n) build and memory, O(1) query, no updates.
• Segment tree: O(n) memory, O(log n) query, supports point and range updates.

Say this explicitly: "The array is static and there are many queries, so I'll use a sparse table; if updates were allowed I'd switch to a segment tree."

Where it appears

• LCA in O(1) via an Euler tour plus RMQ.
• Longest common prefix queries on a suffix array's LCP array.
• Sliding-window problems with arbitrary windows rather than fixed-size ones.

Disclosure: written by the team behind linkjob.ai, a real-time interview assistant. Use these notes freely for practice.