Prefix Sums

Prefix Sums

Suppose you're asked many questions of the form "what's the sum of the elements from index l to index r?". Adding them up each time costs O(n) per question. A prefix sum array answers every such question in O(1) after one O(n) pass of preparation. The same idea, "store running totals, then subtract two of them", also unlocks harder problems like counting subarrays with a given sum.

Building it

prefix[i] holds the sum of the first i elements, so prefix[0] = 0:

int[] nums = {3, 1, 4, 1, 5};
int[] prefix = new int[nums.length + 1];
for (int i = 0; i < nums.length; i++) {
    prefix[i + 1] = prefix[i] + nums[i];
}
// nums   =    [3, 1, 4, 1, 5]
// prefix = [0, 3, 4, 8, 9, 14]

Range sums in O(1)

The sum of nums[l..r] (inclusive) is everything up to r, minus everything before l:

int rangeSum(int l, int r) {
    return prefix[r + 1] - prefix[l];
}
// rangeSum(1, 3) = prefix[4] - prefix[1] = 9 - 3 = 6   →   1 + 4 + 1 ✓

The extra leading 0 is what makes this formula work for l = 0 without a special case, which is why the array has length n + 1. Watch for overflow with large values or long arrays, and use long[] when sums can exceed about 2.1 billion.

The key insight: subarray sums become differences

A subarray sum is always the difference of two prefix sums: sum(l..r) = prefix[r+1] − prefix[l]. So "find subarrays summing to k" becomes "find pairs of prefix sums that differ by k". Hash maps are very good at "have I seen a value like this before?" questions.

Subarray Sum Equals K

public int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> seen = new HashMap<>();
    seen.put(0, 1);                     // the empty prefix: lets subarrays starting at index 0 be counted
    int running = 0, count = 0;

    for (int x : nums) {
        running += x;                                   // prefix sum ending here
        count += seen.getOrDefault(running - k, 0);     // earlier prefixes P with running - P == k
        seen.merge(running, 1, Integer::sum);
    }
    return count;
}

For each position, the subarrays ending here with sum k correspond exactly to earlier prefix sums equal to running − k. The map counts how many we've seen. That's O(n) time and O(n) space, versus O(n²) for checking every subarray.

Why not a sliding window? Windows only work when all numbers are non-negative: then growing the window never decreases the sum, so you know which pointer to move. With negatives, that monotonicity breaks. The prefix-sum + hash map approach handles any integers.

Variations of the same idea

• Longest subarray with sum k: store the first index each prefix sum appears at, and the answer is i − firstIndex[running − k].
• Subarray sum divisible by k: two prefix sums with the same remainder mod k bound a subarray divisible by k. Count remainders, and normalize negatives with ((running % k) + k) % k.
• Equal numbers of 0s and 1s: map 0 → −1, then find the longest subarray with sum 0.

Pivot index: comparing left and right sums

public int pivotIndex(int[] nums) {
    int total = 0;
    for (int x : nums) total += x;
    int left = 0;
    for (int i = 0; i < nums.length; i++) {
        if (left == total - left - nums[i]) return i;   // right side = total − left − current
        left += nums[i];
    }
    return -1;
}

A running prefix plus the known total gives you the suffix for free, with no second array needed.

2D prefix sums: rectangle sums in O(1)

For a matrix, P[i][j] = sum of the rectangle from (0,0) to (i−1, j−1). Build it with inclusion–exclusion: add the cell above and the cell to the left, and subtract the overlap you counted twice.

int m = grid.length, n = grid[0].length;
int[][] P = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++)
    for (int j = 1; j <= n; j++)
        P[i][j] = grid[i-1][j-1] + P[i-1][j] + P[i][j-1] - P[i-1][j-1];

// Sum of the rectangle with corners (r1,c1) and (r2,c2), inclusive, 0-indexed
int rect(int r1, int c1, int r2, int c2) {
    return P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1];
}

The inverse: difference arrays for range updates

Prefix sums make range queries cheap. Difference arrays make range updates cheap. To add v to every element in [l, r], mark the start and the point just past the end:

int[] diff = new int[n + 1];
void addRange(int l, int r, int v) { diff[l] += v; diff[r + 1] -= v; }   // O(1) per update

// After all updates, a prefix sum over diff recovers the final values
int[] result = new int[n];
int running = 0;
for (int i = 0; i < n; i++) { running += diff[i]; result[i] = running; }

This solves problems like "apply 100,000 bookings of seats to flights" or "car pooling capacity" in O(n + number of updates) instead of O(n × updates).

When prefix sums don't fit

The array must be static. If elements change between queries, each update would force rebuilding O(n) prefixes. For mixed updates and queries, use a Fenwick tree (binary indexed tree) or a segment tree: O(log n) for both.

Follow-up questions this topic invites — and their answers

Q: Why initialize the map with {0: 1} in Subarray Sum Equals K? A: It represents the empty prefix before index 0. Without it, subarrays that start at index 0 and sum to k would never be counted, because there'd be no earlier prefix equal to running − k = 0.

Q: Why doesn't a sliding window work when the array has negative numbers? A: A sliding window relies on the sum growing when you extend the window and shrinking when you move its start. Negative numbers break that, so you can't decide which pointer to move. The prefix-sum + hash map method doesn't depend on monotonicity.

Q: What if the array is updated between queries? A: A plain prefix array needs O(n) to update. Use a Fenwick tree or segment tree, which support point updates and prefix or range queries in O(log n) each.

Q: How do you count subarrays whose sum is divisible by k, with negative numbers? A: Track the frequency of running mod k, normalized to be non-negative with ((running % k) + k) % k. Any two positions with equal remainders bound a divisible subarray. Seed the map with remainder 0 → 1, as before.

Q: What's the memory cost, and can it be avoided? A: O(n) for the prefix array or the map. For a single pass (pivot index, running checks), a running variable is enough, so O(1). For arbitrary range queries after preprocessing, the O(n) array is the price of O(1) queries.