Data Structures

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**?

StructureBuildQueryUpdate
Segment TreeO(n)O(log n)O(log n)
Sparse TableO(n log n)**O(1)**None

**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

A Sparse Table beats a Segment Tree when:

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.

Which operation does NOT fit a Sparse Table?

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.

st[3][2] holds the min on the range:

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.

The complexity of a single Sparse Table query:

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!
ApplicationHow Sparse Table helps
LCA in a treeRMQ on Euler tour depths → O(1) LCA after O(n log n) build
Suffix arraysLCP queries use a Sparse Table for O(1) answers
Cartesian TreeRMQ gives the root of any subrange

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

LCA via a Sparse Table reduces to which problem?

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
Sparse Table: O(1) Range Queries

0

1

Sign In