The Patterns Behind Most Coding Problems

Totals You Compute Once, Then Read by Subtraction

Build the running totals once and every question about the total of a stretch becomes one subtraction, including counts, rectangles and the stretch a window cannot find.

Somebody asks for the total of one stretch of a list, then for the total of

another, then another. Each answer on its own is a loop over the stretch. The

structure being used here is neither sorted order nor adjacency. It is that the

totals of the stretches are not independent of one another, because two

stretches that begin at the same place differ by exactly the values lying

between their right ends. One table, built once, turns every one of those

questions into a subtraction.

The working list throughout is $A = [2, 7, 11, 15, 1, 8, 4, 4, 9, 3]$ , ten

values totalling 64.

The table, and the entry that is not a value

Write $P_k$ for the total of the first $k$ values of $A$ . The first $k$ means

the values at positions 0 to $k - 1$ , which is the half-open reading, and that

one decision is what the rest of this rests on. $P_0$ is the total of no values,

which is 0, so eleven entries describe ten values.

FIG 1Building the table of running totals for A

step	k	the value at position k minus 1	P at k, the total of the first k values	what happened
1	0	nothing yet	0	the total of no values, and the entry that makes stretches starting at position 0 ordinary
2	1	2	2	0 plus 2
3	2	7	9	2 plus 7
4	3	11	20	9 plus 11
5	4	15	35	20 plus 15
6	5	1	36	35 plus 1
7	6	8	44	36 plus 8
8	7	4	48	44 plus 4
9	8	4	52	48 plus 4
10	9	9	61	52 plus 9
11	10	3	64	61 plus 3, and the last entry is the total of the whole list

11 steps

Every entry is the entry above it plus one value, so the table costs ten additions for ten values rather than one pass per entry. That is the same trick the table is about, used on the table itself, and getting it wrong is the quiet way to turn a linear precomputation into a quadratic one while still calling the lookups constant.

So $P_k = P_{k-1} + A_{k-1}$ , ten additions. Now the identity that makes the

table worth having. The values from position $i$ to position $j$ inclusive are

the first $j + 1$ values with the first $i$ values taken away.

The lesson stops here

9 more paragraphs to go

You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.

The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.

See the plan The contents

This is the reading half

Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.

The contents

Totals You Compute Once, Then Read by Subtraction

The table, and the entry that is not a value

9 more paragraphs to go

This is the reading half

Read alongside