Sign in to watch this lesson
Advanced - Data Structures and Range Queries · 3:44
Sqrt Decomposition
Cut the array into blocks of about √n and keep one summary per block: a range query becomes two partial blocks plus at most n/s summaries, O(√n), and a point update touches one value and one summary. Range updates put a lazy tag on every full block, and the summary can be a sorted copy (counting values ≥ x) or a jump table (chains of jumps), with the block size kept as a tunable constant.
You will learn
- Implement a block-sum structure that answers range sums as two partial blocks plus whole-block sums in O(√n)
- Explain why point updates are O(1) for sums but need an O(√n) rescan for min/max, and support range add with per-block tags
- Choose and justify the block size (√n, or about √(n log n) when per-block work costs log n) and handle the short last block
- Use richer block summaries such as sorted copies for 'count ≥ x' and next-outside-block jump tables