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).
Least you need to know
- Precompute answers for intervals of length
2^jstarting 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
Worked example
- Precompute minimums for all intervals of lengths
1, 2, 4, 8, .... - To answer RMQ on
[l, r], choose the largest2^kfitting in the interval. - Compare the two precomputed blocks of length
2^kcovering 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 it
- 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.
Next recommended lesson
Continue through this topic with Least You Need to Know: Stacks, Balanced Delimiters, and Most-Recent Openings.
Least You Need to Know: Stacks, Balanced Delimiters, and Most-Recent OpeningsRelated lessons
Keep going with nearby lessons in the same topic.