Sqrt Decomposition
In short: split the log into blocks of about √n minutes and keep one
running summary per block. An edit changes a cell and adjusts its block's
summary — two writes, O(1). A range query reads whole blocks by their summary
and only the two ragged ends cell by cell, for O(√n) total. Small blocks make
the middle expensive and big blocks make the ragged ends expensive, and √n
is the block size where neither dominates.
Last lesson's prefix row had one weakness, and Quarry hits it straight away.
Monitoring agents report late. A minute that already reads 4 errors becomes
6 when a straggler arrives, and that happens hundreds of times a minute. Every
prefix cell after the edit includes the old value, so one edit rewrites up to
n cells.
So there are two extremes, and each is fast at one thing:
| structure | edit one minute | total of l..r |
|---|---|---|
| the raw log | O(1) | O(n) |
| the prefix row | O(n) | O(1) |
When edits and queries are mixed, both extremes cost O(n) per operation on average. This lesson finds the middle, and it is an idea you'll use far beyond range sums: cut the data into blocks and keep one summary per block.
Blocks with summaries
Split the log into blocks of b minutes and store each block's total beside it.
Minute i lives in block i // b.
- Edit minute
i: change the cell, and adjust its block's summary by the same amount. Two writes, O(1). - Total of
l..r: the blocks lying entirely inside the range contribute their summary, one read each. Only the two blocks at the ends are partly covered, and those are read cell by cell.
Here are 16 minutes in four blocks of four, with the four summaries stored after the log. Watch a query over minutes 2..13:
A block that sits wholly inside the range costs one summary read. Only the two ragged ends are read cell by cell.
The last four cells are block summaries. Block A holds 3 + 1 + 4 + 1 = 9, stored once in ΣA. 20 cells. At index 16.
n = 10
b = max(1, int(n ** 0.5))
blocks = (n + b - 1) // b
print(b, blocks)b = 4
print(13 // b, 8 // b, 3 // b)Why the square root
How big should a block be? A query reads at most b − 1 cells at each ragged
end and at most n / b summaries in between, so roughly n/b + 2b reads.
Small blocks make the middle expensive, and big blocks make the ends expensive.
For a 400-minute log:
block size b |
worst-case reads |
|---|---|
| 1 | 402 |
| 5 | 90 |
| 10 | 60 |
| 14 | 56.6 |
| 20 | 60 |
| 50 | 108 |
The bottom is near b = 14, about the square root of 200, and blocks of 13 to 15 all land around 57 reads. Both extremes waste work.
With b ≈ √n an edit is O(1) and a query is O(√n). For a month of minutes,
√43,200 ≈ 208, so a query reads a few hundred cells instead of tens of
thousands, and an edit is still two writes. This lesson rounds b down to
math.isqrt(n). The exact constant hardly matters; the square root does.
Building it
Forgetting that second write is the classic bug. The log looks right and the queries are wrong:
Minute 6 drops from 2 to 0, so block 3's summary should fall from 8 to 6. It stays at 8, because the change is computed after the old value is gone.
The query walks three phases: the left end cell by cell, whole blocks by
summary, the right end cell by cell. When l and r fall in the same
block there is no middle at all, and the loop just reads the cells. Edit the
range and run it:
Your block query. Whole blocks light up four at a time, and each costs one read.
Step through the edit on its own, and watch the summary move with the cell:
❓ Cross-question — "O(√n) is worse than O(1). Why not keep the prefix row?" Because the prefix row's O(1) query comes with an O(n) edit. For
qqueries anduedits mixed together, the prefix row costs O(q + u·n) and the blocks cost O((q + u)·√n). With a thousand of each on a 43,200-minute log, that is about 43 million writes against about 400,000 reads. The blocks balance the two operations, and a mixed workload needs that balance.
Beyond sums
Anything you can compute per block and combine works: minimum, maximum, counts.
min is the interesting one. An edit can raise a cell that was its block's
minimum, and then the old summary is wrong in a way you can't patch by adding a
difference. You recompute that block from its b cells, which is still O(√n).
The exercises build it.
A block can also keep a sorted copy of its cells. Then "how many values in
l..r are at most x?" becomes a binary search per whole block. That's the
boss exercise, and a common interview question in disguise.
Idioms & real-world patterns
Lazy tags on blocks
A range edit, "add 5 to minutes 3 to 40", would touch every cell. Instead, a
block covered completely gets a pending tag: "everything here is 5 higher
than stored". Its summary grows by 5 · b and its cells aren't touched. Only
the ragged ends are edited cell by cell. A query adds the tag back in. That's
the capstone exercise, and it is the same idea segment trees use in lesson 4,
where it's called lazy propagation.
⚡ Advanced — reordering queries
If every query is known in advance, sorting them by block and walking a window across the log can answer them all in about O((n + q)·√n), even for questions no summary can answer, such as "how many distinct values in this range?". It is a whole technique on its own, and the reason √n blocks keep turning up in places that have nothing to do with sums.
Quick practice
from math import isqrt
n = 23
b = max(1, isqrt(n))
blocks = (n + b - 1) // b
print(b, blocks)The total 24 is right, but this reads every one of the 8 cells instead of skipping whole blocks, so it reports 8 reads instead of 4.
🎯 Your turn
Build Quarry's block summaries: block_query(values, l, r) returns
{"total": ..., "reads": ...} for minutes l..r, both ends included. Use
blocks of b = max(1, math.isqrt(len(values))) minutes, where block k covers
minutes k·b .. k·b + b − 1 (the last block may be shorter). A block lying
completely inside the range costs one read. Every other covered minute is
read on its own.
block_query([3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3], 2, 13)→{"total": 64, "reads": 6}block_query([3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3], 5, 6)→{"total": 11, "reads": 2}
Then press ▶ Run, tap the Live App try chips to call it with different inputs, and hit ✓ Check. Green means this piece of Quarry is built. ✅