Sparse Table: O(1) Range Queries

Цели урока

• Understand when a Sparse Table beats a Segment Tree
• Master the idea of overlapping powers of two
• Implement the table build
• Answer queries in O(1)
• Apply it to LCA

Предварительные знания

• Segment Tree

• Segment Tree

You have a billion historical stock quotes. A user fires off a million queries for 'lowest price over period X-Y'. A Segment Tree gives O(log n) per query. A Sparse Table gives O(1). At a million queries, that is a 20x difference.

• LCA in trees (expressions, DOM, genealogy)
• Range Minimum Query on static arrays
• Suffix arrays (LCP queries)
• Historical data that never changes

Bender and Farach-Colton's RMQ-LCA equivalence

The sparse table itself is older folklore, but its modern role was cemented by Michael Bender and Martin Farach-Colton in their 2000 paper 'The LCA Problem Revisited'. They laid out clearly how the Lowest Common Ancestor problem on a tree reduces to a Range Minimum Query on the depths recorded during an Euler tour, and back again. The sparse table is the natural tool for the static RMQ side of this reduction: it precomputes the answer for every interval whose length is a power of two in O(n log n) time, then answers any range query in O(1) by combining two overlapping power-of-two intervals. This works precisely because operations like minimum, maximum, and gcd are idempotent, so the overlap counts no element in a harmful way. The clean separation between an O(n log n) preprocessing step and O(1) queries made the sparse table a standard building block for static range problems.

The Problem: Fast Queries Without Updates

A **Segment Tree** answers in O(log n), but what if the data **never changes**?

**Sparse Table** trades away updates for **O(1) queries**. Perfect for static data.

**Applications:**

• Lowest Common Ancestor (LCA) in trees
• Range Minimum Query (RMQ) on static arrays
• Suffix arrays and LCP
• Market data - historical min/max over a period

The Idea: Overlapping Powers of Two

**Key observation:** any range can be covered by **two** ranges whose length is a power of 2.

**Overlap is fine.** For min/max/gcd, counting an element twice does not change the result: min(a, a) = a.

Such operations are called **idempotent**: applying them again to the same element does not change the result.

**Sum is NOT idempotent.** Overlap would count elements twice. For sums, use a Segment Tree.

Building the Table

A **Sparse Table** is a 2D array: `st[i][j]` = the result of the operation on the range `[i, i + 2^j - 1]`.

**Build complexity:** O(n log n) time and O(n log n) memory.

Querying in O(1)

For a query `[l, r]`, find the largest power of 2 that fits in the range.

**Why O(1)?** Precomputing log gives the power in O(1). Two table lookups are O(1) too.

Application: LCA in O(1)

**LCA (Lowest Common Ancestor)** is an important tree problem. A Sparse Table solves it in O(1).

**Algorithm (Euler Tour + RMQ):**

1. Euler Tour: traverse the tree, recording each node on entry and exit
2. For each node, store its first occurrence in the tour
3. LCA(u, v) = the node with minimum depth between first[u] and first[v]
4. This is an RMQ problem → Sparse Table!

**Result:** O(n) Euler Tour + O(n log n) Sparse Table = O(n log n) preprocessing, O(1) LCA.

Sparse Table

• For idempotent operations (min, max, gcd)
• Preprocessing: O(n log n), Query: O(1)
• Does not support updates!
• Two overlapping ranges cover any interval
• Used for O(1) LCA

Range query structures

Each structure has its own trade-offs.

• Segment Tree — O(log n) with updates
• Fenwick Tree — Prefix sums

Связанные уроки

• ds-19-segment-tree — Segment Tree also answers range queries but allows updates
• ds-21-fenwick-tree — Fenwick Tree gives O(log n) updatable range sums
• alg-19-divide-conquer — Precomputed power-of-two blocks come from divide and conquer
• alg-35-bit-manipulation — Query decomposition uses powers of two and log indexing
• ds-01-arrays — The table is just a 2D array of precomputed answers
• alg-36-prefix-sum