Prefix Sum 101

What prefix sums are

The idea

A prefix sum array stores, at position i, the total of all elements before it. With pre[0] = 0 and pre[i + 1] = pre[i] + a[i], the sum of any range a[l..r] is simply pre[r + 1] - pre[l]. You pay O(n) once to build it and then answer each range-sum query in O(1).

The deeper insight is that a subarray sum is the difference of two prefix sums. That turns questions about subarrays into questions about pairs of prefix values, and pairs can be found quickly with a hash map. This is what makes prefix sums powerful in interviews, far beyond simple range queries.

Signals in a problem statement

• "Sum of elements between index i and j", asked many times.
• "Count subarrays whose sum equals k", especially when numbers can be negative (sliding window fails there).
• "Pivot" or "balance" index where the left sum equals the right sum.
• "Longest subarray with equal numbers of 0s and 1s" — replace 0 with -1 and look for sum 0.
• "Subarray sum divisible by k" — look at prefix sums modulo k.
• 2D grids: "sum of a sub-rectangle".

Mental model

Picture a running balance in a bank passbook. The amount spent between two dates is the balance on the first date minus the balance on the second. You never need to add up the individual transactions again. Similarly, if two moments have the same balance, nothing net was added between them: that is exactly the "subarray with sum 0" condition.

Core patterns with templates

1. Build and query

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

def range_sum(pre, l, r):
    return pre[r + 1] - pre[l]

Python's itertools.accumulate(a, initial=0) builds the same list in one line.

2. Pivot index (left sum equals right sum)

def pivot_index(a):
    total, left = sum(a), 0
    for i, x in enumerate(a):
        if left == total - left - x:
            return i
        left += x
    return -1

3. Count subarrays with sum k (prefix sum + hash map)

from collections import defaultdict

def subarray_sum(a, k):
    count = defaultdict(int)
    count[0] = 1
    run = ans = 0
    for x in a:
        run += x
        ans += count[run - k]
        count[run] += 1
    return ans

Seeding count[0] = 1 handles subarrays that start at index 0. Example: a = [1, 2, 3], k = 3. Running sums are 1, 3, 6. At 3 we find count[0] = 1 (subarray [1,2]); at 6 we find count[3] = 1 (subarray [3]). Answer 2.

4. Longest subarray with sum 0 (first occurrence)

def longest_balanced(bits):
    first = {0: -1}
    run = best = 0
    for i, b in enumerate(bits):
        run += 1 if b == 1 else -1
        if run in first:
            best = max(best, i - first[run])
        else:
            first[run] = i
    return best

For counting store how many times each sum appeared; for longest store the first index only.

Complexity, mistakes and edge cases

Complexity

Common mistakes

• Off-by-one in the prefix array. Using pre[i] = a[0] + ... + a[i] (inclusive) makes the range formula pre[r] - pre[l - 1], which breaks at l = 0. The extra leading zero avoids this.
• Forgetting count[0] = 1 or first = {0: -1}, so subarrays that start at the beginning are missed.
• Updating the map before querying. In the counting template, look up run - k first, then record run; otherwise k = 0 counts empty subarrays.
• Reaching for sliding window with negative numbers. If values can be negative, the window is not monotonic; prefix sums with a map are the right tool.
• Overwriting the first index in "longest" problems. Only store an index the first time a sum appears.
• Modulo with negatives. In Python -1 % 5 is 4, which is what you want; in Java or C++ you must add k and take the modulo again.

Edge cases

Empty array, single element, all zeros (many overlapping answers), k = 0, very large or very negative values, and a pivot at index 0 or at the last index (the empty side sums to 0).

2D prefix sums in one formula

P[i+1][j+1] = grid[i][j] + P[i][j+1] + P[i+1][j] - P[i][j]. The sum of the rectangle from (r1, c1) to (r2, c2) is P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]. Draw the four rectangles once and you will never forget it.

Variations and practise

How interviewers twist it

• Transform the input first. Replace 0 with -1 to turn "equal zeros and ones" into "sum zero". Replace each element with 1 if odd else 0 to count subarrays with exactly k odd numbers.
• Divisible by k. Two prefix sums with the same remainder modulo k bound a subarray whose sum is divisible by k.
• Product instead of sum. "Product of array except self" uses a prefix product from the left and a suffix product from the right, without division.
• Difference arrays. The reverse idea: to add v to every element in [l, r] many times, add v at l and subtract it at r + 1, then take one prefix sum at the end. Great for booking and range-update questions.
• Updates between queries. If the array changes, a plain prefix array costs O(n) per update. Mention a Fenwick tree or segment tree for O(log n) updates and queries, even if you do not code it.

How to explain it

Say: "A subarray sum is pre[j] - pre[i], so I need the number of earlier prefix values equal to pre[j] - k, which I keep in a hash map." That one sentence shows you understand the idea rather than a memorised template.

Practise

The problems below cover the pivot index, counting subarrays with a target sum (with negatives allowed), and the longest balanced subarray. For each one, write the first few running sums on paper before coding.