vault

Sparse Table

15 min read

Sparse Table

A sparse table is a static data structure that answers a range query (min, max, gcd, lcm, bitwise AND/OR — any idempotent associative aggregate) over a fixed array in O(1) time per query after O(n log n) preprocessing. It does not support updates: changing a single element invalidates much of the table. The structure is essentially a 2-D dynamic-programming table indexed by (power-of-two length, starting position). Range queries exploit two ideas: every range [l, r] can be covered by two overlapping intervals of length 2^k where k = ⌊log₂(r − l + 1)⌋, and idempotent operations (where combine(x, x) = x) tolerate this overlap. For non-idempotent operations like sum or XOR, sparse tables can still be used but with O(log n) per query and a different decomposition (only ranges of exact power-of-two length are stored). Sparse tables are the cornerstone of the Bender-Farach-Colton 2000 reduction from Lowest Common Ancestor to Range Minimum Query, which is the standard O(n)-preprocessing, O(1)-query LCA algorithm.

1. Intuition — A Power-of-Two Lookup Table

Suppose you want to answer “minimum of A[l..r]” queries quickly on a fixed array. The naive scan is O(n) per query. The Segment Tree gives O(log n) per query and supports updates. But if there are no updates and you have time to preprocess, you can do better — O(1) per query.

The trick: precompute the answer for every “power-of-two-length window” starting at every position. That is:

st[k][i] = min(A[i], A[i+1], …, A[i + 2^k - 1])

with 0 ≤ k ≤ ⌊log₂ n⌋ and 0 ≤ i ≤ n - 2^k. This is O(n log n) slots total. With this table, a query for min(A[l..r]) works as follows: let L = r - l + 1 (the length of the queried range), let k = ⌊log₂ L⌋. The two intervals [l, l + 2^k - 1] and [r - 2^k + 1, r] both have length exactly 2^k, both fit inside [l, r], and together they cover all of [l, r] (they overlap in the middle whenever 2 · 2^k > L, which is always true except when L is exactly a power of two). The answer is then:

min(A[l..r]) = min(st[k][l], st[k][r - 2^k + 1])

Two table lookups + one min. O(1).

The crucial requirement is that the operation is idempotent — combine(x, x) = x, so double-counting elements in the overlap doesn’t break the answer. min, max, gcd, lcm, bitwise AND, bitwise OR are all idempotent. Sum is not idempotent (x + x = 2x ≠ x), so the two-overlapping-windows trick double-counts the overlap. For sum, you can still use a sparse table but only for ranges whose length is exactly a power of two; arbitrary-length ranges then need O(log n) lookups (one per set bit of L), which is rarely better than a Fenwick Tree or Segment Tree.

2. Tiny Worked Example

Let A = [4, 7, 3, 1, 5, 2, 6, 8] (n = 8), aggregate = min.

Build the sparse table. Rows are indexed by k; columns by starting position i.

k = 0: window length 2^0 = 1. st[0][i] = A[i].

st[0] = [4, 7, 3, 1, 5, 2, 6, 8]

k = 1: window length 2^1 = 2. st[1][i] = min(A[i], A[i+1]).

st[1][0] = min(4, 7) = 4
st[1][1] = min(7, 3) = 3
st[1][2] = min(3, 1) = 1
st[1][3] = min(1, 5) = 1
st[1][4] = min(5, 2) = 2
st[1][5] = min(2, 6) = 2
st[1][6] = min(6, 8) = 6
st[1] = [4, 3, 1, 1, 2, 2, 6]            # last valid i is n - 2 = 6

k = 2: window length 2^2 = 4. The recurrence st[k][i] = min(st[k-1][i], st[k-1][i + 2^(k-1)]) lets us compute each entry in O(1) from the previous row.

st[2][0] = min(st[1][0], st[1][2]) = min(4, 1) = 1
st[2][1] = min(st[1][1], st[1][3]) = min(3, 1) = 1
st[2][2] = min(st[1][2], st[1][4]) = min(1, 2) = 1
st[2][3] = min(st[1][3], st[1][5]) = min(1, 2) = 1
st[2][4] = min(st[1][4], st[1][6]) = min(2, 6) = 2
st[2] = [1, 1, 1, 1, 2]                  # last valid i is n - 4 = 4

k = 3: window length 2^3 = 8. Only one entry: st[3][0] = min(st[2][0], st[2][4]) = min(1, 2) = 1.

st[3] = [1]

k stops at ⌊log₂ 8⌋ = 3.

Query min(A[1..6]). Length L = 6, k = ⌊log₂ 6⌋ = 2. Two windows of length 2^2 = 4: [1, 4] and [3, 6]. Look up st[2][1] = 1 and st[2][3] = 1. Answer: min(1, 1) = 1. Manual: min(7, 3, 1, 5, 2, 6) = 1. ✓

Query min(A[2..5]). Length L = 4, k = 2. Two windows of length 4: [2, 5] and [2, 5] (they coincide because L = 2^k exactly). Both lookups: st[2][2] = 1. Answer: 1. Manual: min(3, 1, 5, 2) = 1. ✓

Query min(A[0..2]). Length L = 3, k = ⌊log₂ 3⌋ = 1. Two windows of length 2: [0, 1] and [1, 2]. They overlap at index 1. Look up st[1][0] = 4 and st[1][1] = 3. Answer: min(4, 3) = 3. Manual: min(4, 7, 3) = 3. ✓

The overlap at index 1 (value 7) shows up in both windows — it’s compared against itself, but min(7, 7) = 7, and the surrounding minimums dominate anyway. This is the idempotency in action: even though some element is “counted twice”, the answer doesn’t change.

3. Why Idempotency Matters — Worked Counter-Example

Try the same approach for sum on A = [1, 2, 3, 4]:

st_sum[1][0] = 1 + 2 = 3, st_sum[1][1] = 2 + 3 = 5, st_sum[1][2] = 3 + 4 = 7.

Query sum(A[0..2]). Length 3, k = 1. Windows [0, 1] and [1, 2]. Lookups 3 and 5. Combine with +: 3 + 5 = 8. But sum(A[0..2]) = 1 + 2 + 3 = 6. Wrong, by exactly the duplicated A[1] = 2. The overlap got double-counted.

The fix for sum: only query ranges whose length is exactly a power of two. For arbitrary-length ranges, decompose L into its binary representation — one lookup per set bit, each at a different k, with starting positions chosen to tile [l, r] without overlap. That’s O(log n) lookups per query, no longer O(1). At that point Fenwick Tree (also O(log n) per query) is usually a better choice because it supports updates.

The general statement: an aggregate combine is idempotent iff combine(x, x) = x. Idempotent + associative aggregates: min, max, gcd, lcm, bitwise AND, bitwise OR. Non-idempotent (but still associative): +, *, XOR. The first class gets the O(1) sparse-table query; the second gets O(log n).

4. Algorithm and Pseudocode

build(A):                                # 0-indexed, n = len(A)
    K = ⌊log₂ n⌋ + 1
    st = 2-D table of size K × n        # st[k][i]
    for i in 0..n-1:
        st[0][i] = A[i]
    for k in 1..K-1:
        len_k = 2^k
        for i in 0..n - len_k:
            st[k][i] = min(st[k-1][i], st[k-1][i + 2^(k-1)])
    precompute log_floor[1..n]           # log_floor[L] = ⌊log₂ L⌋

query(l, r):                             # 0-indexed, inclusive
    L = r - l + 1
    k = log_floor[L]
    return min(st[k][l], st[k][r - 2^k + 1])

The log_floor precomputation is the standard speedup that makes the query a true O(1): computing ⌊log₂ L⌋ from scratch via int(math.log2(L)) is conceptually O(1) but in practice has constant-factor overhead (and floating-point edge cases at powers of 2). The recurrence log_floor[L] = log_floor[L / 2] + 1 (with log_floor[1] = 0) precomputes all values in O(n) and lets the query be a single array lookup.

5. Python Implementation

import math
 
class SparseTable:
    """Static O(1)-query sparse table for an idempotent aggregate.
    Default aggregate: min. Pass `op=max` etc. to switch."""
 
    def __init__(self, data, op=min):
        self.n = len(data)
        self.op = op
        # Number of layers we need: K = floor(log2(n)) + 1.
        self.K = max(1, math.floor(math.log2(self.n)) + 1) if self.n else 1
        # st[k][i] = op(data[i .. i + 2^k - 1]).
        self.st = [list(data)]
        for k in range(1, self.K):
            length = 1 << k
            prev = self.st[k - 1]
            half = 1 << (k - 1)
            row = [op(prev[i], prev[i + half]) for i in range(self.n - length + 1)]
            self.st.append(row)
        # Precompute floor(log2(L)) for L in [1..n].
        self.log_floor = [0] * (self.n + 1)
        for L in range(2, self.n + 1):
            self.log_floor[L] = self.log_floor[L // 2] + 1
 
    def query(self, l, r):
        """Return op over data[l..r], inclusive. O(1) when op is idempotent."""
        length = r - l + 1
        k = self.log_floor[length]
        return self.op(self.st[k][l], self.st[k][r - (1 << k) + 1])

Usage:

A = [4, 7, 3, 1, 5, 2, 6, 8]
st = SparseTable(A, op=min)
st.query(1, 6)        # → 1
st.query(2, 5)        # → 1
st.query(0, 2)        # → 3

For non-idempotent (e.g., sum) sparse tables, the same st table works but query must decompose length bit-by-bit and walk multiple k levels — see the cp-algorithms note for a clean implementation.

6. Complexity

Time.

  • Build: Θ(n log n). K = ⌊log₂ n⌋ + 1 rows, each row i has n - 2^k + 1 ≤ n entries each computed in O(1). Total: Σ_{k=0}^{K-1} (n - 2^k + 1) ≤ n K = O(n log n).
  • Query (idempotent op): Θ(1). One log-floor lookup + two table lookups + one combine.
  • Query (non-idempotent op): Θ(log n). One lookup per set bit in the binary representation of the length.

Space. Θ(n log n) for the st table itself. The log_floor table is O(n).

The O(1) query argument is the interview gold: be ready to explain it precisely. The argument is “any range [l, r] of length L is covered by two overlapping intervals of length 2^⌊log₂ L⌋ placed at l and at r - 2^⌊log₂ L⌋ + 1; these two intervals together include every index of [l, r]; idempotency means double-counting the overlap is harmless.” Each piece must hold for the answer to be O(1) correct.

Alternative O(n)-build, O(1)-query RMQ. Bender and Farach-Colton’s 2000 paper combines a sparse table on O(n / log n) “blocks” with a Cartesian-tree based representation of in-block patterns, achieving O(n) preprocessing total. This is mostly of theoretical interest — in practice, the plain O(n log n)-build sparse table is fast enough.

7. Variants and Use Cases

7.1 Idempotent Aggregates Beyond Min/Max

gcd is idempotent (gcd(x, x) = x) and associative; sparse tables answer range-gcd in O(1) per query, useful for problems like “find the longest subarray with gcd > 1”. lcm is idempotent in the same way, though less common. Bitwise AND and OR are idempotent and associative — sparse tables answer “AND of A[l..r]” in O(1).

7.2 Disjoint Sparse Table

A different decomposition, due to Akhmedov and others (CP folklore), achieves O(n log n) build and O(1) query for non-idempotent associative operations as well — including sum, product, and XOR. The construction is more involved (each row k partitions the array into blocks of length 2^(k+1) and stores prefix and suffix aggregates within each block). It’s a strict generalization but rarely needed in interviews — most non-idempotent range-query problems are better solved with Fenwick Tree or Segment Tree anyway because they need updates.

7.3 LCA via Euler Tour + RMQ (Bender-Farach-Colton)

A Lowest Common Ancestor query in a tree reduces to a Range Minimum Query on the Euler tour of the tree (the sequence of nodes visited by a DFS, including revisits when the recursion unwinds). The depths along the Euler tour are an array; the LCA of two nodes corresponds to the minimum-depth node in the slice between their first occurrences in the tour. Build a sparse table over the depth array → O(n log n) preprocessing, O(1) LCA queries. This is the canonical use of sparse tables in competitive programming and is covered in the Lowest Common Ancestor note.

7.4 Range Modes / Frequency

Sparse tables don’t directly answer “most frequent value in [l, r]” — that’s not idempotent and the answer doesn’t decompose by overlap. There’s a separate body of work on offline range-mode using sqrt decomposition or wavelet trees.

7.5 Production Use

Mostly absent. Real production systems with read-heavy static range queries use:

  • Min/max precomputed indexes for static numeric columns (seen in some columnar databases).
  • Bitmap indexes for OR/AND queries.
  • Skiplist + sketch structures for streaming workloads.

Sparse tables are a CP / interview tool. Their constraint of “no updates ever” rarely matches production realities.

8. Pitfalls

  1. Trying to apply it to a non-idempotent operation expecting O(1) queries. Sum, product, XOR, and “concatenate” all double-count on overlap. The naive O(1) lookup gives wrong answers; you need either a power-of-two-only restriction or the disjoint-sparse-table variant.
  2. Computing ⌊log₂ L⌋ with floats. int(math.log2(8)) returns 3 on most platforms but int(math.log2(8.0)) has been seen to return 2 on some older platforms due to floating-point representation issues. Precompute log_floor[] integer-only.
  3. Off-by-one in the second window’s start. The right window starts at r - 2^k + 1, not r - 2^k. Drawing it out: a length-2^k window at start s covers indices s, s+1, …, s + 2^k - 1. To end at index r, we need s + 2^k - 1 = r, so s = r - 2^k + 1.
  4. Allocating too few rows. K must be at least ⌊log₂ n⌋ + 1 to cover the full-length range; using K = ⌊log₂ n⌋ (without the +1) silently misses the largest windows.
  5. Trying to support updates. A point update to A[i] can invalidate up to O(log n) rows — every row k has up to 2^k entries that include index i. A “lazy update” doesn’t make sense because there’s no recursion to push down to. If you need updates, sparse table is the wrong data structure.
  6. For sum, mixing the O(log n) query with the O(1) formula. The O(1) two-window formula is only correct for idempotent ops. For sum, you must explicitly walk through the bits of the length and tile the range with disjoint power-of-two windows.
  7. Memory blowup for large n. Θ(n log n) is fine for n = 10^6 (≈ 20 million entries), but for n = 10^8 you’re at 2-3 GB just for the table. In that regime the disjoint-sparse-table variant or block-decomposed RMQ (Lowest Common Ancestor’s O(n)-build approach) wins.

9. Diagram

flowchart TD
    subgraph "Sparse table for A = [4,7,3,1,5,2,6,8] (min)"
        K0["k=0 (len 1):  4   7   3   1   5   2   6   8"]
        K1["k=1 (len 2):  4   3   1   1   2   2   6"]
        K2["k=2 (len 4):  1   1   1   1   2"]
        K3["k=3 (len 8):  1"]
        K0 --> K1
        K1 --> K2
        K2 --> K3
    end
    subgraph "Query min(A[1..6]): L=6, k=2, two windows of length 4"
        Q1["window [1,4]: st[2][1] = 1"]
        Q2["window [3,6]: st[2][3] = 1"]
        Q1 --> R["answer = min(1, 1) = 1"]
        Q2 --> R
    end

What this diagram shows. Top: the four rows of the sparse table for our example. Each row k covers windows of length 2^k; row k has n − 2^k + 1 valid starting positions. The arrows between rows indicate the dynamic-programming recurrence st[k][i] = min(st[k-1][i], st[k-1][i + 2^(k-1)]). Bottom: a worked range-min query on the range [1, 6] (length 6). The query selects k = ⌊log₂ 6⌋ = 2, then takes the minimum over the two length-4 windows [1, 4] (lookup st[2][1] = 1) and [3, 6] (lookup st[2][3] = 1). The two windows overlap at indices 3 and 4; idempotency of min makes that overlap harmless. Final answer: 1.

10. Common Interview Problems

LC #ProblemWhy Sparse Table
239Sliding Window MaximumSparse table works (O(1) query); monotonic deque is the canonical O(n) solution but ST is acceptable
1521Find a Value of a Mysterious Function Closest to TargetRange-AND queries with monotonic shrinking; sparse table elegantly handles
1851Minimum Interval to Include Each QuerySparse table on sorted-by-length intervals + offline processing
1944Number of Visible People in a QueueRange-max queries; can be solved with monotonic stack but sparse table is also clean
1235Maximum Profit in Job SchedulingRange-max DP; sparse table on the DP array
Codeforces Sereja and BracketsRange bracket-matching aggregatesMonoidal aggregate; sparse table works because the aggregate is idempotent on overlapping segments after a clever encoding

In LeetCode interviews, sparse tables show up less often than Segment Tree or Fenwick Tree because most problems involve updates. They’re more common in competitive programming (Codeforces, ICPC) where static problems abound.

The more important meta-fact: any time you’d naturally want range-min/max/gcd and the array is static, sparse table is your friend. Any time the underlying problem reduces to LCA via Euler tour, sparse table is the standard plug-in.

11. Open Questions

  • When does the disjoint-sparse-table variant beat Fenwick Tree for static range-sum queries? In theory ST gives O(1) queries vs Fenwick’s O(log n), but the constant factor and the lack of updates often makes Fenwick + offline-batching competitive.
  • Is there a clean argument for why O(1) query / O(n log n) preprocessing is the natural sweet spot — i.e., why not O(1) query with O(n) preprocessing for all idempotent operations? Bender-Farach-Colton achieves it for RMQ specifically by exploiting the special structure of Cartesian trees on the underlying array, but the technique doesn’t obviously generalize.
  • Are there idempotent aggregates beyond min, max, gcd, lcm, AND, OR that come up in practice? Multiplicative idempotents (x · x = x only for x ∈ {0, 1}) don’t give a useful structure; lattice meet/join in non-numeric algebras occasionally appear in static analysis but rarely as range queries.

12. See Also

Graph View

Backlinks