If you need totals for many parts of the same list, you can save the running totals once and reuse them as often as you like. A prefix sum at position i is the sum of the values before i. It starts at zero, because there are no values before position zero.
For [3, 4, 2], the prefix totals are [0, 3, 7, 9]. To get the total for positions 1 through 2, subtract the prefix at 1 from the prefix at 3:
The difference is 9 - 3, or 6. Both prefixes include the initial 3, so the subtraction cancels it out. This matches the half-open range [1, 3), which includes the start and stops before the end. It’s the same convention you know from Python slicing.
Building the prefix list takes O(n) time and space. Python’s itertools.accumulate() can build it for you when you pass initial=0. After that, each range total needs just one subtraction. For q queries, that’s O(n + q) time, with the returned answers counted separately from the prefix storage. Repeatedly calling sum() over the requested ranges, on the other hand, can revisit the same values many times.
Subtraction works with negative values too. Later exercises combine prefix totals with a dictionary. An earlier total may tell you where a matching region begins, or how many matching regions you’ve seen so far. Pay close attention to what you store. An earliest position answers a different question than a frequency, even when both dictionaries use prefix totals as keys.
