ZERO / HERO
Running totals on a receipt

Prefix Sums & Difference Arrays

The analogy

Write down the running total after every item on a receipt. Now the cost of any stretch of items is just one subtraction — the total at the end minus the total before the start. The mirror trick: to add £5 to items 3 through 9, mark "+5 starts here" and "−5 ends here", then run the totals once at the end.

Visualizer

Running totals

step 1 / 10
5
0
3
1
8
2
1
3
9
4
2
5
7
6
4
7

The array [5, 3, 8, 1, 9, 2, 7, 4]. Someone will ask for many range sums.naive: O(n) per query

from itertools import accumulate
from collections import Counter

a = [3, 1, 4, 1, 5, 9, 2]
P = [0] + list(accumulate(a))       # sentinel zero
P[5] - P[2]                         # sum of a[2:5] — O(1)

def range_add(n, updates):          # difference array
    D = [0] * (n + 1)
    for l, r, v in updates:
        D[l] += v
        D[r + 1] -= v               # O(1) per update
    return list(accumulate(D[:n]))  # materialise once

def count_subarrays_sum_k(a, k):    # works with negatives
    seen, run, total = Counter({0: 1}), 0, 0
    for v in a:
        run += v
        total += seen[run - k]
        seen[run] += 1
    return total
Check yourself

You must apply 100,000 range-add updates then read the array once. Best tool?