Algorithms · 11 min

Square-root decomposition

Keep one total per block of about √n numbers, so both “change one number” and “add up a stretch” stay cheap.

A train company shows a live board in its control room. For every station it keeps one number: how many riders tapped in this minute. Those numbers change all the time, every time a ticket gate beeps.

The board also answers questions like “how many people boarded between Kanda and Ikebukuro?” hundreds of times a second. So two things must be fast at once: changing one station’s number, and adding up a stretch of stations.

The obvious ways each make one of those fast by making the other slow. This article is about a dial between them, and where to set it.

Here is the row we will use the whole way through (the demo calls it the array): 16 stations on Tokyo’s Yamanote line, numbered #0 to #15, with made-up rider counts.

We will count cost in steps: one step is touching one stored number, whether you read it, change it, or both. Fewer steps means a faster board.

All the way left: store only the counts

Keep the 16 numbers and nothing else. When Ueno gets one more rider, you write one number. That is as cheap as an update gets.

The cost shows up in range sums. To answer Kanda to Ikebukuro, you loop from #1 to #12 and add 12 numbers. A range of 10,000 stations would cost 10,000 reads, every time someone asks.

All the way right: store running totals

Now go to the other extreme. Next to each station, store the total of everything from Tokyo up to and including it. These are called running totals (the demo’s table calls them prefix sums).

Any range sum is now 2 reads. Kanda to Ikebukuro is “everything up to Ikebukuro” minus “everything before Kanda”: 116 − 12 = 104. The 12 is Tokyo’s running total, which is everything before Kanda. A range of 10,000 stations still costs 2 reads.

But one more rider at Tokyo changes its own running total and every one after it: all 16 of them. With 10,000 stations, a single beep at the first gate rewrites 10,000 numbers. On a board that never stops beeping, this is the wrong end of the dial.

From here on, n is the number of stations in the row: 16 for ours, 10,000 for a big network.

The middle: one total per block

Cut the row into blocks of b neighbouring stations, and store one extra number per block: its total, called the block sum. With b = 4, our 16 stations make 4 blocks.

To add up Kanda to Ikebukuro, walk from Kanda. Kanda, Akihabara and Okachimachi cover only part of block 0, so read them one by one: 7 + 15 + 3. Blocks 1 and 2 sit fully inside the range, so read their sums: 33 + 26. Ikebukuro is the only part of block 3 you need, so read it alone: 20.

That is 104 in 6 reads instead of 12. The loose stations at the two ends are read singly; every block that fits whole inside the range counts as one read. A short range that fits inside one or two blocks is just walked station by station, so a range sum never costs more steps than the range has stations.

Changing a number is cheap too. If Ueno gets one more rider, change Ueno’s count and add 1 to block 1’s sum. Two numbers change, so 2 steps, whatever the size of the row.

In code, a range sum is three loops: loose stations up to the first block edge, whole blocks while they fit, then the leftover loose stations. Notice that update touches exactly two numbers.

riders = [12, 7, 15, 3, ...]      # one count per station
b = 4                             # block size
sums = total of each block of b

range_sum(first, last):
    total = 0
    i = first
    while i <= last and i % b != 0:   # loose stations at the start
        total += riders[i];  i += 1
    while i + b - 1 <= last:          # whole blocks
        total += sums[i / b];  i += b
    while i <= last:                  # loose stations at the end
        total += riders[i];  i += 1
    return total

update(i, new_count):
    sums[i / b] += new_count - riders[i]
    riders[i] = new_count

Turning the knob: how big should a block be?

Updates always cost 2 steps, whatever b is. So the only thing the block size changes is how many reads a range sum takes. It pulls in two directions:

• Small blocks mean lots of block sums to add up. With b = 1 every block is one station, and you are back to the plain loop.
• Big blocks mean long loose ends to walk one by one, and fewer blocks fit inside the range. With b = 8 on our row, none fit at all.

Now scale up: a network of n = 10,000 stations, and a long range across most of the row. A range rarely starts exactly on a block edge; a range can start at any station, so its start is as likely to land near a block’s end as near its beginning. On average it lands halfway, so you walk about half a block (b ÷ 2 stations) at the start and the same at the end: about b loose stations in total, plus up to n ÷ b block sums.

Read the table from the top. Going from blocks of 10 to 50 to 100, the block sums drop fast (1,000 → 200 → 100) while the loose stations grow slowly (10 → 50 → 100), so the total falls. Past 100 it flips: blocks of 200 save only 50 block sums but add 100 loose stations, so the total rises.

The turning point is where the two columns are equal: loose stations (b) equal block sums (n ÷ b). That happens when b × b = n.

The number that, times itself, gives n is called the square root of n, written √n. √10,000 = 100, because 100 × 100 = 10,000. For our 16 stations, √16 = 4, because 4 × 4 = 16. That is why the demo’s chart bottoms out at b = 4, and why the trick is called square-root decomposition.

At b = √n, a range sum costs about √n loose stations plus √n block sums: about 2 × √n reads for a typical long range. For 10,000 stations that is 200 instead of 10,000.

Back in the control room

Back to the board: 10,000 stations, 1,000 beeps and 100 long range questions a second. Running totals spend up to 10,000,000 steps a second on updates. Plain counts spend up to 1,000,000 on questions. Blocks of 100 spend 2,000 on updates and about 20,000 on questions: about 22,000 in all.

The blocks win by a wide margin because neither job is ever terrible. If the counts never changed, running totals would beat everything; if nobody asked questions, plain counts would. Blocks are for the busy middle, where both happen all the time.

It is not the fastest possible answer. A segment tree (it has its own article) stacks totals in a tree about 14 levels tall for 10,000 stations (log₂ 10,000 ≈ 13.3). It touches about 2 numbers per level, so roughly 28 steps per range sum and 14 per update; the demo’s “At real sizes” table shows these. But it is harder to write and get right. Square-root decomposition is the one you can write correctly in five minutes, which is why it shows up so often in coding interviews and contests.