Prefix Sums — Section 2: Arrays and Strings

Given an array $A$ , the prefix sum array $P$ is defined by $P[i] = A[0] + A[1] + \dots + A[i-1]$ , with $P[0] = 0$ . The sum of any range $A[i..j-1]$ is then $P[j] - P[i]$ — a single subtraction.

Why it's useful

Without prefix sums, $q$ range-sum queries on an array of size $n$ cost $O(nq)$ . With them, you pay $O(n)$ upfront to build $P$ and $O(1)$ per query, total $O(n + q)$ . For any query-heavy workload this is a massive speedup.

Beyond sums

The same idea generalizes: prefix XOR, prefix product (with care for zeros), prefix min/max (less useful — you can't "reverse" min). In 2D, the prefix sum $P[i][j]$ over a matrix lets you query the sum of any submatrix in $O(1)$ via the inclusion-exclusion formula $P[r2][c2] - P[r1][c2] - P[r2][c1] + P[r1][c1]$ .

Subarray sum problems

"Count subarrays whose sum equals $K$ " — a classic. Iterate through the array maintaining the running prefix sum $s$ . At each step, check whether $s - K$ has appeared before (use a hash map of prefix-sum counts). If yes, every previous occurrence is the start of a subarray with sum $K$ . $O(n)$ time, $O(n)$ extra space.

Difference arrays

The dual technique: given many range-update operations and one final read, use a difference array. To add $v$ to $A[l..r]$ , mark $D[l] += v$ and $D[r+1] -= v$ . After all updates, compute the prefix sum of $D$ to get the final array. Each update is $O(1)$ instead of $O(r - l + 1)$ .

Given an array $A$ , the prefix sum array $P$ is defined by $P[i] = A[0] + A[1] + \dots + A[i-1]$ , with $P[0] = 0$ . The sum of any range $A[i..j-1]$ is then $P[j] - P[i]$ — a single subtraction.