Sparse Table

This is an extension topic beyond most interviews; it pays off in OA problems that ask many range-minimum, range-maximum or range-gcd questions about an array that never changes.

Intuition

A sparse table precomputes answers for every range whose length is a power of two:

st[j][i] = op(a[i], a[i+1], ..., a[i + 2^j - 1])

Level 0 is the array itself, and each level is built from the one below by joining two halves: st[j][i] = op(st[j-1][i], st[j-1][i + 2^(j-1)]). There are about log2(n) levels of at most n entries, so building takes O(n log n) time and space.

To answer a query on [l, r], let k be the largest power of two with 2^k <= r - l + 1. The block starting at l and the block ending at r, both of length 2^k, together cover the whole range. They may overlap in the middle, but for the minimum that does not matter: min(x, x) = x. So each query is a single op of two table entries, O(1).

That last step is the whole trick, and it explains which operations work. The operation must be associative and idempotent (op(x, x) = x): min, max, gcd, bitwise AND and OR. Sum, product and XOR are not idempotent; overlapping blocks would count the middle twice. For static sums use a prefix-sum array instead (a sparse table can do them by splitting into disjoint power-of-two blocks, but in O(log n) per query, so there is no reason to).

The structure is static. Changing one element can affect O(n) entries per level, so with updates you want a segment tree.

Compute k with integer operations: in Python (r - l + 1).bit_length() - 1; in C++ __lg(len) or a precomputed table lg[i] = lg[i // 2] + 1. Floating-point log2 can round the wrong way.

When to use it in interviews / OAs

• Many range min/max queries on fixed data: 10^5 to 10^6 queries where even O(log n) per query is uncomfortable, especially in Python.
• Range gcd / AND / OR: these values change at most O(log W) times as a range grows from a fixed start (W is the maximum value), so "count subarrays whose gcd (or AND) equals k" becomes binary search over ends with O(1) range checks.
• Binary search on the answer with range checks: "longest subarray with max - min <= limit" and similar, when the checker needs fast range extremes. (A monotonic deque often solves the plain sliding version in O(n).)
• Building block for other algorithms: the lowest common ancestor in O(1) per query via an Euler tour plus a sparse table, and longest-common-prefix queries over a suffix array (both beyond typical interviews).

The doubling idea is the same one behind binary lifting for tree ancestors: precompute answers for steps of length 2^j, then compose a few of them.

Template

A generic table for any idempotent operation:

from math import gcd
from typing import Callable


class SparseTable:
    # Static range queries for idempotent ops (min, max, gcd, &, |): O(n log n) build, O(1) query.
    def __init__(self, a: list[int], op: Callable[[int, int], int] = min) -> None:
        self.op = op
        self.st = [list(a)]  # st[j][i] = op over a[i .. i + 2^j - 1]
        j = 1
        while (1 << j) <= len(a):
            prev, half = self.st[-1], 1 << (j - 1)
            self.st.append([op(prev[i], prev[i + half]) for i in range(len(a) - (1 << j) + 1)])
            j += 1

    def query(self, l: int, r: int) -> int:
        # op over a[l..r], inclusive, l <= r.
        k = (r - l + 1).bit_length() - 1  # Largest power of two that fits in the range.
        return self.op(self.st[k][l], self.st[k][r - (1 << k) + 1])  # Two blocks that may overlap.


a = [5, 2, 8, 1, 9, 3]
mn, mx = SparseTable(a, min), SparseTable(a, max)
assert mn.query(0, 2) == 2 and mn.query(2, 5) == 1 and mx.query(3, 5) == 9
assert SparseTable([12, 18, 24, 9], gcd).query(0, 2) == 6

An application where O(1) queries matter: counting subarrays whose gcd is exactly k. For a fixed start, the gcd only decreases (or stays) as the end moves right, so the ends with gcd exactly k form one contiguous block; two binary searches find its boundaries.

def count_subarrays_with_gcd(nums: list[int], k: int) -> int:
    # For a fixed start l, gcd(nums[l..r]) never increases as r grows,
    # so the ends where it equals k form one contiguous block.
    n, st = len(nums), SparseTable(nums, gcd)

    def first_end(l: int, limit: int) -> int:  # Smallest r >= l with gcd(l..r) < limit, else n.
        lo, hi = l, n
        while lo < hi:
            mid = (lo + hi) // 2
            if st.query(l, mid) < limit:
                hi = mid
            else:
                lo = mid + 1
        return lo

    return sum(first_end(l, k) - first_end(l, k + 1) for l in range(n))


assert count_subarrays_with_gcd([9, 3, 1, 2, 6, 3], 3) == 4
assert count_subarrays_with_gcd([4], 7) == 0

Complexity

Step	Time	Space
build	O(n log n)	O(n log n)
query (min, max, AND, OR)	O(1)
query (gcd)	O(log W) for the single gcd call
update	not supported (rebuild O(n log n))

Memory is the real limit in Python: for n = 10^6 the table holds about 2 * 10^7 integers spread over 20 lists, roughly 160 MB of list slots alone, more than most OA memory limits. For n around 10^5 it is comfortable.

Common pitfalls

• Using it for sums or XOR. Overlapping blocks double count; use prefix sums (or prefix XOR).
• Off-by-one in the second block. It starts at r - 2^k + 1, not r - 2^k.
• Mixing inclusive and exclusive ends. The template above uses inclusive [l, r]; convert carefully if the rest of your code uses half-open ranges.
• Floating-point logs. Use bit_length or a precomputed integer table.
• Forgetting it is static. If the problem has updates, switch to a segment tree; rebuilding after every update is O(n log n).
• Memory blowups. Each level is a full list; for very large n consider a segment tree or the sqrt-style alternatives.

Interview variations

• Static range minimum / maximum query at scale.
• Count subarrays with gcd equal to k or bitwise AND equal to k, and "smallest subarray with gcd 1".
• Longest subarray with max - min within a limit via binary search on the length plus O(1) range checks.
• Lowest common ancestor in O(1) after an Euler tour (see the tree/graph material).
• Range queries on a frozen snapshot inside a larger simulation, where the data is fixed between rebuilds.