Data Structures24 min read
Sparse Table Concept
Learn sparse tables for fast static range queries like RMQ when data never changes.
David Miller
Nov 10, 2025
19.4k699
Sparse table answers range min queries fast after preprocessing.
Idea
Precompute answers for ranges of length 2^k.
Graph
flowchart TD
A[Range 0..7]
A --> B[0..3]
A --> C[4..7]
Remember
- preprocess once
- query in O(1)
- data must be static
#Python#Advanced#Table