Skip to content

Data Structures -> Sparse Table

Static range query structure for idempotent operations such as RMQ and LCA reductions.

  • Topic slug: data-structures/sparse-table
  • Tutorial page: Open tutorial
  • Ladder page: Open ladder
  • Repo problems currently tagged here: 1
  • Repo companion pages: 0
  • Curated external problems: 3

Microtopics

  • rmq
  • idempotent
  • immutable-array
  • log-table
  • overlapping-blocks
  • lca-reduction

Learning Sources

Source Type
cp-algorithms sparse table Reference
OI Wiki sparse table Reference
USACO Guide Euler Tour / Static RMQ Reference

Practice Sources

Source Type
CSES Static Range Minimum Queries Practice
SPOJ RMQSQ Practice

Curated External Problems

Core

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
Static Range Minimum Queries CSES Easy - Query-Heavy; Data-Structure-Heavy Idempotent Operations; Range Queries; Preprocessing Range-Min; Static-Queries; Idempotent The textbook static RMQ problem that sparse tables are built for.
Range GCD Query Library Checker Medium - - - GCD; Idempotent Same sparse-table idea with gcd aggregation.

Classics

Problem Source Difficulty Context Style Prerequisites Tags Why it fits
Static RMQ Library Checker Easy - Query-Heavy Sparse Table; Idempotent Queries; Preprocessing Range-Min; Idempotent A concise official benchmark for validating a sparse table implementation.

Repo Problems

Code Title Fit Difficulty Pattern Note Solution
STATICRANGEMINIMUMQUERIES Static Range Minimum Queries primary easy sparse table rmq; idempotent overlap query; log table preprocessing Note Code

Regeneration

python3 scripts/generate_problem_catalog.py