Skip to content
Algorithm Atlas
Data StructuresAll categories
CoreSource checked

Sparse Table

Precomputes overlapping power-of-two ranges for fast static range queries.

Explore relationshipsOpen constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category
Data Structures
Difficulty
Intermediate
Family
Range Query Structure
Tier
Core
Status
Verified
Review
Source Checked
Sources
1
Formulas
1
Relationships
3
Code example
Ready
Visualization
Ready

Overview

A Sparse Table stores answers for intervals of length 1, 2, 4, and so on, enabling O(1) idempotent queries such as range minimum.

Core Concepts

power-of-two rangestatic preprocessingidempotent operationrange query

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n log n)

Average

O(1) query after preprocessing

Worst

O(n log n)

Space

O(n log n)

When to Use

  • Use when many range queries are needed and the array does not change.
  • Use when range minimum queries is a central requirement.

When Not to Use

  • Avoid when frequent updates are required.
  • Avoid when a simpler array, map, or list already meets the access pattern.

What It Does

  • Precomputes range answers
  • Combines power-of-two blocks
  • Answers static queries quickly

Use Cases

  • Range minimum queries
  • Static array analysis
  • Lowest common ancestor helpers

Inputs

  • Static array
  • Associative idempotent operation

Outputs

  • Precomputed query table

Key Formulas (1)

Sparse table recurrence

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

Builds an answer for a larger interval from two half-size intervals.

Pseudocode

  1. 1.Store answers for ranges of length 1
  2. 2.For each larger power of two, combine two half ranges
  3. 3.For a query, choose the largest power fitting the range
  4. 4.Combine the two covering blocks

Canonical Example

Input
array = [5, 2, 7, 3], query min [1,3]
Output
answer = 2
Explanation
Two precomputed blocks cover the requested range.

Implementation Notes

  • Precompute floor log values for query lengths.
  • Keep update operations small and test invariants after insertions and deletions.
  • Keep a tiny example with known output beside the implementation.
  • Test updates and queries as sequences, not only one operation at a time.

Common Pitfalls

  • O(1) queries require an idempotent operation such as min or max.
  • The advertised performance depends on maintaining the structure's invariants.
  • Not defining boundary, empty, or degenerate inputs before implementation.
  • Incorrect updates can leave stale pointers, counts, balance metadata, or cached summaries.

Interactive Mechanism Walkthrough

Graph Frontier & Edge Relaxation

Show array intervals covered by overlapping power-of-two blocks.

Sparse Table mechanism walkthrough step 1 of 4suvwxt
Step 1 of 4: Store answers for ranges of length 1
data-structure

Notes

Sparse Tables are for static data; updates require rebuilding, while disjoint sparse tables are a specialized static range-query variant.

Sources (1)

What each reference supports for this entry.

Handbook of Data Structures and Applications

Book

Data-structures reference for sparse-table preprocessing, range-query lookup, and idempotent aggregate operations.

Explore Next

Good next jumps from the relationship graph, ranked for useful discovery.

Open discoveryOpen map
Alternative toSegment Tree

Data Structures · Core

Sparse tables answer static range queries, while segment trees support dynamic updates.

Compare with this
Conceptual neighborsFenwick Tree

Data Structures · Core

Both answer aggregate-style queries from precomputed indexed summaries, but with different update tradeoffs.

Compare with this

Relationships

View full relationship page
Alternative toSegment Tree

Sparse tables answer static range queries, while segment trees support dynamic updates.

Related Algorithms

Segment TreeFenwick Tree

Tags

Data StructureRange QueryDynamic Programming