Prefix sums

You’ll recognise it when

• You’re asked for the sum of a range a[l..r] many times, and the array doesn’t change between questions.
• You need to count subarrays whose sum is exactly k, and the numbers can be negative.
• Many updates each add a value to a whole range, and you only read the result at the end.
• The brute force adds up the same elements again and again: O(n) per question, O(n · q) in total.

It’s often confused with the sliding window. A window only moves forward and needs a rule that behaves as it grows. Prefix sums answer any range, in any order, and don’t care about negative numbers.

The idea

Think of a car’s odometer. To know how far you drove between two towns, you don’t add up every stretch of road in between. You read the odometer at both towns and subtract.

A prefix sum array is an odometer for your array. Walk along once and write down the running total before each element: pre[i] is the sum of the first i elements. The sum of any stretch is then the reading at its end minus the reading at its start. One pass to build, then every range costs one subtraction.

How it works

pre has one more cell than the array, and pre[i] covers a[0..i-1]. In the graphic, each pre[i] sits on the boundary just before a[i]: it’s the sum of everything to its left.

Scroll through the steps and the graphic follows along. You can also press play, step with the arrow keys, or edit the array and the queries: try l = r, or the whole array.

Why it’s correct: pre[r + 1] is a[0] + … + a[l-1] + a[l] + … + a[r], and pre[l] is a[0] + … + a[l-1]. The shared front part cancels, and what’s left is exactly a[l..r].

def build_prefix(a):
    """pre[i] = a[0] + ... + a[i-1], so pre has len(a) + 1 entries."""
    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):
    """Sum of a[l..r], both ends included, in O(1)."""
    return pre[r + 1] - pre[l]

#include <vector>
using namespace std;

// pre[i] = a[0] + ... + a[i-1], so pre has a.size() + 1 entries.
// 64-bit sums: the total can pass 2^31 even when every value fits in an int.
vector<long long> buildPrefix(const vector<long long>& a) {
    vector<long long> pre(a.size() + 1, 0);
    for (size_t i = 0; i < a.size(); i++) {
        pre[i + 1] = pre[i] + a[i];
    }
    return pre;
}

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

class PrefixSums {
    // pre[i] = a[0] + ... + a[i-1], so pre has a.length + 1 entries.
    // 64-bit sums: the total can pass 2^31 even when every value fits in an int.
    static long[] buildPrefix(long[] a) {
        long[] pre = new long[a.length + 1];
        for (int i = 0; i < a.length; i++) {
            pre[i + 1] = pre[i] + a[i];
        }
        return pre;
    }

    // Sum of a[l..r], both ends included, in O(1).
    static long rangeSum(long[] pre, int l, int r) {
        return pre[r + 1] - pre[l];
    }
}

Counting subarrays that sum to k

The same subtraction answers a harder question: how many subarrays sum to exactly k? A subarray ending at index j sums to k when some earlier prefix equals pre[j + 1] - k. So walk once, keep a hash map from each prefix value to how many times you’ve seen it, and look up running - k before adding the current prefix:

from collections import Counter

def count_subarrays(a, k):
    seen = Counter({0: 1})    # the empty prefix, pre[0] = 0
    running = count = 0
    for x in a:
        running += x
        count += seen[running - k]
        seen[running] += 1
    return count

print(count_subarrays([1, -1, 1, 1], 1))   # 5

That’s O(n) with negatives allowed, which is exactly where a sliding window fails. The {0: 1} seed counts subarrays that start at index 0.

Why it’s O(n) to build and O(1) per query

Building pre touches each element once: n additions. A query reads two cells and subtracts, whatever the length of the range. So q queries cost O(n + q) in total, against O(n · q) for adding each range up from scratch.

Space is O(n) for the n + 1 cells of pre. The catch: if the array changes, every later prefix changes too. For updates mixed with queries, use a Fenwick tree or a segment tree instead.

Common mistakes

total = pre[r] - pre[l]        # ✗ sums a[l..r-1]
total = pre[r + 1] - pre[l]    # ✓ sums a[l..r]

vector<int> pre(n + 1);          // ✗ wraps around silently
vector<long long> pre(n + 1);    // ✓ fits sums up to about 9·10¹⁸

seen = Counter()            # ✗ misses subarrays that start at 0
seen = Counter({0: 1})      # ✓ the empty prefix counts once

Variations

• 2-D prefix sums. For a grid, let S[i][j] be the sum of the rectangle of rows 0..i-1 and columns 0..j-1. Build it with S[i+1][j+1] = g[i][j] + S[i][j+1] + S[i+1][j] - S[i][j]. A rectangle from (r1, c1) to (r2, c2) is S[r2+1][c2+1] - S[r1][c2+1] - S[r2+1][c1] + S[r1][c1]: take the big corner, cut off the strip above and the strip to the left, then add back the piece you cut twice.
• Difference arrays. The reverse trick, for many “add v to a[l..r]” updates followed by one read. Record each update as d[l] += v and d[r + 1] -= v (so d needs n + 1 cells), then take the prefix sums of d once to get the final values. That’s O(n + q) instead of O(n · q).
• Other operations. Anything with an undo works the same way: prefix XOR (undo with XOR), prefix counts of a letter or a condition (how many vowels in s[l..r]?). Minimum and maximum have no undo, so they need a sparse table or a segment tree.
• Prefix sums plus binary search. With non-negative numbers, pre is sorted, so you can binary search it: the first index where the running total reaches a target, or a weighted random pick (draw a number below the total and find which cell it falls in).
• Subarray sums with a hash map. Beyond “sum equals k”, the same map of earlier prefixes finds subarrays whose sum is divisible by k (store prefixes mod k), or the longest subarray with sum k (store each prefix’s first index instead of a count).