vault

Prefix Sums

16 min read

Prefix Sums

The prefix-sum array transforms an input array arr[0..n-1] into a new array prefix[0..n] such that prefix[i] = arr[0] + arr[1] + ... + arr[i-1]. With this O(n) preprocessing in hand, the sum of any contiguous subarray arr[l..r] becomes prefix[r+1] − prefix[l] — an O(1) range query. The technique extends to two dimensions (the summed-area table used in computer vision under the name integral image), and it has a powerful inverse — the difference array — which supports O(1) range updates against an array later read as a single point-query batch. Beyond the literal range-sum applications, prefix sums are the foundational tool for “subarray sum equals K” and many counting problems where seeing the same prefix twice means a subarray summing to zero (or to the target) lies between them.

1. Intuition — The Mile Marker on a Highway

Picture a highway with mile markers at every exit. Each segment between consecutive markers has a known length: 5 miles, 3 miles, 8 miles, 2 miles, 7 miles. Suppose someone asks, “how far is it from exit 2 to exit 4?”

Naively you’d add 8 + 2 = 10. For a query spanning many exits, you’d add many segments — work proportional to the distance.

A smarter setup: every mile marker shows its absolute distance from exit 0. So markers read 0, 5, 8, 16, 18, 25. Now the answer to any “from exit a to exit b” is just marker[b] − marker[a] — one subtraction, regardless of how many segments are spanned.

That’s prefix sums. The one-time cost: walking the highway once and painting the cumulative numbers. The lifetime payoff: every range query thereafter is O(1).

The deeper claim: any function on subarrays that decomposes as f(l, r) = g(prefix[r]) − g(prefix[l]) — sum, count of elements satisfying a predicate, XOR (since XOR is its own inverse) — admits the prefix-sum trick. This is a special case of the monoid with inverse algebraic structure: prefix sums work for any abelian group (sum, XOR, multiplication-mod-prime). They do not work for max/min (no inverse), which is why max/min range queries need segment trees or sparse tables instead.

2. Tiny Worked Example — 1D Range Sum

Let arr = [3, 1, 4, 1, 5, 9, 2, 6] (length 8). Build prefix of length 9, where prefix[i] is the sum of the first i elements (so prefix[0] = 0 is the empty-prefix convention):

i:        0  1  2  3   4   5   6   7   8
arr:         3  1  4   1   5   9   2   6
prefix:   0  3  4  8   9  14  23  25  31

The empty-prefix prefix[0] = 0 is the convention that makes the formula range_sum(l, r) = prefix[r+1] − prefix[l] work uniformly without a special case for l = 0.

Query: sum of arr[2..5] = 4 + 1 + 5 + 9 = 19. Formula: prefix[6] − prefix[2] = 23 − 4 = 19. ✓

Query: sum of arr[0..7] (the whole array) = 31. Formula: prefix[8] − prefix[0] = 31 − 0 = 31. ✓

Query: sum of arr[3..3] (single element 1) = 1. Formula: prefix[4] − prefix[3] = 9 − 8 = 1. ✓

After O(n) preprocessing, every query is one subtraction. For 10⁵ queries on a 10⁵-element array, naive is 10¹⁰ ops; prefix sums is 2 × 10⁵.

3. The Pattern Recognition Signal

Reach for prefix sums when any of these appear:

  1. “Range sum query” (1D or 2D) — the textbook use.
  2. “Multiple queries” asking for a sum, count, or aggregate over arbitrary subarrays of a static array — the more queries, the more the O(n) preprocessing pays off.
  3. “Subarray sum equals K” — combined with Hash Table, O(n) instead of O(n²).
  4. “Count of subarrays with property P” where P decomposes into a prefix difference (e.g., “subarray with at most K odd numbers” by prefixing 0/1 indicators).
  5. “XOR of subarray equals K” — replace addition with XOR. (XOR is its own inverse: prefix_xor[r+1] XOR prefix_xor[l] gives the subarray XOR.)
  6. “Range update, point query” on an array followed by a final read — that’s the difference-array dual.
  7. “Image processing — sum/average over arbitrary axis-aligned rectangles” — that’s the 2D summed-area table (a.k.a. integral image, used in the Viola-Jones face detector).
  8. “Find a subarray whose sum is divisible by K” — apply the prefix-sum mod-K + hash-set trick (two prefixes with the same mod-K residue bracket a divisible-sum subarray).

The inverse signals — when prefix sums are the wrong tool:

  • The array is mutated frequently between queries — the O(n) per update kills you. Use Segment Tree or Fenwick tree (BIT) for O(log n) updates and queries.
  • The range query is non-decomposable (max, min, GCD without an inverse) — use sparse tables (for static arrays) or segment trees.
  • The subarray must be non-contiguous — that’s a different problem entirely.

4. Pseudocode

4.1 1D Build

build_prefix(arr):
    n := length(arr)
    prefix[0] := 0
    for i in 1 .. n:
        prefix[i] := prefix[i-1] + arr[i-1]
    return prefix

4.2 1D Range Sum Query

range_sum(prefix, l, r):
    # Inclusive interval [l, r], 0-indexed.
    return prefix[r + 1] - prefix[l]

4.3 2D Build (Summed-Area Table)

build_summed_area(grid):
    R := rows(grid); C := cols(grid)
    S[0..R][0..C] := 0
    for i in 1 .. R:
        for j in 1 .. C:
            S[i][j] := grid[i-1][j-1]
                     + S[i-1][j]
                     + S[i][j-1]
                     - S[i-1][j-1]
    return S

The −S[i-1][j-1] term corrects for the rectangle counted twice in the union of “above” and “left” (inclusion-exclusion).

4.4 2D Range Sum Query

range_sum_2d(S, r1, c1, r2, c2):
    # Inclusive rectangle [(r1, c1), (r2, c2)].
    return S[r2+1][c2+1]
         - S[r1][c2+1]
         - S[r2+1][c1]
         + S[r1][c1]

Inclusion-exclusion again: total minus top strip minus left strip plus the corner that got subtracted twice.

4.5 Difference Array (Range Update, Point Query)

init_diff(n):
    diff[0..n] := 0
    return diff

range_add(diff, l, r, value):
    diff[l]     += value
    diff[r + 1] -= value           # if r+1 < n; else no-op

point_query(diff, i):
    # After all updates, take the prefix sum of `diff`.
    return prefix_sum(diff)[i]

The diff array stores the delta between consecutive elements of the conceptual updated array. A range add bumps the start delta up and the end-plus-one delta down; the prefix sum recovers the actual array values. This makes O(n + Q) for Q range updates plus a single final read of all positions, vs O(n × Q) for naively updating each cell on every range update.

4.6 Subarray Sum Equals K

count_subarrays_summing_to_k(arr, k):
    seen := { 0: 1 }                # empty prefix has sum 0 (counted once)
    running := 0
    count   := 0
    for x in arr:
        running := running + x
        if (running - k) in seen:
            count := count + seen[running - k]
        seen[running] := seen.get(running, 0) + 1
    return count

The trick: a subarray arr[i+1 .. j] has sum k iff prefix[j+1] − prefix[i] = k iff prefix[i] = prefix[j+1] − k. As we walk forward, we ask: how many earlier prefixes had the value (current prefix − k)? — answered in O(1) by a hash-counter.

5. Python Implementation

5.1 LC 303 — Range Sum Query Immutable

class NumArray:
    def __init__(self, nums: list[int]):
        self.prefix = [0] * (len(nums) + 1)
        for i, x in enumerate(nums):
            self.prefix[i + 1] = self.prefix[i] + x
 
    def sum_range(self, l: int, r: int) -> int:
        return self.prefix[r + 1] - self.prefix[l]

The class structure (constructor + query) is canonical for “preprocess once, query many” problems. O(n) build, O(1) per query.

5.2 LC 304 — Range Sum Query 2D Immutable

class NumMatrix:
    def __init__(self, matrix: list[list[int]]):
        if not matrix or not matrix[0]:
            self.S = [[0]]
            return
        R, C = len(matrix), len(matrix[0])
        self.S = [[0] * (C + 1) for _ in range(R + 1)]
        for i in range(1, R + 1):
            for j in range(1, C + 1):
                self.S[i][j] = (matrix[i-1][j-1]
                                + self.S[i-1][j]
                                + self.S[i][j-1]
                                - self.S[i-1][j-1])
 
    def sum_region(self, r1: int, c1: int, r2: int, c2: int) -> int:
        return (self.S[r2+1][c2+1]
                - self.S[r1][c2+1]
                - self.S[r2+1][c1]
                + self.S[r1][c1])

The 2D structure is the integral image in computer vision. The Viola-Jones face detector (Viola & Jones, CVPR 2001) used integral images to compute Haar-like rectangular features in O(1) per feature regardless of rectangle size — a key step in making real-time face detection viable.

5.3 LC 560 — Subarray Sum Equals K

def subarray_sum(nums: list[int], k: int) -> int:
    seen = {0: 1}
    running = 0
    count = 0
    for x in nums:
        running += x
        count += seen.get(running - k, 0)
        seen[running] = seen.get(running, 0) + 1
    return count

This is the canonical problem to spot the prefix-sum + hash-table marriage. The O(n²) brute force enumerates every subarray; this is O(n) time, O(n) space. The crucial subtlety: we update count before inserting the current prefix into seen, otherwise a 0-element “subarray” could count itself when k = 0.

5.4 Difference Array — LC 1109 Corporate Flight Bookings

def corp_flight_bookings(bookings: list[list[int]], n: int) -> list[int]:
    diff = [0] * (n + 1)
    for first, last, seats in bookings:
        diff[first - 1] += seats           # 1-indexed input
        if last < n:
            diff[last] -= seats
    # prefix-sum the diff to recover totals
    res = [0] * n
    res[0] = diff[0]
    for i in range(1, n):
        res[i] = res[i - 1] + diff[i]
    return res

For each booking, you’d naively add seats to every flight in [first, last] — O(B × n) total. With the difference array, each booking is O(1) and the final prefix-sum pass is O(n) — total O(B + n).

5.5 Subarray Sum Divisible by K (LC 974)

from collections import defaultdict
 
def subarrays_div_by_k(nums: list[int], k: int) -> int:
    seen = defaultdict(int)
    seen[0] = 1
    running = 0
    count = 0
    for x in nums:
        running = (running + x) % k
        # Python: (-1) % k is in [0, k), so this is safe even with negatives
        count += seen[running]
        seen[running] += 1
    return count

Two prefixes with the same residue mod K bracket a subarray whose sum is divisible by K. The hash-counter pattern is identical to LC 560; the only change is taking % k on the running sum.

6. Complexity

Preprocessing time: O(n) for 1D, O(R × C) for 2D — one pass over the input.

Query time: O(1) for both 1D and 2D — a constant number of array lookups and additions/subtractions per query.

Space: O(n) for the 1D prefix array, O(R × C) for the 2D summed-area table. Both can be done in-place over the input if you don’t need the original — arr[i] += arr[i-1] rewrites in place.

Why this beats brute force. Brute-force range sum is O(r − l + 1) per query, i.e., O(n) worst case. With Q queries on an n-element array, naive is O(n × Q); prefix sum is O(n + Q). For Q = n that’s O(n²) vs O(n) — a quadratic speedup. The crossover point where preprocessing pays for itself is essentially after one full-range query; after that, every additional query is pure profit.

For LC 560 (subarray sum equals k), the brute force is O(n²) (enumerate all (l, r)) or O(n³) (recompute sum each time). Prefix sum + hash table is O(n). For n = 10⁴, that’s 10⁸ vs 10⁴ — five orders of magnitude.

7. Variants and Sub-patterns

7.1 Prefix XOR

XOR is its own inverse, so the prefix-sum machinery applies verbatim with + replaced by XOR. subarray_xor(l, r) = prefix_xor[r+1] XOR prefix_xor[l]. Useful for LC 1310 (XOR queries of subarray) and LC 1442 (number of subarrays with equal XOR on either side of a split).

7.2 Prefix Product (with caveats)

For ranges of products, you can keep prefix_product[i]. range_product(l, r) = prefix_product[r+1] / prefix_product[l]. The catch: division requires the elements to be in a field (no zeros) or you do it modulo a prime (using modular inverse). With zeros in the array, prefix products break — you need a different scheme.

7.3 Difference Array as the Inverse Operator

The difference operation diff[i] = arr[i] − arr[i-1] is the inverse of the prefix-sum operation: prefix_sum(diff(arr)) == arr. This duality is why range-update / point-query is the dual problem of point-update / range-query: each is solved by composing the two operators in opposite orders.

A range update / range query combination can be supported by stacking two difference arrays (a difference of a difference). For dynamic versions of all four combinations, you’d graduate to a Fenwick Tree or Segment Tree with lazy propagation.

7.4 2D Difference Array

The 2D dual of the summed-area table: diff[r1][c1] += v; diff[r1][c2+1] -= v; diff[r2+1][c1] -= v; diff[r2+1][c2+1] += v to range-add v to a rectangle, then 2D-prefix-sum to recover. Used for “k-th largest element after Q rectangle additions.”

7.5 Prefix Min/Max — Cannot Be Range-Queried This Way

prefix_max[i] = max(arr[0..i-1]) lets you query max(arr[0..r]) in O(1), but not max(arr[l..r]) for arbitrary l. The reason: max has no inverse, so you cannot “subtract out” the prefix [0..l-1]. For arbitrary range max/min you need Sparse Table (static, O(n log n) preprocess, O(1) query) or Segment Tree (dynamic, O(n) preprocess, O(log n) query).

7.6 Prefix-Sum Trick for “Number of Subarrays with Average ≥ T”

Subtract T from every element first; then the question becomes “number of subarrays with sum ≥ 0,” reducible to inversion-counting on the prefix-sum array (use Merge Sort or a Fenwick tree).

7.7 Counting “Pivot Index” / “Equal Sum” Problems (LC 724, LC 1991)

A pivot index is one where the sum to the left equals the sum to the right. With prefix sums, this is prefix[i] == total - prefix[i+1] — a single pass after preprocessing.

8. Pitfalls

8.1 Off-By-One on the Prefix Length

The convention prefix[0] = 0, prefix[i] = sum(arr[0..i-1]) makes range_sum(l, r) = prefix[r+1] - prefix[l] work uniformly. The alternative prefix[i] = sum(arr[0..i]) requires a special case if l == 0: return prefix[r] else: prefix[r] - prefix[l-1], which is uglier and more bug-prone. Pick the off-by-one convention up front and stick with it.

8.2 Hash-Counter Insertion Order in LC 560

In subarray_sum, you must look up seen[running - k] before inserting the current running into seen. Otherwise, when k = 0, the current prefix counts itself and you over-count. The seed seen = {0: 1} represents the empty prefix — necessary so that subarrays starting at index 0 are counted (their prefix[i] - 0 = k lookup hits the seed).

8.3 Integer Overflow

For large n and large element values, prefix[n] can overflow 32-bit signed integers. In Python this is moot; in C/C++/Java, use long long/long. Some interview judges run code in C++; the same concern applies.

8.4 2D Inclusion-Exclusion Sign Errors

The 2D query formula has four terms with alternating signs. Memorize the box drawing: total minus top minus left plus the doubly-subtracted corner. Or derive from scratch on the 2x2 grid [[1,2],[3,4]] and verify before submitting.

8.5 Difference Array Off-The-End

When you do diff[r + 1] -= value, if r + 1 == n you’d index out of bounds. The clean fix: allocate diff of size n + 1 so diff[n] exists as a sentinel that’s never read. Then either ignore diff[n] in the final prefix-sum, or use it deliberately.

8.6 Mutable Array Antipattern

Prefix sums shine on static arrays. If the array is updated between queries, every update invalidates the prefix array and rebuilding is O(n) — quickly worse than naive. Detect this trap: if the problem mentions both queries and updates, reach for Fenwick Tree (O(log n) for both) or Segment Tree.

8.7 Negative Numbers in 2D Brick-Sum Problems

The summed-area table works fine with negative entries (sum is well-defined). But problems that involve area sums with thresholds (e.g., “max-size square submatrix with sum ≤ K”) can have non-monotone behavior with negatives, requiring a different decomposition.

8.8 Forgetting to Reset Between Test Cases

In competitive-programming contexts (multiple test cases per input), forgetting to clear the seen hash between test cases produces phantom matches. Always reset shared state.

9. Diagram — Inclusion-Exclusion in 2D

flowchart LR
    subgraph "Summed-area lookup for rectangle"
        A["S[r2+1][c2+1]\n(big rectangle through bottom-right)"]
        B["−S[r1][c2+1]\n(strip above the target)"]
        C["−S[r2+1][c1]\n(strip left of the target)"]
        D["+S[r1][c1]\n(top-left corner subtracted twice)"]
        A --> R["= sum of target rectangle"]
        B --> R
        C --> R
        D --> R
    end

What this diagram shows. The four-term formula for a 2D range-sum query as inclusion-exclusion. The first term S[r2+1][c2+1] is the cumulative sum of the entire rectangle from the origin to the bottom-right corner of the target. To carve out just the target rectangle, we subtract the strip above (everything in rows [0, r1)) and the strip to the left (everything in columns [0, c1)). But the upper-left rectangle [0, r1) × [0, c1) got subtracted twice — once by each strip — so we add it back once. The result: the sum of just the target rectangle in O(1), regardless of how big it is. This same inclusion-exclusion trick generalizes to k-dimensional summed-volume tables with 2^k terms in the formula.

10. Common Interview Problems

#ProblemPattern
LC 303Range Sum Query — Immutable1D prefix sum
LC 304Range Sum Query 2D — Immutable2D summed-area
LC 307Range Sum Query — MutableUse Fenwick tree, not prefix sum
LC 308Range Sum Query 2D — Mutable2D Fenwick tree
LC 560Subarray Sum Equals KPrefix sum + hash
LC 974Subarray Sums Divisible by KPrefix sum mod K + hash
LC 523Continuous Subarray Sum (multiple of K)Same residue + length ≥ 2
LC 525Contiguous Array (equal 0s and 1s)Map 0 → −1, then sum-equals-0
LC 1248Count Subarrays with Exactly K OddMap odd → 1; sum equals K
LC 930Binary Subarrays With SumSum-equals-K with 0/1 values
LC 1109Corporate Flight BookingsDifference array
LC 1854Maximum Population YearDifference array on years
LC 2381Shifting Letters IIDifference array on shifts
LC 1314Matrix Block Sum2D summed-area
LC 363Max Sum Rectangle ≤ K2D + Kadane + ordered set
LC 724Find Pivot Index1D prefix sum
LC 1480Running Sum of 1d ArrayTrivial prefix sum
LC 1413Minimum Value to Get Positive Step SumMin of running sum
LC 238Product of Array Except SelfPrefix + suffix product
LC 1352Product of Last K NumbersPrefix product with reset on zero
LC 1310XOR Queries of SubarrayPrefix XOR
LC 1442Equal-XOR TripletsPrefix XOR + counting
LC 327Count of Range SumPrefix sum + merge-sort BIT
LC 437Path Sum III (tree)Prefix sum on root-to-node path

11. Open Questions

  • What is the right algebraic generalization of “prefix sum applies”? Conjecture: any abelian group operation (closure, identity, inverse, associativity, commutativity). Max/min fail because they form a semigroup without inverses.
  • When does 2D prefix sum lose to alternative methods (e.g., for very sparse 2D queries on huge grids)? The O(R × C) preprocessing might dominate.
  • Is there a clean characterization of which subarray-counting problems can be reduced to “subarray sum equals K”? 525 (equal 0s/1s) maps via 0 → −1; 974 maps via mod K; 1248 maps via odd-indicator. The pattern feels under-formalized in interview prep material.

12. See Also

  • Hash Table — the universal companion for “subarray sum equals K”-style problems
  • Fenwick Tree — when updates and queries are both needed (O(log n) both)
  • Segment Tree — when range queries don’t decompose by subtraction (max, min)
  • Sparse Table — for static range max/min queries in O(1)
  • Sliding Window — the alternative for “subarray with property” when the predicate is monotone in window length
  • Two Pointers — sometimes interchangeable with prefix sums on positive-only arrays
  • Kadane’s Algorithm — uses a running-sum / running-max idea closely related to prefix thinking
  • Merge Sort — combined with prefix sums for “count of range sums”
  • Big-O Notation — for the O(1) query justification
  • SWE Interview Preparation MOC

Graph View

Backlinks