Prefix Sum Explained: Range Sums, Subarray Sums & 2D Grids

Some questions ask for the sum of a range again and again: the total of nums[2..7], then of nums[0..3], then of nums[5..9]. Others ask how many stretches of an array add up to a target. A prefix sum array does every addition once, up front, and then answers any range with a single subtraction. With a hash map beside it, it also counts subarrays with a given sum, even when the array holds negative numbers.

Why adding up every range is too slow

One range sum is cheap: a loop from l to r. The trouble is repetition. With n = 100,000 numbers and q = 100,000 queries, a loop per query costs up to n × q = 10¹⁰ additions, a hundred times what a judge allows in a second. Neighbouring ranges share almost all their numbers, and the naive code adds the shared part again every time.

The idea: running totals

Walk the array once and write down the running total before each position:

• The array has n + 1 entries. prefix[0] = 0 is the sum of no numbers, and prefix[n] is the sum of all of them.
• Each entry is one addition. prefix[i + 1] = prefix[i] + nums[i], so building the row is O(n).
• A range is one subtraction. The sum of nums[l..r], both ends included, is prefix[r + 1] - prefix[l].

1. prefix[k] will hold the sum of the first k numbers, so the row is one longer than nums and starts with prefix[0] = 0, the empty sum. Each entry sits under the boundary where its numbers end.
2. prefix[1] = prefix[0] + nums[0] = 0 + 2 = 2. Each entry is the one before it plus one more number, so no stretch is ever added up twice.
3. prefix[2] = prefix[1] + nums[1] = 2 + 4 = 6, the same as 2 + 4 without adding those again.
4. prefix[3] = prefix[2] + nums[2] = 6 + 1 = 7, the same as 2 + 4 + 1 without adding those again.
5. prefix[4] = prefix[3] + nums[3] = 7 + 3 = 10, the same as 2 + 4 + 1 + 3 without adding those again.
6. prefix[5] = prefix[4] + nums[4] = 10 + 5 = 15, the same as 2 + 4 + 1 + 3 + 5 without adding those again.
7. prefix[6] = prefix[5] + nums[5] = 15 + 2 = 17, the total of all 6 numbers. The whole row took 6 additions: O(n), paid once.
8. Now the sum of nums[1..4]. prefix[5] covers indices 0 to 4 and prefix[1] covers index 0 alone, so taking one from the other leaves exactly indices 1 to 4.
9. 15 − 2 = 13, the same as 4 + 1 + 3 + 5. Any range now costs one subtraction, O(1), after the O(n) build, instead of up to n additions per query.

Why it works

Think of the numbers as lengths laid end to end. Each prefix value is a mark on that ruler, and a range sum is the distance between two marks. prefix[r + 1] and prefix[l] both measure from the same start, so subtracting one cancels the shared part exactly. Every range is the difference of two totals that were each computed once, so nothing is added twice.

1. Lay the numbers end to end like lengths on a ruler. prefix[k] is the mark where the first k numbers end, so prefix[0] = 0 is where the ruler starts and prefix[6] = 17 is where it ends.
2. prefix[5] measures from 0 to mark 5, prefix[1] from 0 to mark 1. Both start at the same 0, so their difference is exactly the stretch between the two marks: 15 − 2 = 13, which is 4 + 1 + 3 + 5.
3. A range that starts at index 0 subtracts prefix[0] = 0, the start of the ruler: 17 − 0 = 17. That empty first slot is why no range needs a special case.
4. One number is the distance between two neighbouring marks: 10 − 7 = 3, nums[3] itself. Any range costs two lookups and one subtraction: O(1).

The extra slot at the front keeps the formula free of special cases. With only n entries, a range starting at index 0 would need prefix[r] alone while every other range needed prefix[r] - prefix[l - 1]. Index arithmetic is where prefix-sum bugs live, so pick the n + 1 convention and use it every time.

The code

The prefix values are 64-bit: 100,000 numbers of up to a billion each overflow a 32-bit int.

#include <iostream>
#include <vector>
using namespace std;

// prefix[i] is the sum of the first i numbers, so prefix has n + 1 entries.
vector<long long> buildPrefix(const vector<int>& nums) {
    vector<long long> prefix(nums.size() + 1, 0);   // prefix[0] = 0, the empty sum
    for (size_t i = 0; i < nums.size(); i++) prefix[i + 1] = prefix[i] + nums[i];
    return prefix;
}

// Sum of nums[l..r], both ends included, in O(1).
long long rangeSum(const vector<long long>& prefix, int l, int r) {
    return prefix[r + 1] - prefix[l];   // first r + 1 numbers minus first l numbers
}

int main() {
    vector<int> nums = {2, 4, 1, 3, 5, 2};
    vector<long long> prefix = buildPrefix(nums);
    cout << "prefix:";
    for (long long p : prefix) cout << " " << p;
    cout << "\n";
    int queries[3][2] = {{1, 4}, {0, 5}, {3, 3}};
    for (auto& q : queries) {
        cout << "sum(" << q[0] << ".." << q[1] << ") = " << rangeSum(prefix, q[0], q[1]) << "\n";
    }
    return 0;
}

public class Main {
    // prefix[i] is the sum of the first i numbers, so prefix has n + 1 entries.
    static long[] buildPrefix(int[] nums) {
        long[] prefix = new long[nums.length + 1];   // prefix[0] = 0, the empty sum
        for (int i = 0; i < nums.length; i++) prefix[i + 1] = prefix[i] + nums[i];
        return prefix;
    }

    // Sum of nums[l..r], both ends included, in O(1).
    static long rangeSum(long[] prefix, int l, int r) {
        return prefix[r + 1] - prefix[l];   // first r + 1 numbers minus first l numbers
    }

    public static void main(String[] args) {
        int[] nums = {2, 4, 1, 3, 5, 2};
        long[] prefix = buildPrefix(nums);
        StringBuilder row = new StringBuilder("prefix:");
        for (long p : prefix) row.append(" ").append(p);
        System.out.println(row);
        int[][] queries = {{1, 4}, {0, 5}, {3, 3}};
        for (int[] q : queries) {
            System.out.println("sum(" + q[0] + ".." + q[1] + ") = " + rangeSum(prefix, q[0], q[1]));
        }
    }
}

def build_prefix(nums):
    """prefix[i] is the sum of the first i numbers, so prefix has n + 1 entries."""
    prefix = [0] * (len(nums) + 1)    # prefix[0] = 0, the empty sum
    for i, x in enumerate(nums):
        prefix[i + 1] = prefix[i] + x
    return prefix


def range_sum(prefix, l, r):
    """Sum of nums[l..r], both ends included, in O(1)."""
    return prefix[r + 1] - prefix[l]  # first r + 1 numbers minus first l numbers


nums = [2, 4, 1, 3, 5, 2]
prefix = build_prefix(nums)
print("prefix:", *prefix)
for l, r in ((1, 4), (0, 5), (3, 3)):
    print(f"sum({l}..{r}) = {range_sum(prefix, l, r)}")

// prefix[i] is the sum of the first i numbers, so prefix has n + 1 entries.
function buildPrefix(nums) {
  const prefix = new Array(nums.length + 1).fill(0); // prefix[0] = 0, the empty sum
  for (let i = 0; i < nums.length; i++) prefix[i + 1] = prefix[i] + nums[i];
  return prefix;
}

// Sum of nums[l..r], both ends included, in O(1).
function rangeSum(prefix, l, r) {
  return prefix[r + 1] - prefix[l]; // first r + 1 numbers minus first l numbers
}

const nums = [2, 4, 1, 3, 5, 2];
const prefix = buildPrefix(nums);
console.log(`prefix: ${prefix.join(" ")}`);
for (const [l, r] of [[1, 4], [0, 5], [3, 3]]) {
  console.log(`sum(${l}..${r}) = ${rangeSum(prefix, l, r)}`);
}

prefix: 0 2 6 7 10 15 17
sum(1..4) = 13
sum(0..5) = 17
sum(3..3) = 3

Running Sum of 1d Array asks for the prefix row itself. Find Pivot Index wants an index whose left side, prefix[i], equals its right side, total - prefix[i + 1].

Subarray sum equals k: prefix sums meet a hash map

How many contiguous subarrays add up to exactly k? That is Subarray Sum Equals K, and the array may hold negative numbers, which rules out the sliding window: dropping a negative element raises a window's sum instead of lowering it.

The subarray from i to j sums to k exactly when prefix[i] = prefix[j + 1] - k. So walk the array with a running prefix and ask at each position: how many earlier prefixes equal the current one minus k? Each one starts a subarray that ends here. A hash map from prefix value to how often it has appeared answers that in O(1), with two details:

• Start the map with {0: 1}, the empty prefix, or subarrays that start at index 0 are never counted.
• Look up before you record, so every subarray found has at least one element.

This is hashing doing for sums what it does in Two Sum: remember every value seen and look the partner up.

1. A subarray ending at i sums to k = 3 exactly when some earlier prefix equals prefix − 3. So walk once and keep a map of how often each prefix value has appeared, starting with the empty prefix: 0 → 1.
2. nums[0] = 2 makes the prefix 2. No earlier prefix equals 2 − 3 = −1, so no subarray ending here sums to 3. Record 2 only after the lookup.
3. nums[1] = −1 makes the prefix 1. No earlier prefix equals 1 − 3 = −2, so no subarray ending here sums to 3. Record 1 only after the lookup.
4. prefix = 3, and 0 was seen once — the empty prefix. So nums[0..2] = 2 − 1 + 2 sums to 3: count becomes 1.
5. prefix = 4, and 1 was seen once, after index 1. So nums[2..3] = 2 + 1 sums to 3: count becomes 2.
6. nums[4] = −2 brings the prefix back to 2. No earlier prefix equals −1, so nothing ends here; the map now holds 2 twice, and both copies will count later.
7. prefix = 5, and 2 was seen 2 times, so 2 subarrays end here: nums[1..5] and nums[5]. Adding the stored count, not 1, is what catches both. count = 4.
8. 4 subarrays in one pass: O(n) time and O(n) space for the map, against O(n²) for every pair of ends. Negative numbers do no harm, because nothing here assumes a sum only grows.

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

// How many contiguous subarrays of nums add up to exactly k. Negative numbers are fine.
int subarraySum(const vector<int>& nums, int k) {
    unordered_map<long long, int> seen;   // prefix value -> how many times it has occurred
    seen[0] = 1;                          // the empty prefix, so subarrays starting at 0 count
    long long prefix = 0;
    int count = 0;
    for (int x : nums) {
        prefix += x;
        auto it = seen.find(prefix - k);  // earlier prefixes p with prefix - p == k
        if (it != seen.end()) count += it->second;
        seen[prefix]++;                   // record this prefix only after the lookup
    }
    return count;
}

int main() {
    vector<int> nums = {2, -1, 2, 1, -2, 3};
    for (int k : {3, 2}) {
        cout << "Subarrays summing to " << k << ": " << subarraySum(nums, k) << "\n";
    }
    return 0;
}

import java.util.HashMap;
import java.util.Map;

public class Main {
    // How many contiguous subarrays of nums add up to exactly k. Negative numbers are fine.
    static int subarraySum(int[] nums, int k) {
        Map<Long, Integer> seen = new HashMap<>(); // prefix value -> how many times it has occurred
        seen.put(0L, 1);                           // the empty prefix, so subarrays starting at 0 count
        long prefix = 0;
        int count = 0;
        for (int x : nums) {
            prefix += x;
            count += seen.getOrDefault(prefix - k, 0); // earlier prefixes p with prefix - p == k
            seen.merge(prefix, 1, Integer::sum);       // record this prefix only after the lookup
        }
        return count;
    }

    public static void main(String[] args) {
        int[] nums = {2, -1, 2, 1, -2, 3};
        for (int k : new int[] {3, 2}) {
            System.out.println("Subarrays summing to " + k + ": " + subarraySum(nums, k));
        }
    }
}

def subarray_sum(nums, k):
    """How many contiguous subarrays of nums add up to exactly k. Negative numbers are fine."""
    seen = {0: 1}        # prefix value -> how many times it has occurred; 0 is the empty prefix
    prefix = count = 0
    for x in nums:
        prefix += x
        count += seen.get(prefix - k, 0)       # earlier prefixes p with prefix - p == k
        seen[prefix] = seen.get(prefix, 0) + 1  # record this prefix only after the lookup
    return count


nums = [2, -1, 2, 1, -2, 3]
for k in (3, 2):
    print(f"Subarrays summing to {k}: {subarray_sum(nums, k)}")

// How many contiguous subarrays of nums add up to exactly k. Negative numbers are fine.
function subarraySum(nums, k) {
  const seen = new Map([[0, 1]]); // prefix value -> how many times it has occurred; 0 is the empty prefix
  let prefix = 0;
  let count = 0;
  for (const x of nums) {
    prefix += x;
    count += seen.get(prefix - k) || 0; // earlier prefixes p with prefix - p == k
    seen.set(prefix, (seen.get(prefix) || 0) + 1); // record this prefix only after the lookup
  }
  return count;
}

const nums = [2, -1, 2, 1, -2, 3];
for (const k of [3, 2]) {
  console.log(`Subarrays summing to ${k}: ${subarraySum(nums, k)}`);
}

Subarrays summing to 3: 4
Subarrays summing to 2: 5

Store something else and the same loop solves more. Keep the first index of each prefix and you get the longest subarray with sum k; Contiguous Array is that, with each 0 counted as −1. Key the map on prefix % k and you get sums divisible by k, because two prefixes with equal remainders differ by a multiple of k: Continuous Subarray Sum and Subarray Sums Divisible by K.

2D prefix sums

On a grid, let P[i][j] be the sum of rows 0 to i − 1 and columns 0 to j − 1, again with an extra row and column of zeroes. Any rectangle then takes four lookups, by inclusion–exclusion.

1. P[i][j] holds the sum of the block above and left of row i, column j, with an extra row and column of zeroes. The goal is the rectangle of rows 1–2 and columns 1–2.
2. Start with the whole block from the top-left corner down to the rectangle's bottom-right: P[3][3] = 21. It holds the rectangle plus everything above it and to its left.
3. Take away the strip above, P[1][3] = 4, and the strip to the left, P[3][1] = 9. The top-left corner block sits in both strips, so it has now been taken away twice.
4. Add the corner back once, P[1][1] = 3: 21 − 4 − 9 + 3 = 11, which is 6 + 3 + 2 + 0. Four lookups answer any rectangle in O(1).

Building P is the same picture in reverse: P[i + 1][j + 1] = grid[i][j] + P[i][j + 1] + P[i + 1][j] - P[i][j], since the block above and the block to the left share a corner. Matrix Block Sum is one rectangle query per cell.

Difference arrays: prefix sums in reverse

The reverse problem is range updates: "add 2 to every element from 1 to 3", thousands of times, then report the array. Writing every element costs O(n) per update. A difference array records only where each change starts and stops, and one running sum at the end applies them all.

1. To add v to every element from l to r, write +v where the change starts and −v just after it ends. diff has n + 1 = 7 slots, so a range that ends at the last index still has a slot to stop in.
2. Add 2 to indices 1..3: diff[1] += 2 and diff[4] −= 2. Two writes, O(1), however long the range is.
3. Add 3 to indices 2..5: diff[2] += 3 and diff[6] −= 3. Two writes, O(1), however long the range is.
4. Add −1 to indices 0..1: diff[0] −= 1 and diff[2] += 1. Two writes, O(1), however long the range is.
5. Now one running sum over diff. arr[0] = −1: the −1 on 0..1 starts here, and the running sum carries it to every later index until something cancels it.
6. arr[1] = −1 + 2 = 1: the +2 on 1..3 starts here and carries forward from now on.
7. arr[2] = 1 + 4 = 5: the +3 on 2..5 starts and the −1 on 0..1 ends, so diff[2] = 4 is +3 and +1 netted together.
8. arr[3] = 5 + 0 = 5: no update starts or stops at index 3, so the running value carries straight over.
9. arr[4] = 5 − 2 = 3: the +2 on 1..3 ends here, cancelled by the −2 written at diff[4].
10. arr[5] = 3 + 0 = 3, nothing changes here. diff[6] = −3 would cancel an update one step past the end: that slot is never read, it only gave the last update somewhere to stop.
11. arr = [−1, 1, 5, 5, 3, 3]. 3 updates cost 6 writes plus one O(n) pass, where updating each range element by element costs up to n per update: O(n + q) instead of O(n × q).

Car Pooling is exactly this: a trip adds passengers at one stop and removes them at another, and the car is over capacity if any running total passes the limit. Corporate Flight Bookings does the same with seats.

Other prefix operations

The idea needs only an operation whose effect on a shared part can be undone. XOR undoes itself, so the XOR of nums[l..r] is px[r + 1] ^ px[l] (XOR Queries of a Subarray). Products cannot be divided out past a zero, so Product of Array Except Self multiplies a prefix product by a suffix product instead. Running counts of vowels or 1s work like sums, as in Maximum Score After Splitting a String. A maximum cannot be undone, so range-maximum queries need a sparse table or a segment tree.

Time and space complexity

How to recognise a prefix-sum problem

• It asks for range sums, especially many of them: "q queries", "the sum of everything before i".
• It asks how many subarrays have a sum equal to, or divisible by, k — especially with negative numbers.
• It compares the left and right parts of an array around each index.
• It applies many range updates and only then reads the result, or asks for rectangle sums in a grid.

If it wants the largest sum of any subarray, use Kadane's algorithm, the next lesson.

Common mistakes

• prefix[r] - prefix[l] silently drops nums[r]; with n + 1 entries it is prefix[r + 1] - prefix[l].
• Forgetting the {0: 1} seed, so subarrays starting at index 0 are never counted.
• Recording before the lookup: with k = 0 every position matches itself.
• Overflow: use long long or long once sums can pass two billion.
• Negative remainders: -7 % 3 is −1 in C++, Java and JavaScript; normalise with ((p % k) + k) % k.

Practice in this order

1. Running Sum of 1d Array: build the prefix row.
2. Find Pivot Index: left sum against right sum.
3. Left and Right Sum Differences: prefix and suffix sums side by side.
4. Subarray Sum Equals K: the hash map of prefix counts.
5. Contiguous Array: first indices for the longest subarray.
6. Continuous Subarray Sum: key the map on remainders.
7. Product of Array Except Self: prefix and suffix products.
8. Car Pooling: a difference array over the stops.
9. Matrix Block Sum: 2D prefix sums with clamped edges.

The prefix sum problem list has every problem in the catalogue that uses the technique. Next in this stage, Kadane's algorithm finds the maximum subarray in one pass — a prefix-sum argument in disguise.