# Cut it into √n pieces

> The first talk I ever gave, at the first Code Camp IFPB/ACM, was about this.

- Author: Marcello Oliveira (https://mrcll.me/about/)
- Published: Oct 30, 2026
- Topics: ICPC, Fundamentals
- URL: https://mrcll.me/stories/root-decomposition/

The first talk I ever gave was at the first Code Camp IFPB/ACM, and it was about a technique you can explain in one sentence: split the array into blocks of size √n and keep the sum of each block.

That is it. A range-sum query in the simple loop costs up to n steps. With blocks, it costs the loose ends, at most 2√n single elements at the edges, plus the whole blocks in the middle, at most √n sums you already have. Updating one value means fixing one element and one block sum.

> Interactive figure (SqrtDecomp): open the web version at https://mrcll.me/stories/root-decomposition/

For 800,000 elements, that is the gap between 800,000 steps and 2,798. Why √n and not some other size? Bigger blocks mean fewer of them but longer loose ends; smaller blocks, the opposite. √n is where the two costs meet.

It is not the fastest structure there is; a segment tree does better. But square-root decomposition is the one you can write correctly in ten minutes, in a contest, under pressure, and that counts for a lot. The good-enough structure you fully understand beats the optimal one you copy.