11Prefix Sums & Difference Arrays — The Same Arithmetic, Facing Two Ways

01Four questions, one array, one Tuesday

One array of 730 daily sales totals, one Tuesday, and four questions that arrive from four different people.

The finance lead wants how much came in between two dates, and she will ask it about a different pair of dates every few minutes. The floor manager wants how many days fell below the two-thousand-dollar line, over whatever stretch of the calendar she is arguing about. The forecasting script wants the average of every ninety-day window, and there are 641 of those windows in an array of 730 days. The owner wants the busiest single day of the year.

Nothing in that list is hard. You can write all four loops in a morning, and every one of them will be correct.

Each of the four is a loop, and each loop is honest work. The finance lead's last question covered ninety days, so it added 90 numbers together. Her next one covers a different ninety, so it adds another 90 of them. Four hundred such questions in a working day is 36,000 additions, and the machine will not notice 36,000 additions. The forecasting script's 641 windows come to 57,690 additions between them, and the machine will not notice those either. This is the ordinary state of affairs, and it is worth saying plainly that nothing has gone wrong yet.

Look at what the additions are rather than at how many there are. Yesterday's ninety-day window and today's share 89 of their days, and every one of those 89 values gets added a second time by a loop that already added it. That happens because one read of this array hands back exactly one day's takings. A question about a stretch of days therefore has to touch every cell in the stretch, and the honest price is the length of the block, charged once per question. At 730 daily totals that price is invisible. The same array of per-minute readings holds 525,600 cells a year, and the same questions are the same shape at that size.

Three of the four questions are one question wearing different clothes. A range total is a total. The count below the line is also a total, once each day is scored one for under and zero for over. A ninety-day average is a range total divided by 90. The owner's question is not built that way. The busiest day asks which single cell is largest, and largest is not something anyone adds up. Hold that difference where you can see it, because the two forms this page builds are made out of adding and taking away, and nothing else. Mark the busiest day as unfinished business, because everything this page builds in its first half will refuse it.

02Can you take a piece back out?

Page 9 handed you a running maximum down a stored array and called it one extra pass and nearly free, and page 9 was right. Page 7 was right as well. It set total, count, minimum and maximum side by side as summaries that ride along with a key, and said the reach does not vary with the payload. Neither page was hedging, and neither owes you a correction. There is one inch of ground where both of those true statements stop being true, and it is worth standing on before any machinery exists to defend it. The inch has nothing to do with extremes, which is exactly why it is easy to walk straight past.

Every summary either page handed you was a fold in. A new item arrived, the summary absorbed it, and nothing already inside was ever removed again. Now watch Tuesday's four loops with that in mind. Each loop re-adds numbers the loop before it already added, and the only way to stop paying twice is to hold on to an earlier total and take back the part you did not want. That is a fold run out. It is a different demand, and this page is the one place in the course that makes it.

So ask it of the aggregate itself, before a single line is written: can I take a piece back out? A total says yes, and the removal is a subtraction. A count says yes for the same reason, because a count is a total of ones wearing a different name. XOR says yes, and says it louder than either. XOR is its own inverse, so the piece leaves by the very operation that put it there, and there is not even a minus sign involved. Three aggregates, three yeses, and all three are the same yes.

Now the other column, which is longer than most people expect. A maximum says no. You hold the largest value across the stretch and nothing whatever about the rest, so no arithmetic removes one sample and leaves the largest of the survivors behind. A minimum fails in the identical way. A count of distinct users fails for a subtler reason, because taking a day's events back out never tells you how many of those users also showed up on some other day. And GCD says no, which is the refusal worth holding on to. GCD is associative, and associative is precisely what convinces people it must be precomputable. It is not. Nothing divides a value back out of a greatest common divisor, and no amount of stored scaffolding invents a way.

One aggregate fails on purpose. A cryptographic digest is built so that no piece can ever be taken back out, and that impossibility is the security property somebody paid real money for. Nothing is missing from the implementation. The refusal is a design decision, made deliberately, and made against you on purpose. Carry the question out of this section rather than the eight answers, because the answers were only ever the question applied. Six refusals close this page, and the first of them is this one question asked of five different aggregates and answered no five times. The other five are different atoms failing, and you have not built them yet.

03The array you already built by hand

A sum answered yes, so build the thing that lets you take the piece out. On page 3 you turned the counters 2, 1, 3, 1, 1 into 0, 2, 3, 6, 7 with your own hands, and priced every step of it. It cost 8 steps to count, 5 to run the total and 8 to place. Page 3 named that array a prefix sum and said it would turn up a long way from there. It has. Nothing here rebuilds it, because you built it once already and paid for it in counted steps.

The construction is one line, and it appears only so that we agree on the indices. P[0] = 0, then P[k+1] = P[k] + a[k], which on those five counters makes P[3] = 6. One pass, one addition per cell, and P finishes one entry longer than a. That is one entry longer than page 3 printed, and the counted steps say which is right. Five counters bought 5 additions, and five additions on top of P[0] = 0 make six entries, not five. The sixth is 8, the total of 2, 1, 3, 1 and 1. Page 3 stopped at 0, 2, 3, 6, 7 because a seat allocator needs the five starts and never the grand total. Every subtraction on this page needs the sixth, so keep it. Call it a dynamic program if you like, because it is one. There is one subproblem per position and exactly one choice — which is no choice at all. That is the degenerate corner of page 2's states-times-choices table, and it is why nobody reaches for the name.

You have already read this array in print, on paper, with nobody calling it anything. A bank statement stores the amounts, and the balance column beside them is the running total. No row computes its balance from scratch. Each one is the row above plus a single amount — the same one-line recurrence in a different typeface. The bank prints both columns because each answers a question the other cannot.

Page 3 read 0, 2, 3, 6, 7 as addresses to write to. Each number was the seat where one value's block began, and the array's whole job was placement. Bring a different question to the identical five numbers and the seats stop being seats. P[3] = 6 now says the first three counters total 6, and that is an answer nobody looped for. The difference between those two readings is the entire forward half of this page. A running total is a set of addresses, page 3 said, and it was right; read the identical array from here and it is a set of answers.

04Two lookups and a minus sign — but which two?

The stretch from i to j is the total ending at j with the total ending before i taken back out, and that is the entire identity. There is no second step, and no special case waiting further down. You built the running total on page 3 with your own hands. Two sections back you asked whether a piece can be taken back out, and a sum answered yes. What is left of the job is one minus sign. The difficulty here was never the arithmetic. It is writing the identity down in a form that still means the same thing tomorrow, in somebody else's editor.

Two readings of the phrase prefix sum are in circulation, and both wear the same word. Under the first, P[k] holds the total of the first k elements. So P[0] is 0, and P runs one entry longer than the array it came from. Under the second, P[k] holds the total up to and including position k. So P[0] is a[0], and the two arrays are the same length. Now pick a subtraction that belongs to one reading, and feed it an array built under the other. Nothing throws. You get a number, and the number is the honest total of a real stretch of your data, just not the stretch anybody asked about. That is why this particular bug ships instead of getting caught in the room where it was written.

Fig. 1 puts ten daily numbers above their running total and prints both. Set i and j wherever you like with the two handles. Then commit one of three subtractions before a single thing is evaluated: P[j] − P[i], P[j+1] − P[i], or P[j+1] − P[i−1]. The brute-force loop that adds the highlighted cells one at a time stays locked until you have chosen, and that lock is deliberate. Read the loop's answer first, then pick whichever expression matches it, and what you have done is arithmetic. Arithmetic does not travel to the next array. A convention does.

Here is the convention, committed once and used everywhere on this page: the sum of a[i..j] inclusive is P[j+1] − P[i]. On the array in Fig. 1 the stretch a[2..5] is P[6] − P[2], which is 23 − 4 = 19, and the loop over 4, 1, 5 and 9 hands back 19 as well. The two rejected candidates are not nonsense either. P[5] − P[2] is 14 − 4 = 10, the honest total of a[2..4]. P[6] − P[1] is 23 − 3 = 20, the honest total of a[1..5]. Three correct subtractions sit on the table, and exactly one of them is about your stretch. As for P[0] = 0, it is not a rule to memorise. It is the sum of nothing, and if that does not feel obvious the convention has not landed yet.

Two more things the same figure does to that identity are worth staying for. Flip the stored aggregate from SUM to MAX, and the subtraction still runs. With i at 0 it returns 9, and 9 is right, because page 9's running maximum was exactly this case. Now slide i off zero to 2. The identical machinery returns M[6] − M[2], which is 9 − 3 = 6, while the true maximum of a[2..5] is 9. The 6 is not a maximum of anything. It is the arithmetic difference of two maxima, a quantity no range of this array has, and on the next array it will be a different meaningless number. Then raise a[3] from 1 to 8. Seven of P's eleven entries go stale at once, and the committed query goes on printing its old 19. What that repair costs is the next section's business.

Read the identity in the fraction page 3 handed you: what the answer requires, over what one read of the structure discharges. A raw array promises one element per read. Its denominator is 1, so a ninety-day question pays for all ninety of its cells. A prefix array promises far more at every position, namely the total of everything to its left. One read now discharges an entire prefix, and the denominator went from 1 to n. Page 3 sold that same enlargement when one look at a key started buying lg u bits rather than one bit, and page 8 called it the move sorting exists to make. On the 730-day array this chapter opened with, a ninety-day question falls from 90 reads to 2. What moved was the denominator, from 1 toward 730.

That also settles a bill two earlier pages left open. Page 8's drill met the orders-between-two-dates report, four hundred runs a day against a table that keeps growing. It ruled the report a per-run purchase that should be kept, an index, without ever saying what the index is. Page 10's drill met the twin room and settled it with the log you already own: sorted at zero upkeep, two boundary probes. Both verdicts were right. Both were searching for the position of a sparse value. Here the axis is a day number, dense and consecutive, which is page 7's move landing on an integer axis — the key is the address, computed rather than searched. Page 9 named this destination in its own routing table without building it, as an address and a prefix sum when the axis is dense and every query is a range, and this is that address. When the axis is dense, the search has nothing left to find. The day is the address, so delete the two probes and keep the subtraction.

05Where does the repair start?

Ask where the number sitting in P[500] came from, and answer it before reading on. It is the total of a[0] through a[499], five hundred of the array's thousand elements folded into one cell. So a[137] is inside it. Raise a[137] by 4 and P[500] is now wrong by exactly 4. So is P[501]. So is every single entry from P[138] to the far end of the array. One write into a leaves 863 of P's 1,001 entries stale, and not one of them announces it.

This is not bad luck, and it is not a badly written loop. It is the denominator you enlarged, sending its bill on the other side of the ledger. One read of P discharges an entire prefix, and that was the whole purchase. An entry that speaks for five hundred elements is wrong the moment any one of those five hundred moves. Cheap reads and ruinous writes are one fact wearing two faces. Take the 730 days of sales this page opened on, one total per day. Correct the total for day 200 and 530 entries of P have to be walked and rewritten. The query cost fell to two lookups (a subtraction) and the update cost climbed to n.

Set that against the two structures whose repairs you have already watched and already priced. A sorted array claims something about neighbouring pairs, and page 8 charged you upkeep for keeping that claim true. Change one key and only the pairs touching that key can be in violation, so the repair stays local. Lift the item out, put it where it now belongs, and the order everywhere else was never disturbed. Cells far from the edit stay correct, because they were never making a claim about the edited cell in the first place.

A heap claims less again, and page 10 showed you exactly how much: no child beats its parent, edge by edge. One changed key violates the two or three edges around it and nothing further out. The repair therefore walks one root-to-leaf path, which page 10 priced at nineteen hops for a million items, because a heap charges each node its own height. Bounded, and bounded by the depth of the heap rather than by the number of items in it. Both of those structures share one property that nobody ever bothers to say out loud. The damage has a neighbourhood.

A prefix array has no neighbourhood at all, because it never made a neighbourly claim. P[138] and P[139] make no claim about each other, so there is nothing between them to violate. Every entry instead makes its one claim about the whole run of elements sitting behind it. Nothing near a[137] is broken, and that absence is the strange part. Everything downstream of a[137] is simply stale, and there is no local repair to attempt, because the repair is the entire tail. Hold that escalation in the order it arrived, because a structure that repairs along one path is precisely what a flat running total gave away. Sorted repairs locally, a heap repairs along one path, and a running total repairs everything downstream of the change — and the third of those is the one nobody budgets for.

06Two hundred thousand pending edits — what does applying them honestly cost?

Leave the repair bill unpaid for one section and turn the array around instead. Two hundred thousand pending instructions sit against an array of a million cells, and every one of them says add v to everything from i to j. The array is 1,000,000 cells of zero and not one instruction has been applied yet. Of the 200,000 instructions, 190,000 cover short spans of 4 to 396 cells, and the other 10,000 cover long spans of 4,000 to 24,400. The values run over the whole numbers from −40 to +160, with zero excluded. So 40 in every 200 pull their range down rather than up. The spans overlap heavily, and most cells sit under many instructions at once.

Applying them honestly means what it sounds like. Take an instruction, walk its span, add its v to every cell inside, and go on to the next. Nothing in that loop is clever and nothing in it is wrong. The bill is the total number of cell-writes it performs, and the spans decide that number entirely. Say what it is before you read on. Then write one line saying how you got there, because the reason is the part that gets corrected.

Two reasons are available in this room and they do not agree with each other. One prices every instruction at the widest span in the set. The other prices every instruction at the span it actually has. Fig. 2 takes a number and a written reason, and it holds its sweep control shut until both exist. Commit, and the widget stops applying the instructions the honest way and does something else to them instead.

The stroke rests on a question that only works pointed one way. Not given the totals, what were the parts?, which is true and inert. Ask instead: what array would I have to run a total over to get the one I actually want? Raise the ledger at i by v, and every total from i onward rises by v. That is simply what a running total does, and you have now watched it do so twice. You wanted the rise to stop after j, so put the v back at j + 1. Two writes. Take Fig. 2's single illustration. It writes +5 at index 3 and −5 at index 901, which raises cells 3 to 900 by five. That span is 900 − 3 + 1 = 898 cells, moved by two touches.

The descriptive fact arrives one beat later, as confirmation rather than as the argument. What you have been writing into is D[k] = a[k] − a[k−1], the gap between each cell and the one before it. Run a total across the gaps and the original array comes back, because every cell is its predecessor plus exactly one gap. So a and D are two views of one thing and the map runs in both directions: a total forwards, a difference backwards. It is page 3's array read from the other end.

Page 2 §06 was called don't do the work yet, and this is that sentence made into a data structure. Your gut should object here, and it is right to. Between the writes and the sweep, the array on screen holds nothing that anybody asked for, and its spikes answer no question at all. D is a ledger of pending work, not the data. It becomes the data only when the sweep passes over it, which also means anyone who reads it mid-flight reads garbage. The unspoken assumption being broken is that a data structure must always contain the answer. This one contains an instruction for producing the answer.

Now the batching, and the argument is page 2's rather than a new one. Nothing can be materialised that was not written. The 200,000 updates write at most 400,000 marks, the sweep consumes each mark exactly once, and no series was summed anywhere. Put the three numbers beside each other. Pricing every instruction at the widest span gives 200,000 × 24,400 = 4,880,000,000. That is page 2's named error in new clothes — it assumes every operation could be maximal simultaneously. The honest naive cost is the summed spans, 200,000 × 900 = 180,000,000, because 900 is what the average span works out to. The ledger costs 400,000 writes plus one sweep of 1,000,000, so 1,400,000 touches, and 180,000,000 ÷ 1,400,000 = 128.6 times less work. The work did not go anywhere clever. It went into a pass you already owned, and that pass costs one sweep whether you stacked one update or a million.

Do the same thing by hand at twelve cells and the ledger loses, which is worth more to you than a win. Five updates: +5 on [2,7], −3 on [0,4], +2 on [6,11], +7 on [7,8], −1 on [3,3]. The naive cost is 6 + 5 + 6 + 2 + 1 = 20 cell-writes. The ledger is 10 writes plus a 12-cell sweep, which is 22 touches. Page 1's crossover has just turned up in your own handwriting rather than as a caution from us. Now sweep the ledger [−3, 0, 5, −1, 1, 3, 2, 7, −5, −7, 0, 0, −2] by hand, twelve running totals, and find the peak before reading on.

It resolves to [−3, −3, 2, 1, 2, 5, 7, 14, 9, 2, 2, 2], and its peak is 14 at index 7. Look at what you just did to get it. Maximum has no inverse, so the forward half of this page refused §01's busiest day outright, and that refusal still stands. The shape of the question comes back anyway. The backward half hands you a materialised array and you walk it, so the peak is read off the result rather than subtracted out of it, and it works only because nothing was ever subtracted. That is the door for any array built out of range instructions rather than stored outright.

State the model before the claim, because page 3 taught you that a bound binds a model. One flat array, O(1) for each cell you touch, nothing layered over the top. Inside that model the array is in exactly one of three positions. Fig. 2's slider walks all three over one concrete range — cells 300,000 to 349,999, so 50,000 cells long. Raw costs 50,000 reads to answer and 50,000 writes to edit. Cumulative answers in 2 reads, P[350,000] − P[300,000], and then owes 700,000 repaired entries on an edit, because everything from P[300,001] to P[1,000,000] has gone stale. Differenced edits in 2 writes and owes 350,000 accumulation steps on a question, because the total at index 349,999 has to be built from the start. No position lights both columns green, and the reason is not the slider. Any representation that discharges a whole prefix on one read is already holding aggregates that a range edit invalidates.

So go hunting for the position that is fast at both, and watch what happens when you try to build it by composing the two you have. Difference a cumulative array (D[k] = P[k] − P[k−1]) and what falls out is a[k−1], every original value back in place one index over. You have gained no structure. You have unwound your own purchase and paid two passes for the privilege. Widening the model is the real way out, and what widening costs is priced in the next section. Cheap in both directions is not expensive; it is the identity, and it hands back the array you started with.

07What does it cost to widen the model?

Put reads and writes on the same dial in alternation, take the phased workload away, and both columns go linear at once. The 1,000,000 cells are still there and so are the 200,000 operations, but nothing is phased now. A write arrives, then a read, then another write, and no sweep ever gets a quiet stretch to run in. Hold the cumulative array and each of the 100,000 range updates restages every cell downstream of it, which averages 500,000 cells of repair. Hold the difference array and each of the 100,000 reads demands the sweep that has not happened yet, all 1,000,000 cells. That is 50,000,000,000 cell-touches for the cumulative array and 100,000,000,000 for the difference array. Neither column is the cheap one.

Read that as the model widening rather than as the last section being taken back. Its claim was made inside the model printed above that slider before the slider ever moved, and inside that model the opposition still holds exactly. Run the difference of a cumulative array and the original still comes back. What the alternating workload refuses is the model, not the claim. It says this array wants structure above it, and structure is something you buy rather than something you notice.

Here is the price, named and then left alone. The repair question earlier on this page had a hard answer. A flat running total has no local repair at all. The edit breaks nothing nearby, everything downstream is merely stale, and the repair is the whole tail. A Fenwick tree or a segment tree buys back exactly the one-path repair that the flat array threw away. It is the shape page 10's heap already used, a walk from root to leaf instead of a scan. Over 1,000,000 cells that path is 20 nodes deep, which is the nineteen hops page 10 priced, counted as nodes rather than as the edges between them. A read costs about 20 touches, a write costs about 20 touches, and the 200,000 alternating operations come to roughly 4,000,000 touches against the flat array's 50,000,000,000.

It is a purchase and not a discovery. The two lookups and a minus sign are gone. No single cell in either structure holds your answer any more, and every read walks its own 20-node path to assemble one. Both directions carry a logarithm that neither of them carried before, so a genuinely phased workload is still better served by the flat array you already have. That is why this is a door rather than a lesson, and why it stays shut here. A logarithm on both sides is what you pay to stop paying a linear cost on one, and naming that trade is where this page's business ends.

08A one-day answer read off two eleven-digit totals — how many digits survive?

Shut that door and come back to the subtraction, which is the same subtraction it was four sections ago and is about to be priced in the arithmetic the machine actually has rather than the arithmetic the identity assumes. Page 9 put a sum that leaves the range of its own type on the wrong side of a seam, and charged you nine years of shipped standard-library code for it. The same bill arrives here, on a new sum. Hold eight years of profit and loss in whole cents and every row is a small integer, sitting comfortably inside an int32. The running total is not. Four hundred million rows come to roughly 10¹⁴ cents, and int32 stops at 2,147,483,647. It cycles through 2³² = 4,294,967,296 values, so that accumulator wraps 23,283 times before the last row lands. No element ever overflowed. The total did. The accumulator's type is part of the identity, and you size it for the total, never for the rows.

Sized for the total, the failure ends outright. An int64 holding cents tops out at 9,223,372,036,854,775,807, which leaves the same 10¹⁴-cent total about 92,000× of headroom, and the error is not small but zero. That route is the answer to this half, not a footnote to it. So take the width failure away entirely. Hold the identical eight years in float64 dollars rather than integer cents, where nothing wraps and nothing warns, and ask the same question again.

Four hundred million rows spread over 2,922 days, values running from a millionth up to ten million, and a running total that reaches about 1.0 × 10¹² dollars. Now ask for one flat Tuesday, where roughly 136,892 rows carry the day, every one of them small, and they come to 3.50 between them. Say plainly what that day is. It is not a typical day on a book that clears hundreds of millions. It is picked for exactly that reason, because it is the day the method breaks on: a small answer read off two enormous totals. Read as a prefix subtraction, that 3.50 is the difference of two stored totals that agree with each other to eleven digits. Float64 carries about 15 significant digits. Near 10¹² its neighbouring values are spaced 2⁻¹³ = 0.000122 apart. That spacing comes from 2³⁹ = 549,755,813,888 sitting below the total and 2⁴⁰ = 1,099,511,627,776 sitting above it.

So of float64's 15 digits, how many survive the trip? Fig. 3 wants that count committed before anything runs, with a one-line reason beside it. Then it runs the identical sum four ways over the same 400,000,000 rows. Four columns: the brute-force loop over that Tuesday's rows, the prefix subtraction, Kahan-compensated block sums, and the int32 accumulator you already priced above, running beside them as a control rather than as a question. Digits print as digits, the surviving ones in ink and the dead ones greyed. A second control then walks the same question down the array (day 1, day 800, day 2,900) while the answer stays 3.50. A footnote panel checks the subtraction itself.

The brute-force loop never lets a partial total climb above 3.50. Its accumulated error is around 8.3 × 10⁻¹⁴, and about 13 of the 15 digits come through. The prefix subtraction inherits totals near 10¹² instead. Naive sequential accumulation across 400,000,000 rows puts its error near 1.3, and against an answer of 3.50 that leaves not one digit safe. Kahan blocks pull the error back to about 0.00022, which is 4 digits. That sits within a factor of two of the 0.000122 floor the final rounding alone already imposes. The int32 column wraps its 23,283 times and prints a number related to nothing.

Here is the part almost every telling gets backwards. The subtraction destroyed nothing. The two totals sit within 3.50 of each other up near 10¹², far inside a factor of two. So their difference is exactly representable, the minus sign is exact, and the digits were already gone before it ever ran. They were rounded off one at a time, while millionths were folded into a total the size of 10¹². Each stored total therefore carries an absolute error sized for the totals. Cancelling away the large agreeing part does not create that error. It reveals it, leaving an answer of 3.50 sitting on top of an error built for 10¹².

Which is why the relative error of the answer is roughly the error already in the totals divided by the size of the answer. Here that is 1.3 over 3.50. It worsens the further down the array you ask, because the totals keep growing while one Tuesday's profit does not. On a twenty-element test array the totals are tiny and every digit survives, which is how this ships. Kahan compensation and block sums are the repair, and notice what they repair. They are better accumulation, not better subtraction. Nothing you do to the minus sign helps, which is the whole reason the repair lives in the forward pass.

09The same question, one axis on

Keep the question and add one axis: the total inside a rectangle rather than the total along a stretch. Here is a 4×4 grid of counts and, beside it, the 5×5 running total its forward pass produces. Every entry of that second grid holds the total of everything above it and everything to its left. That is the promise you already own, with one more direction folded into it. The rectangle wanted here is rows 2 to 3 by columns 2 to 3, which is four cells in the bottom-right corner. Brute force reads all four and adds them, and at this size brute force is free. The live question is how few entries of the running total can answer the same thing.

The move is the one you already own, run twice. Start from the biggest block the running total knows outright: the whole grid from the origin to the far corner, which sits in P[4][4] as 80. That block holds the rectangle you want and a great deal you do not. So take away the strip above it, 31. Then take away the strip to its left, 42. The running total holds each of those outright as a corner block of its own. Two lookups removed, two subtractions made, and nothing yet claimed about what is left standing. Fig. 4 hands you the four corner blocks and prints no formula until you assemble the answer from them. Decide first whether those two removals leave the rectangle you asked for.

Three terms give 7 for a rectangle whose four cells hold 5, 8, 9 and 3, and those add to 25. The gap is 18, and 18 is not a rounding of anything. It is the corner block of rows 0 to 1 by columns 0 to 1. That block holds 3, 1, 5 and 9, and it sits on the grid where you can count it. The strip above ran the full width of the grid, so it carried that corner. The strip to the left ran the full height, so it carried the same corner again. Removing both strips removed that block twice, and adding it back once is the fourth term: 80 − 31 − 42 + 18 = 25.

Read that line back and notice what it does not say. Four terms and four signs are written down, and not one character names the region that came out twice. This is the whole reason the rule gets stored as minus, minus, plus, and the whole reason it is gone a week later. Somebody who has opened the hole and filled it holds something else entirely. The fourth term is a region, and the region is the overlap of the two strips, which is why it is added and not subtracted. Check it a second time on rows 1 to 2 by columns 1 to 2, four cells holding 9, 2, 3 and 5, which add to 19. The running total gives 37 − 8 − 13 + 3 = 19, and the block removed twice there is the single cell holding 3.

Now ask the constructive question with the extra axis in place. Not what the totals were made of, but what grid would I have to sweep to get the rectangle I want? Add 7 to rows 1 to 2 by columns 1 to 2 of an empty grid. The ledger answers in four writes: +7 at [1][1], −7 at [1][3], −7 at [3][1], +7 at [3][3]. Same four corners as the query. Same four signs as the query. Written rather than read, which is the only difference between the two halves of this page. Then sweep twice, across the rows and then down the columns, and exactly four cells hold 7 while every other cell is still 0.

Price it where the size makes the point, because the games room in the drill is this room. A 2,048 × 2,048 tile map is 4,194,304 cells. Fourteen thousand buildings each add a bonus to a 200 × 200 rectangle. Applied honestly, that is 14,000 × 40,000 = 560,000,000 cells written. The ledger writes 14,000 × 4 = 56,000 cells, then sweeps twice for 8,388,608 additions. That is 8,444,608 touches all in, a ratio of 66.3×. On the 4×4 grid above the ledger loses outright: four writes plus a 32-step sweep, against four cells. Page 1's crossover is real at both ends of the dial. Predicting the four writes before they draw is the check that the inverse question landed, and it is the only reason this section is here.

10Where the reach is wrong

Every refusal below is one of the atoms already installed on this page, failing. The first one is the question you asked before any machinery existed, and its five noes stand exactly as you left them: maximum, minimum, a distinct-count, GCD — the one people genuinely try — and a cryptographic digest, which refuses on purpose. What is new is where each no sends you. When the answer is no, precomputation invents nothing. Route a fixed array to a sparse table, a changing one to a segment tree, an approximate distinct-count to a sketch, and a digest to a Merkle tree.

The second atom is the axis, and page 3 already charged you for it once. You cannot afford the universe, page 3 said, on the write side. This is the identical bill arriving on the query side. Microsecond timestamps over five years make u about 1.6 × 10¹⁴ cells, and n is the few million readings actually standing in them. An axis of account numbers or hostnames has no cell to index at all, and a wide sparse integer axis has cells you pay for and never read. Route both to page 9. Sort the marks and binary-search the two ends. Rank compression is not a new idea either. It is choosing a smaller u, which is what page 3's four digit-passes were doing all along.

The third atom is the arithmetic, and the section above spent both halves of it. Too narrow, and the accumulator wraps long before any subtlety about rounding gets a turn. Inexact, and every stored total carries an error sized for the totals rather than for your answer. The subtraction is honest in both cases. It hands back exactly what the forward pass put there, which is the reason the repair lives in the forward pass and nowhere else. Neither failure announces itself. Both return a number of the right shape, the right sign and roughly the right magnitude.

The fourth atom is the workload, and that door closed one section ago. A prefix array wants reads hot and writes rare. A difference array wants the opposite, and both want the two phases kept apart. Put them in alternation and neither survives: the cumulative form repairs the whole tail on every write, and the differenced form sweeps the whole array on every read. Nothing inside a flat array can be fixed to help, which is why the answer was a different structure and a logarithm on both sides. This is the only refusal here where the tool is not wrong about the data. It is wrong about the calendar.

The fifth atom is the array itself, and it is the quietest failure on the list. A materialising sweep needs a last element to sweep to. A stream does not have one. Everything else survives that: the counts are invertible, the buckets are dense, the two writes are still two writes. What dies is the pass, because it never gets to finish, and there is no moment at which the ledger is the data. Keep the idea and drop the array. A ring of bucket counts with a running total maintained in place does the same arithmetic and never needs an end.

The sixth atom is the bill for the precompute, in time or in space. Below some n the naive loop is free, and P is a second allocation, a second memory sweep and a second thing to keep true. Above some working-set size it is worse than free. P is often held at a wider type than a, so it more than doubles a footprint that already did not fit, and every query then faults two pages nowhere near each other. Page 8's own crossover dial already priced the first of those, and its number carries here unchanged: the purchase pays for itself at 3.72 questions, so the fourth question against the same array is the first one that is free. None of these is a special case with a name to memorise; each is one atom failing, which is why you will recognise them without a list.

11Twenty-five rooms, called twice each

The words prefix sum and difference array appear in none of the twenty-five statements below, because they never appear in the wild either. Nobody files a ticket naming a representation. The ticket says the nightly report has started taking four hours, or that a blur has to run sixty times a second, and it stops there. The reach is hearing the shape inside a sentence that was never written for you. That hearing is the whole product of a tool page, and no list of answers installs it.

So Fig. 5 deals the rooms one at a time and makes you call each one cold. Every room takes two commits rather than one. First the verdict, from the three this course has used since page 9 (reach for it, something else, refuse). Then the direction: forward, backward, or neither. A room will not open on one commit alone, and the status line names the half that is still missing. Neither commit can be revised once it is made, which is what makes it a commit.

The second commit is the one that matters, and it is why this is not a yes-or-no drill. Asked only whether the tool fits, you would learn the trick. This page's thesis is a call about which way a workload points, so the drill makes you point. Every statement therefore says whether anything changes, and when the thing is read. Those two facts are the entire call, and nothing else in the room is doing any work.

The rooms are drawn from wherever this arithmetic actually turns up. A 31×31 blur at sixty frames a second, and twelve thousand hotel bookings across a two-year calendar. Forty million particles that must end up packed contiguously by threads that cannot talk to each other. A leaderboard rewritten thousands of times a second. Ninety days of per-minute CPU samples, and the greatest common divisor of any span of version stamps. A 40 GB file verified one client-chosen byte range at a time, and four hundred million rows of tick data sitting frozen. None of them names a direction, and none of them is going to.

Several rooms arrive in near-identical pairs, and what separates a pair is a single clause of the statement. It is usually the clause nobody reads twice — how many times the question gets asked, or whether somebody else already fixed the width. Sometimes that clause moves the verdict. Sometimes it leaves the verdict where it stands and moves only the destination, which is the harder call of the two. Read for that clause before you commit.

When the last room is called, the census unmasks beside your own scorecard, and that scorecard has two columns. Verdicts right, and directions right, counted apart, and they are counted apart for a reason. The direction column is where this page shows up rather than the trick. A reader who calls a room correctly and still cannot say which way its workload points has the verdict and not the reason, and in the rooms that do reach, the way it points is the whole ticket. Read the census when it unmasks and check it against your own two columns, not against a rule you were given.

12Which way does this workload point?

You walk out holding one idea with two directions rather than two tricks, and a question you now ask before you build. Read it in the course's own fraction and the two directions become one move, made twice. A running total promises, at every position, the total of everything to its left. So one read discharges an entire prefix, and the denominator is what grew. That is page 3's move, and it is the move page 8 said sorting exists to make. The difference array is the identical enlargement seen from the write side, where one write discharges an entire suffix. Because the two forms are inverse maps of one another, you may enlarge one denominator or the other and never both. Which is why the reach is a reading of the room rather than a reading of the code.

Two questions on this page arrive before any machinery does, and the ordering is what makes them useful. The first asks legality. Can I take the piece I do not want back out? Sum yes, count yes, XOR yes and without even a minus sign. Maximum no, and there the method collapses rather than degrades. Asked after the build it is a caveat, and asked before it is a boundary you own. The second question is constructive. Given that a range read costs two lookups and one minus sign, what should a range write cost? Answering that yourself produced the two writes at i and at j + 1, which is why the difference array is a cost you derived and not a name you were handed.

A representation is a bet you already placed, including on the arrays where nobody remembers choosing. Raw, cumulative and differenced are three readings of the same 730 numbers, and every array you inherit is already sitting in one of them. Six refusals fell out of that same accounting, and not one of them is a special case with a name to memorise. No inverse. A sparse axis. Arithmetic too narrow for the total, or too inexact to survive the cancelling. A workload that never phases. A stream with no last element to sweep to. A precompute you cannot afford. Each is one atom failing, which is why you will recognise them without the list. And when somebody shows you reads and writes both cheap at once, say which model your claim was made in. Ours was a flat array at constant cost per cell touched, and a Fenwick tree pays a logarithm on both sides to widen it.

The four signs of the rectangle sum are the smallest test of whether any of this stayed. Plus, minus, minus, plus, rebuildable a week from now, and not because the order was memorised. You took the overlapping corner out twice with your own hands and had to put it back once, and the fourth term is that putting back. Then those same four corners returned as four writes rather than four reads, which is this page's one gesture performed in two directions. Of every array, buffer, counter table and log you meet from here: what does one read of this discharge, what does one write of it discharge, and which of those two did my workload actually need?