Prefix Sums

A prefix sum (or cumulative sum) is a precomputed running total of an array. You build it once, walking left to right and adding as you go, and in exchange you can then answer "what is the sum of the slice from position l to position r?" in a single subtraction, no matter how long the slice is. That turns a stream of range-sum questions from $O(n)$ each into $O(1)$ each, after one $O(n)$ setup.

If you have ever plotted cumulative P&L or a cumulative-return curve, you have already built a prefix sum: the equity curve is the running total of the period returns, and the return earned between two dates is just the difference of the two cumulative values. The coding technique and the trading calculation are the same object.

The definition

Define $P$ so that $P_i$ is the sum of the first $i$ elements of the array $a$:

$$P_0 = 0, \qquad P_i = a_0 + a_1 + \dots + a_{i-1} .$$

The leading $P_0 = 0$ is a convenience that removes edge cases. With this, the sum of the elements from index $l$ up to (but not including) index $r$ is

$$\sum_{k=l}^{r-1} a_k = P_r - P_l .$$

In words: the total up to r minus the total up to l leaves exactly the piece in between. Everything before l cancels. Building $P$ is one pass ($O(n)$ time, $O(n)$ space); every range query after that is one subtraction ($O(1)$).

Worked example: range sums

For a = [2, 4, 1, 5, 3, 2], the prefix array is P = [0, 2, 6, 7, 12, 15, 17].

• Sum of a[1..3] (the elements 4, 1, 5): $P_4 - P_1 = 12 - 2 = 10$.
• Sum of the whole array: $P_6 - P_0 = 17 - 0 = 17$.
• Sum of a[4..5] (3, 2): $P_6 - P_4 = 17 - 12 = 5$.

def build_prefix(a):          # O(n)
    P = [0] * (len(a) + 1)
    for i, x in enumerate(a):
        P[i + 1] = P[i] + x
    return P

def range_sum(P, l, r):       # inclusive l..r, O(1)
    return P[r + 1] - P[l]

The power move: count subarrays with sum k

The technique that makes prefix sums an interview staple is pairing them with a hash map. To count how many contiguous subarrays sum to exactly k, note that a subarray a[i..j] sums to k precisely when $P_{j+1} - P_i = k$, i.e. when $P_i = P_{j+1} - k$. So as you sweep the prefix values, keep a running tally of how many times each prefix value has occurred, and for each new prefix ask "how many earlier prefixes equal current − k?"

def subarrays_with_sum(a, k):  # O(n) time, O(n) space
    from collections import defaultdict
    count = defaultdict(int)
    count[0] = 1               # empty prefix
    running = total = 0
    for x in a:
        running += x
        total += count[running - k]   # earlier prefixes that close a k-sum
        count[running] += 1
    return total

For a = [3, 4, 7, 2, -3, 1, 4, 2] and k = 7: the subarrays [3,4], [7], [7,2,-3,1], [1,4,2], and [4,... ] combinations are all found in one pass, $O(n)$, instead of the $O(n^2)$ you would pay checking every subarray. This handles negative numbers too, which is exactly where a sliding window fails.

Extensions and pitfalls

• 2D prefix sums (the "integral image") let you sum any rectangle of a matrix in $O(1)$ after $O(nm)$ setup, useful for image and grid problems.
• Difference arrays are the mirror trick: to apply many range updates cheaply, add at the start index and subtract past the end, then prefix-sum once at the end.
• Off-by-one is the whole battle. Fix a convention, the half-open P[r] - P[l] with a leading zero is the cleanest, and stick to it. Mixing inclusive and exclusive indices is the classic bug.

In quant-dev interviews prefix sums power range-sum queries, subarray-sum-equals-k, count-nice-subarrays, pivot-index, and 2D region sums. On the desk the same structure is your cumulative-return curve and cumulative P&L, and it is the first step before scanning that curve for the peak-to-trough drawdown.