Cut it into √n pieces

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.

Fig. 1 — Range sum with √n decompositionquery from 10% to 90% of the array

Loading interactive figure…

Static version: with n = 1,000,000, summing 80% of the array costs 800,000 steps in the simple loop and 2,798 with blocks of 1,000.

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.