Algorithms / Sparse Table Rmq
Least You Need to Know: Sparse Tables, RMQ, and Static Idempotent Queries
Sparse tables preprocess answers for intervals of length power of two. They shine on **static arrays** and especially on idempotent operations like minimum, where overlapping power-of-two blocks can answer a query in `O(1)`.
The least you need to know
- Precompute answers for intervals of length `2^j` starting at each index.
- RMQ stands for range minimum query.
- Sparse tables are for static arrays; updates are not their strength.
- Idempotent operations like min and max support the classic `O(1)` query trick.
- Preprocessing usually costs `O(n log n)`.
Key notation
st[i][j]
answer on interval starting at i of length `2^j`
RMQ(l, r)
minimum on interval `[l, r]`
idempotent
combining a value with itself does not change it
Tiny worked example
- Precompute minimums for all intervals of lengths `1, 2, 4, 8, ...`.
- To answer RMQ on `[l, r]`, choose the largest `2^k` fitting in the interval.
- Compare the two precomputed blocks of length `2^k` covering the left and right ends.
- Overlap is harmless for `min`, which is why the query is constant time.
Common mistakes
- Sparse tables are poor for frequent updates because preprocessing would need to be redone.
- The overlapping-two-block query trick relies on an idempotent operation like `min`.
- Students sometimes confuse sparse tables with Fenwick or segment trees, which are better for updates.
How to recognize this kind of problem
- The array is static and there are many RMQ-style queries.
- Power-of-two interval preprocessing is suggested.
- You need fast query time more than dynamic updates.