You have an array and a stream of “sum of range [l, r]” queries. Scanning each range is O(n) per query — too slow when there are many. Sqrt decomposition is the simplest fix: chop the array into √n contiguous blocks and precompute each block’s answer. Now a query grabs the whole blocks fully inside the range in one lookup each, and only scans the leftover elements at the two ends. Whole blocks (about √n) plus two partial ends (each under √n) gives O(√n) per query. Pick a range and watch it touch far fewer cells.
O(√n) per query & update · O(n) space · the simplest sub-linear range structure
block
A contiguous group of about √n elements, with its answer precomputed.
block sum
The precomputed aggregate (here, sum) of a whole block.
whole block
A block entirely inside the query range — used via its precomputed sum, one lookup.
partial end
The leftover elements at the range’s edges — scanned one by one.
sqrt.js — whole blocks plus two ends
Ready
An array of 16, split into 4 blocks of 4, each with a precomputed sum below it. A range query uses whole blocks by their sums and only scans the partial ends. Query range to see how few cells it touches.
–
range sum
–
cells touched
–
naive would
How it works
The magic is choosing the block size to be √n, which balances two opposing costs. A query walks over at most √n whole blocks (each handled in one step via its precomputed sum) plus at most 2·√n loose elements at the two partial ends — so total work is proportional to √n. If blocks were larger, the partial ends would be longer; if smaller, there’d be more blocks to walk. The square root is the sweet spot. Updates are just as cheap: change one element and adjust its single block’s precomputed sum — also O(√n) in the worst case, and often O(1) for a point update.
1
Split into √n blocks
Divide the array into contiguous blocks of about √n elements. For n = 16, that’s 4 blocks of 4.
2
Precompute each block’s answer
Store the sum (or min, max, gcd…) of each whole block. This is the shortcut a query will reuse instead of re-scanning.
3
Query = whole blocks + partial ends
For range [l, r], add the precomputed sum of every block fully inside, and scan only the leftover elements at the two edges. That’s O(√n) work, not O(n).
✓
Update one element and its block
To change an element, update it and adjust just its block’s precomputed sum. All queries stay correct, and the whole structure stays O(√n) per operation.
Query
O(√n)
Update
O(√n)
Space
O(n)
Block size
√n
The code
# sqrt decomposition for range-sum queriesimport math
block = int(math.isqrt(len(a)))
bsum = [sum(a[i:i+block]) for i in range(0, len(a), block)]
def query(l, r): # inclusive [l, r]
total, i = 0, l
while i <= r:
if i % block == 0 and i + block - 1 <= r:
total += bsum[i // block] # whole block: one lookup
i += block
else:
total += a[i]; i += 1 # partial end: elementreturn total
def update(i, val):
bsum[i // block] += val - a[i]; a[i] = val # fix element + its block
Quick check
1. Why is the block size chosen to be √n?
A query costs about (number of whole blocks) + (partial-end elements) = n/block + 2·block. That sum is minimized when block ≈ √n, giving O(√n) per query.
2. How does a range query use the precomputed block sums?
Blocks fully contained in [l, r] contribute their precomputed sum in a single lookup. Only the leftover elements at the two edges (less than a block each) are scanned individually — O(√n) total.
3. What must a point update do?
Updating element i changes exactly one block’s aggregate. Adjust that block’s stored sum by the delta and update the element itself. Everything stays consistent in O(1) for a point update.
FAQ
What is sqrt decomposition?
A technique that splits an array into contiguous blocks of ~√n elements, precomputing an aggregate (sum, min, gcd…) per block. Range queries combine whole-block values with a scan of the partial ends — O(√n) per query and update. It’s the simplest sub-linear range-query structure.
How does it compare to a segment tree?
A segment tree is O(log n) — asymptotically faster than sqrt decomposition’s O(√n) — but sqrt decomposition is far simpler to implement and adapt. Use a segment tree when log n matters or for complex lazy updates; sqrt decomposition is a great low-effort default for moderate sizes.
What is Mo’s algorithm and how does it relate?
Mo’s algorithm answers many offline range queries by sorting them (often by √n block index) and moving the window incrementally. It builds on sqrt-decomposition ideas — the block structure bounds total movement — achieving about O((n + q)·√n) for q queries.
What kinds of queries can sqrt decomposition handle?
Any range query whose per-block answer can be precomputed and combined: sum, min, max, gcd, value counts, and many custom aggregates. Combined with Mo’s algorithm it also handles things like distinct-values-in-range. Its flexibility comes from storing whatever per-block answer you define.
SOLVE IT YOURSELF
Solve it: range queries with no tree at all
A segment tree is O(log n) but fiddly. Chop the array into √n blocks and you get O(√n) with about ten lines — often fast enough, and far harder to get wrong. Python or TypeScript.
YOUR TASK
Implement a √-decomposition over an array: precompute a sum per block, support update(i, val), and answer range_sum(lo, hi) over an inclusive range.
HINTS — 6 IDEAS
Pick a block size around √n and keep one running sum per block.
An update touches exactly two things: the element, and its block’s sum — adjust by val − old rather than recomputing the block.
A query walks from lo to hi. When you are at a block boundary and the whole block fits inside the range, take the precomputed sum and jump a whole block.
Otherwise add the single element and step forward by one.
The cost argument: at most √n partial elements at each end, plus at most √n whole blocks in between — hence O(√n).
√n is the optimum precisely because it balances those two halves: smaller blocks mean more blocks to skip, larger blocks mean more leftovers to walk.