A simple balancing idea
Square root decomposition cuts an array into contiguous blocks, each roughly the size of the square root of the array length. Each block stores a precomputed summary, such as its sum or minimum.
Answering a range query
A range query splits into three parts:
- A partial left block, scanned element by element.
- A run of whole blocks in the middle, answered from their stored summaries.
- A partial right block, scanned element by element.
There are about a square root number of whole blocks, and each partial end has at most a block's worth of elements, so the total work per query is near the square root of the array length.
Updating
A point update changes one element and refreshes its block's summary. That touches only the affected block, which is cheap. Block size is chosen to balance the count of blocks against the size of each block, since making one smaller makes the other larger.
This technique is less sharp than a segment tree but easier to reason about, and it adapts to many summary types that are awkward for a tree.
Key idea
Group the array into blocks near the square root in size so queries combine a few partial scans with many cheap block summaries.