Prefix Sums & Difference Arrays

The idea

Precompute running totals once, and the sum of any range becomes a single subtraction. Build prefix[i] = nums[0] + … + nums[i-1]; then sum(l..r) = prefix[r+1] − prefix[l] in O(1) after O(n) preprocessing:

def build_prefix(nums):
    prefix = [0]
    for x in nums:
        prefix.append(prefix[-1] + x)   # prefix[i] = sum of first i elements
    return prefix                        # sum(l..r) = prefix[r+1] - prefix[l]

Reach for it whenever you’ll answer many range queries or count subarrays by sum.

Prefix sum + hash map (the powerful one)

Count or find subarrays with a target sum by remembering prefix sums seen so far — O(n), and it handles negatives (where sliding window fails):

from collections import defaultdict
def subarray_sum(nums, k):
    seen = defaultdict(int); seen[0] = 1     # empty prefix
    total = ans = 0
    for x in nums:
        total += x
        ans += seen[total - k]               # a prior prefix completes a k-sum window
        seen[total] += 1
    return ans

Variations by what you store as the key:

• Equal 0s and 1s / equal counts (“contiguous array”) — map 0→−1, then find subarrays summing to 0 by first index per prefix value.
• Divisible by K — key on prefix % K (subarray sums divisible by K).
• Longest subarray with sum K — store the earliest index of each prefix; answer i − first[prefix − k].

The pattern: “a subarray (l..r) has property P” ⇔ “two prefixes differ by the right amount” → hash the prefixes.

Difference arrays (range updates)

The inverse trick — apply many range increments cheaply, materialize once. To add v to all of [l, r]: diff[l] += v, diff[r+1] −= v; then a prefix sum of diff gives the final array:

def range_updates(n, updates):              # updates = [(l, r, v)]
    diff = [0] * (n + 1)
    for l, r, v in updates:
        diff[l] += v; diff[r + 1] -= v
    out, run = [], 0
    for i in range(n):
        run += diff[i]; out.append(run)
    return out

Solves Range Addition, Car Pooling, Corporate Flight Bookings — O(updates + n) instead of O(updates × n).

2-D prefix sums

For matrices, a 2-D prefix sum answers any rectangle-sum in O(1) via inclusion–exclusion:

P[i][j] = sum of the submatrix from (0,0) to (i-1,j-1)
rectSum = P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]

Powers Range Sum Query 2D and Matrix Block Sum. (A 2-D difference array does range updates on a grid the same way.)

Prefix products and other aggregates

The technique generalizes beyond sums:

• Product of array except self — prefix products from the left × suffix products from the right, O(n)/O(1) (no division).
• Prefix XOR — subarray XOR = prefixXor[r+1] ^ prefixXor[l] (count subarrays with XOR = K via hash map).
• Prefix min/max / running counts for “best so far” comparisons.

Pitfalls

• Off-by-one — the prefix[0] = 0 sentinel and the r+1/l indices; keep one convention.
• Forgetting seen[0] = 1 in the hash-map count (the empty prefix makes whole-array windows count).
• Sliding window vs prefix sums — with negatives, “subarray sum = K” needs prefix + hash map, not a window.

Choosing in an interview

• Many range-sum queries → prefix sums (1-D or 2-D).
• Count/find subarrays by sum (esp. with negatives) → prefix + hash map.
• Many range updates → difference array.
• “Except self” / range XOR → prefix products / prefix XOR.