3 subtopics · 7 problems
Sparse Table, Sqrt Decomposition & More
Sparse table for static RMQ, sqrt decomposition, and Mo's algorithm.
01Sparse Table & RMQ
O(1) range minimum/maximum queries after O(n log n) build.
2 medium1 hard
| Problem | Difficulty | Link |
|---|---|---|
| 1904BCollecting Game | medium | Solve |
| 474DFlowers | medium | Solve |
| 872DBroken BST | hard | Solve |
02Sqrt Decomposition
Divide the array into blocks of √n for balanced query/update.
2 hard
| Problem | Difficulty | Link |
|---|---|---|
| 455DSerega and Fun | hard | Solve |
| 785EAnton and Permutation | hard | Solve |
03Mo's Algorithm
Offline range queries in O((n + q) √n) with add/remove operations.
2 hard
| Problem | Difficulty | Link |
|---|---|---|
| 617EXOR and Favorite Number | hard | Solve |
| 86DPowerful array | hard | Solve |
Was this helpful?