Sparse Table

How a sparse table works

Build a 2D table indexed by (k, i) where:

table[k][i] = combine of a[i], a[i+1], …, a[i + 2^k − 1]

So table[0][i] = a[i] (intervals of length 1), table[1][i] covers [i, i+1] (length 2), table[2][i] covers [i, i+3] (length 4), and so on up to k = ⌊log₂ n⌋.

Build with the doubling recurrence:

table[k][i] = combine(table[k−1][i], table[k−1][i + 2^(k−1)])

Each cell is filled in O(1) given the previous level. Total cells: ⌊log₂ n⌋ × n. Total preprocessing: O(n log n).

Constant-time query

To answer a query [l, r], find the largest k such that 2ᵏ ≤ r − l + 1 — that is k = ⌊log₂(r − l + 1)⌋. Two power-of-2-length intervals starting at l and ending at r cover [l, r] (possibly with overlap):

answer = combine(table[k][l], table[k][r − 2^k + 1])

For idempotent ⊕ (min, max, gcd, AND, OR), the overlap region contributes its values twice, but x ⊕ x = x, so the result is correct.

JavaScript implementation — range min

class SparseTableMin {
  constructor(a) {
    const n = a.length;
    const K = Math.floor(Math.log2(n)) + 1;
    this.log = new Array(n + 1).fill(0);
    for (let i = 2; i <= n; i++) this.log[i] = this.log[i >> 1] + 1;
    this.table = Array.from({ length: K }, () => new Array(n));
    for (let i = 0; i < n; i++) this.table[0][i] = a[i];
    for (let k = 1; k < K; k++) {
      for (let i = 0; i + (1 << k) <= n; i++) {
        this.table[k][i] = Math.min(
          this.table[k - 1][i],
          this.table[k - 1][i + (1 << (k - 1))]
        );
      }
    }
  }
  // Range min over [l, r] inclusive
  query(l, r) {
    const k = this.log[r - l + 1];
    return Math.min(this.table[k][l], this.table[k][r - (1 << k) + 1]);
  }
}

The precomputed log table avoids Math.log2 calls per query — saving a factor of 5-10× on hot inner loops.

Python implementation — range gcd

from math import gcd, log2

class SparseTableGcd:
    def __init__(self, a):
        n = len(a)
        K = int(log2(n)) + 1
        self.log = [0] * (n + 1)
        for i in range(2, n + 1):
            self.log[i] = self.log[i >> 1] + 1
        self.table = [[0] * n for _ in range(K)]
        for i, v in enumerate(a):
            self.table[0][i] = v
        for k in range(1, K):
            half = 1 << (k - 1)
            for i in range(n - (1 << k) + 1):
                self.table[k][i] = gcd(self.table[k - 1][i],
                                       self.table[k - 1][i + half])

    def query(self, l, r):
        k = self.log[r - l + 1]
        return gcd(self.table[k][l], self.table[k][r - (1 << k) + 1])

Sparse table vs segment tree vs prefix sums

Structure	Build	Query	Update	Operations
Sparse table	O(n log n)	O(1)	Not supported	Idempotent (min, max, gcd, AND, OR)
Disjoint sparse table	O(n log n)	O(1)	Not supported	Any associative
Segment tree	O(n)	O(log n)	O(log n)	Any associative
Fenwick tree	O(n log n)	O(log n)	O(log n)	Sum (or invertible)
Prefix sum	O(n)	O(1)	Rebuild	Sum, XOR (invertible)

For n = 10⁶ static range-min queries: sparse table builds in 10⁶ × 20 = 2 × 10⁷ ops, queries in 1 op. Segment tree builds in 10⁶ ops, queries in 20 ops. Sparse table wins on query latency by 20× when no updates are needed.

Famous applications

Range Minimum Query (RMQ)

The canonical sparse-table problem. Static array, q queries each asking the minimum value in a range. O(n log n) build + O(q) total query time. For n = 10⁵, q = 10⁵: 2 × 10⁶ build + 10⁵ query = ~2 ms wall-clock in C++.

Lowest Common Ancestor (LCA) via Euler tour

The classic LCA-via-RMQ reduction. Compute the Euler tour of a tree (length 2n − 1) and the depth of each visited node. LCA(u, v) is the node of minimum depth in the Euler-tour range between u's and v's first occurrences. RMQ on a length-2n array → O(n log n) preprocessing, O(1) per LCA query.

// Sketch: tour = [v0, v1, ...], depth = [d0, d1, ...], first[v] = index in tour
function lca(u, v) {
  let a = first[u], b = first[v];
  if (a > b) [a, b] = [b, a];
  const k = log[b - a + 1];
  // RMQ over depth[a..b], return the vertex at the minimizing position
  const i1 = sparseTable.argmin(a, b);
  return tour[i1];
}

Suffix array LCP queries

The Kasai LCP array gives the longest common prefix between adjacent suffixes in suffix-array order. To compute LCP between any two suffixes, take the minimum of LCP values over the corresponding range — a classic sparse-table application. Used in string-matching and bioinformatics for substring queries.

Path-min queries on static trees

Combine LCA with auxiliary depth-prefix arrays to answer "minimum edge weight on path (u, v)" in O(1) per query after O(n log n) preprocessing. Used in network reliability and competitive programming problems where edges are immutable.

Why sparse table matters

• Truly static RMQ. Geometric and stringology problems often build immutable data once and query many times. Sparse table is the right tool: O(1) queries, no log factor.
• LCA in trees. The reduction LCA → RMQ via Euler tour gives O(1) per query LCA — used in tree path queries, generic offline tree algorithms, and persistent-segment-tree-on-tree problems.
• Suffix array LCP. The full string toolbox (suffix arrays, LCP arrays, sparse-table RMQ) gives O(n log n + q) total time for q suffix-prefix-comparison queries — fundamental in bioinformatics and search engines.
• Hot inner loops. When millions of range-min queries dominate runtime (computational geometry sweep lines, simulation snapshots), the constant-factor advantage over segment-tree (1 vs 20 ops per query) compounds.
• Disjoint sparse table for any associative op. Generalize to sum, product, matrix multiply via the disjoint variant — same O(1) query, same O(n log n) build, no idempotency requirement.
• Plus-Minus-1 RMQ → O(1) build and query. The Euler-tour depth sequence has differences ±1 (adjacent in DFS), enabling Fischer-Heun structures: O(n) build, O(1) query — true linear-time RMQ for this special case.
• Memory cost is acceptable. O(n log n) is about 20× n for n = 10⁶ — usually fits in cache or RAM. Compare to segment tree's 4n memory.

Common misconceptions

• "Works for any operation." Only idempotent operations (x ⊕ x = x). Sum, product, average all fail because the overlap doubles their contribution.
• "Supports point updates." No — a single update potentially affects O(log n) levels at multiple positions; rebuild from scratch when data changes.
• "O(n²) memory." No — only powers of 2 are stored, giving O(n log n) total. The naive every-(l, r)-pair table would be O(n²); the sparse-table insight is that idempotency lets you skip non-power-of-2 lengths.
• "Faster than segment tree always." Build is slower (O(n log n) vs O(n)). Query is faster (O(1) vs O(log n)). Pick based on whether you need updates, and whether queries dominate build.
• "log table is optional." Computing ⌊log₂(r − l + 1)⌋ via floating-point log2 is slow and may have rounding errors. Always precompute log[i] = log[i/2] + 1 for i = 1..n.
• "Replaces Fenwick tree." No — Fenwick tree handles dynamic prefix sums in O(log n) per op. Sparse table is for static idempotent range queries — different problems.
• "Returns the index, not the value." Standard sparse table stores values. To get the index of the min/max, store (value, index) pairs and break ties by index — small extra constant.