Prefix Sums: Any Range Sum From One Subtraction

A prefix sum array holds the running total of an array before each position, so the sum of any range of it is one subtraction. The cue is a property of the problem: many sums are asked over ranges of an array that does not change, or a run must add up to an exact total. Recomputing each range costs its length; the prefix array pays that cost once.

The array p has one more entry than the input. Its invariant is that p[i] is the sum of the first i elements, so p[0] is 0, the sum of none, and p[n] is the sum of all n. The sum of the elements at indices i to j inclusive is then p[j + 1] − p[i]: everything up to and including j, minus everything before i.

The values 2 6 1 4 3 show it.

Three ranges read from it, each with one subtraction:

Building the array is O(n) time and O(n) extra space for n values, and each range then costs O(1). The array must not change after it is built: one changed value shifts every total after it.

A car's mileage reading at each town works the same way: the distance between two towns is the later reading minus the earlier one. The likeness breaks on direction. A mileage reading only goes up, while a prefix array over negative values goes down as well, and the subtraction still holds, which is why prefix sums handle the negative values that break a sliding window.