Prefix Sums: Range Totals in O(1)

The problem

You have daily sales for a year and people keep asking: “what were total sales from day 30 to day 90?”. Adding up 61 numbers for every question is slow when there are thousands of questions.

The trick: running totals

Make a list where each position holds the total of everything before it. This is a prefix sum list:

sales = [5, 2, 7, 1, 4]
prefix = [0]
for x in sales:
    prefix.append(prefix[-1] + x)
print(prefix)

Output

[0, 5, 7, 14, 15, 19]

prefix[i] is the total of the first i items. Now the sum from index i to j (both included) is just one subtraction:

sum(i..j) = prefix[j + 1] - prefix[i]

sales = [5, 2, 7, 1, 4]
prefix = [0]
for x in sales:
    prefix.append(prefix[-1] + x)

def range_sum(i, j):
    return prefix[j + 1] - prefix[i]

print(range_sum(1, 3))   # 2 + 7 + 1
print(range_sum(0, 4))   # everything

Output

10
19

Think of it like this: Your car's odometer. To know how far you drove between Monday and Friday, you don't re-add every trip – you subtract Monday's reading from Friday's.