Lesson 270
Sqrt Decomposition
√n Blocks: O(√n) Query & Update
1:00Split an array into blocks of size sqrt(n) to answer range queries and point updates in O(sqrt(n)) and O(1) respectively — and extend the idea to offline range queries with Mo's algorithm.
By the end, you can
- Compute the block size and the number of blocks for a given n.
- Compute all block sums for a concrete array in O(n).
- Trace a range-sum query through the three-part left-tail / whole-blocks / right-tail decomposition.
- Apply a point update in O(1) by adjusting one element and one block sum.
- Derive why s = sqrt(n) minimizes the query cost n/s + s.
- Explain when sqrt decomposition is preferable to a segment tree despite its slower asymptotic bound.
- Describe what Mo's algorithm does, why it requires offline queries, and state its O((N+Q)*sqrt(N)) complexity.
Up next in String Algorithms, Advanced DP & Competitive Techniques
