Prefix Sums

A prefix sum array stores the running total before each position of an array, so the sum of any range is the total at its end minus the total at its start: one subtraction instead of a loop. It matters wherever many ranges of one unchanging array are summed, and wherever a run must hit an exact total, because a run sums to k exactly when two running totals differ by k. The topic builds the array and reads ranges from it, answers many rainfall questions without re-adding the days, and gives the template in Python, Java and TypeScript. It counts the stretches of a ledger that total exactly 2 with a map of totals, finds the till runs that pay out in whole £5 notes, where Java's and TypeScript's remainder differs from Python's, shows the off-by-one that drops a range's last element, and ends with an exercise that counts coats of paint along a road.