Prefix sums and difference arrays

Why this matters when you build with AI

Range sums are the first thing an AI tool writes for a grid or array problem. It will often produce a prefix array, a formula with four terms, and a loop. The code looks finished, and it fails in ways that are easy to miss: the prefix array is one element too short, the query uses the right end as inclusive in one line and exclusive in another, or a range update touches one cell more than it should.

These bugs do not crash. They give a number that is off by a little, on exactly the cases the sample tests did not cover, such as an empty range or a range that touches the last cell. The check that catches them is cheap. Write a brute force that does the operation the slow obvious way, generate a few thousand small random inputs, and compare the two outputs. This lesson builds each structure with that check next to it.

Every program below was compiled with g++ -O2 -std=c++17 and run on the machine that wrote this lesson, which uses g++ 15.2.0. The random tests use a fixed seed, so you can repeat them. Nothing here was compared with an outside source. The claims are checked by the programs themselves.

Half-open ranges: the convention that prevents most bugs

A range in this lesson is half-open. The range [l, r) includes l and stops before r. So [1, 4) holds the indices 1, 2 and 3. Its length is r - l, which is 3. The range [2, 2) is empty and has length 0.

Half-open ranges have three useful properties. The length is always r - l. Two neighbouring ranges [a, b) and [b, c) split [a, c) with no gap and no overlap. An empty range needs no special case in the code.

The rule to hold onto is simple: pick one convention for the whole program and write it into the function name or a comment. Mixing [l, r] in one function with [l, r) in another is the most common source of wrong answers in this topic.

Prefix sums in one dimension

A prefix sum array stores the sum of everything before each position. Let a be the input with n values. Define pre with n + 1 entries, where pre[i] is a[0] + a[1] + ... + a[i - 1]. The extra entry pre[0] = 0 is the empty sum. Because pre has n + 1 entries, every half-open range [l, r) with 0 <= l <= r <= n has a valid answer.

The sum over [l, r) is pre[r] - pre[l]. The difference removes everything before l and keeps the values from l up to r - 1.

Worked example with a = [3, 1, 4, 1, 5]:

index:  0  1  2  3   4
a:      3  1  4  1   5
pre:    0  3  4  8   9  14

To read pre as a row, pre[0] = 0, pre[1] = 3, pre[2] = 3 + 1 = 4, pre[3] = 4 + 4 = 8, pre[4] = 8 + 1 = 9 and pre[5] = 9 + 5 = 14. The sum over [1, 4) is pre[4] - pre[1] = 9 - 3 = 6, which is 1 + 4 + 1.

Here is the C++ version. It is a small struct so the array and the query stay together:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
// 1D prefix sums. pre[i] = a[0] + ... + a[i-1]. Query [l, r) is half-open.
struct Prefix1D {
    vector<ll> pre;
    explicit Prefix1D(const vector<ll> &a) : pre(a.size() + 1, 0) {
        for (size_t i = 0; i < a.size(); i++) pre[i + 1] = pre[i] + a[i];
    }
    ll sum(int l, int r) const { return pre[r] - pre[l]; }
};

A short main that builds the example array and prints pre and one sum printed this, when run on the machine that wrote the lesson:

pre: 0 3 4 8 9 14
sum[1,4) = 6

The values use long long. With values up to 10^9 and n up to 10^6, the total can reach 10^15, which does not fit in a 32-bit int. Use long long for every sum unless you have a bound that proves the total fits.

Difference arrays for batched range updates

A prefix sum answers many range sum queries. A difference array does the opposite job. It handles many range updates, such as "add v to every value in [l, r)", and then reads the final values in one pass.

Let d be an array with n + 1 entries, all zero at the start. To add v to [l, r), do two point changes: d[l] += v and d[r] -= v. The value at index i is the running sum d[0] + d[1] + ... + d[i]. Adding v at l makes every index from l onward larger by v. Subtracting v at r cancels that from r onward, so only [l, r) keeps the change.

Worked example with n = 5 and two updates: add 2 to [0, 3), then add -1 to [2, 5).

Update 1: d[0] += 2, d[3] -= 2.
Update 2: d[2] += -1, d[5] -= -1, which is d[5] += 1.

So d = [2, 0, -1, -2, 0, 1]. The running sums are 2, 2, 1, -1, -1. Those are the final values, and they match the brute force: indices 0 and 1 get +2, index 2 gets +2 - 1, indices 3 and 4 get -1.

Each update costs O(1). One final pass costs O(n). With q updates the total is O(n + q), where the naive loop would cost O(n q) in the worst case.

The C++ function takes the list of updates and returns the final array. The updates are half-open, the same convention as above:

// Batched 1D range add with a difference array. Each op is [l, r) gets +v.
vector<ll> apply_range_adds(int n, const vector<array<ll, 3>> &ops) {
    vector<ll> d(n + 1, 0);
    for (auto [l, r, v] : ops) {
        d[l] += v;
        d[r] -= v;
    }
    vector<ll> a(n);
    ll run = 0;
    for (int i = 0; i < n; i++) {
        run += d[i];
        a[i] = run;
    }
    return a;
}

The same idea works in Python with no change in the logic. Python is fast enough for this size of input, and this program needs no input, so the site can run it:

Python · editable

Real output of that program:

difference array: [2, 2, 1, -1, -1]
brute force:      [2, 2, 1, -1, -1]
same: True

A difference array is also the reverse of prefix sums. If you take the prefix sums of a, you get a structure that answers range sums. If you take the differences a[i] - a[i - 1], you get back a difference array. Knowing both directions helps when a problem asks for "the number of updates that would produce this final array".

Prefix sums in two dimensions

For a grid g with n rows and m columns, the 2D prefix table P has size (n + 1) x (m + 1). The entry P[i][j] is the sum of all cells g[x][y] with x below i and y below j. The first row and first column are zero, which serves the same purpose as pre[0] = 0 in one dimension.

The table fills in one pass. Each cell is the cell itself, plus the cell above's total, plus the cell to the left's total, minus the top-left corner, which both of those totals already contain:

P[i + 1][j + 1] = g[i][j] + P[i][j + 1] + P[i + 1][j] - P[i][j]

The subtraction is the inclusion-exclusion step. Without it the corner is counted twice.

To get the sum over rows [r1, r2) and columns [c1, c2), take the big rectangle to the bottom-right, remove the two strips above and to the left, and add back the corner that was removed twice:

P[r2][c2] - P[r1][c2] - P[r2][c1] + P[r1][c1]

Worked example with the grid below, which the program in the next section also uses:

g:            P (with the zero border):
1 2 3         0  0  0  0
4 5 6         0  1  3  6
7 8 9         0  5 12 21
              0 12 27 45

The rectangle with rows [1, 3) and columns [1, 3) holds 5, 6, 8 and 9. Using the formula, P[3][3] - P[1][3] - P[3][1] + P[1][1] = 45 - 6 - 12 + 1 = 28, which is 5 + 6 + 8 + 9. A small script that builds this table with the same formula printed the rows above, and it printed 28 for the rectangle, the same as the direct sum.

The struct for the 2D version is short:

// 2D prefix sums. P[i+1][j+1] is the sum of g[0..i][0..j].
struct Prefix2D {
    int n, m;
    vector<vector<ll>> P;
    explicit Prefix2D(const vector<vector<ll>> &g)
        : n((int)g.size()), m((int)g[0].size()), P(n + 1, vector<ll>(m + 1, 0)) {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                P[i + 1][j + 1] = g[i][j] + P[i][j + 1] + P[i + 1][j] - P[i][j];
    }
    // Sum over rows [r1, r2) and columns [c1, c2).
    ll sum(int r1, int c1, int r2, int c2) const {
        return P[r2][c2] - P[r1][c2] - P[r2][c1] + P[r1][c1];
    }
};

Each query is O(1). Building the table costs O(nm) time and memory. For a grid of 3000 by 3000 cells, the table holds about 9 million 64-bit values, which is about 72 MB by arithmetic. Check your judge's memory limit before you choose long long.

Two-dimensional difference arrays for rectangle updates

The 1D idea extends to rectangles. To add v to every cell in rows [r1, r2) and columns [c1, c2), change four corners of a difference grid D:

D[r1][c1] += v
D[r1][c2] -= v
D[r2][c1] -= v
D[r2][c2] += v

After all updates, take the 2D prefix sum of D. The value at (i, j) in that prefix sum is the value of the cell. The reason is the same as in 1D. The top-left corner starts the increase, the two side corners remove it from the right and from below, and the bottom-right corner gives back what was removed twice.

Worked example: a 3 by 3 grid of zeros with +1 on rows [0, 2) and columns [1, 3). The corners are D[0][1] += 1, D[0][3] -= 1, D[2][1] -= 1 and D[2][3] += 1. The column index 3 is the padding column, so those two corners are never read. The final grid is:

0 1 1
0 1 1
0 0 0

The C++ version does the 2D prefix sum in place on D, which is allowed because the padding row and column absorb the corners that fall outside the grid:

// 2D range add with a 2D difference array. Each op adds v to rows [r1, r2) x cols [c1, c2).
vector<vector<ll>> apply_rect_adds(int n, int m, const vector<array<ll, 5>> &ops) {
    vector<vector<ll>> D(n + 1, vector<ll>(m + 1, 0));
    for (auto [r1, c1, r2, c2, v] : ops) {
        D[r1][c1] += v;
        D[r1][c2] -= v;
        D[r2][c1] -= v;
        D[r2][c2] += v;
    }
    // In-place 2D prefix sum over D. Row n and column m are padding and are not read.
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= m; j++) {
            if (i > 0) D[i][j] += D[i - 1][j];
            if (j > 0) D[i][j] += D[i][j - 1];
            if (i > 0 && j > 0) D[i][j] -= D[i - 1][j - 1];
        }
    vector<vector<ll>> A(n, vector<ll>(m));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) A[i][j] = D[i][j];
    return A;
}

Running the worked example through this function and printing the result gives the grid above, with trailing spaces removed:

0 1 1
0 1 1
0 0 0

Combining the two structures gives a solution to a task of the form "paint rectangles, then answer rectangle sums". Apply the rectangle updates with the difference grid, and then build a Prefix2D from the result to answer the sum queries. The worked problem below does exactly this.

Worked problem: paint rectangles, then answer sums

Here is an original problem to solve by hand first. You have a grid of n rows and m columns, all zero. You get q paint operations, each adding v to a rectangle. After all of them, you get k queries, each asking for the sum over a rectangle. Use half-open rectangles.

Work it on this input: n = 3, m = 3, one paint operation +1 on rows [0, 2) and columns [1, 3), and the query rows [1, 3) and columns [1, 3).

The final grid is the one from the previous section, so the query covers cells (1, 1), (1, 2), (2, 1) and (2, 2). Their values are 1, 1, 0 and 0. The answer is 2.

The full algorithm: build D with the corner updates, take the 2D prefix sum to get the cell values, build a Prefix2D from those values, and answer each query with four lookups. The total time is O(nm + q + k) because the corner updates cost O(1) each, and each query costs O(1).

The random test in the next section compares this pipeline with a brute force that paints each cell directly.

A prefix count with a hash map

A prefix sum can also be a key for counting. Suppose you need the number of non-empty subarrays whose sum is exactly k. A subarray a[i..j-1] has sum pre[j] - pre[i], so you need pairs of prefix positions i < j where pre[j] - pre[i] = k, which means pre[i] = pre[j] - k.

Scan the array from left to right. Keep a hash map from each prefix value to how many times it has been seen. At position j, look up pre[j] - k and add its count to the answer. Then add pre[j] to the map. The lookup comes before the insert, so a prefix never pairs with itself. Pairing a prefix with itself would count the empty subarray.

Worked example: a = [1, -1, 1, -1] and k = 0. The prefixes are 0, 1, 0, 1, 0. The subarrays with sum 0 are [1, -1] at positions 0 and 1, [-1, 1] at positions 1 and 2, [1, -1] at positions 2 and 3, and the whole array. So the answer is 4.

// Count subarrays a[l..r) (non-empty) whose sum is exactly k.
ll count_subarrays_with_sum(const vector<ll> &a, ll k) {
    unordered_map<ll, ll> seen;
    seen[0] = 1;                       // the empty prefix before the first element
    ll pre = 0, ans = 0;
    for (ll x : a) {
        pre += x;
        auto it = seen.find(pre - k);  // lookup first, so the prefix never pairs with itself
        if (it != seen.end()) ans += it->second;
        seen[pre]++;
    }
    return ans;
}

The real output of a run on the worked example is 4. The complexity is O(n) expected time and O(n) memory. The bound is expected because a hash table can slow down a lot when the keys are chosen to collide, and a judge may send such keys. On a contest judge, sort the prefix values and map them to indices, or use a custom hash function.

Testing these structures against brute force

The random tests below run every structure against a brute force on 3000 random small inputs each. Each test draws its own sizes, so the edge cases of size 1 and of ranges touching the last cell come up often.

Prompt for an AI tool:
Write C++17 code for a 2D difference array that supports rectangle add and a 2D prefix sum table
for rectangle sums. Use half-open rectangles [r1, r2) x [c1, c2). Write a brute force that paints
each cell directly. Generate 3000 random cases with n and m from 1 to 6, up to 5 paint operations
with values from -3 to 3, and 1 query per case. Print the number of mismatches. Use a fixed seed.
A good answer uses the four corner updates and an in-place 2D prefix sum over a grid with one extra
row and column. Check that the answer uses half-open ranges everywhere, that the brute force does not
share code with the fast version, and that the random generator never produces an empty range.

The test program for this lesson printed the following on the machine that wrote it. The harness itself is not shown in full here, and its loop structure is the same as the brute force comparisons described above:

1D range-add tests: 3000 cases, mismatches 0
2D rect-add tests: 3000 cases, mismatches 0
2D rect-sum queries: 3000 cases, mismatches 0
subarray-sum-k tests: 3000 cases, mismatches 0
subarrays of [1,-1,1,-1] with sum 0: 4

The brute force for the subarray count is an O(n^2) double loop over l and r, which is slow but obviously correct. Keep the brute force simple, even when it is slow. Its job is to be right, and the fast version has to agree with it.

Common mistakes and what they look like

The first mistake is a prefix array with n entries instead of n + 1. Writing pre[i + 1] = pre[i] + a[i] for i up to n - 1 then writes one past the end. Compiling the program with .at() in place of [] shows the error at once. This program does that on the example array, and printed:

terminate called after throwing an instance of 'std::out_of_range'
  what():  vector::_M_range_check: __n (which is 5) >= this->size() (which is 5)

The exact message depends on the standard library. This one comes from libstdc++ on the machine that wrote this lesson. Other libraries print different text.

The second mistake is reading a range as inclusive when the code is half-open. The function sum(l, r) = pre[r] - pre[l] treats r as exclusive. Calling it with sum(1, 4) and meaning "indices 1 to 4" gives the wrong answer. The run printed:

half-open sum(1, 4) = 6 (indices 1,2,3)
inclusive [1, 4] needs sum(1, 5) = 11 (indices 1..4)

The fix is to change the call, not the function. Keep one convention in one place.

The third mistake is applying the 2D corner update with the wrong sign or the wrong corner. It is easy to write D[r2][c2] -= v by accident. The random test catches this at once, because the rectangle edges no longer cancel. Without the random test, the sample cases often pass, since a single rectangle that touches the grid edge hides the error.

The fourth mistake is inserting into the hash map before the lookup in the subarray count. For a = [5] and k = 0, the correct answer is 0, because the only subarray sums to 5. If the insert comes first, the prefix 5 finds itself with pre - k = 5, and the program reports 1. That is the empty subarray being counted.

The fifth mistake is overflow in the sum. With values up to 10^9 and n up to 10^6, a 32-bit int overflows. The symptom is a wrong answer that looks random, not a crash. Use long long for every prefix and every sum.

Checklist

Decide the range convention once, write it in the names and the comments, and use it everywhere.
Check the array sizes: n + 1 for a prefix, (n + 1) x (m + 1) for a 2D table, with the padding row and column.
For a difference array, make sure the end update is at r, not r - 1, and that it is subtracted.
For 2D, check that all four corners of each rectangle are used and that the signs are +, -, -, +.
Put the hash map lookup before the insert when counting pairs of prefixes.
Use long long for sums and for every prefix value.
Run a random test against a brute force with empty ranges, size 1 inputs and ranges that touch the last index.
Check the output on the smallest input you can do by hand before you trust a larger one.

Practice

Try each problem on paper or in code before you open the answer. Each one uses the half-open convention.

Given a = [2, -1, 4, 0, 3], build the prefix array and find the sum over [1, 4). Hint: the prefix array has six entries.
Start with n = 6 and all zeros. Apply +1 to [0, 6), then +5 to [2, 4), then -2 to [4, 5). Give the final array using a difference array. Hint: find the index d[4] and add both of its updates.
Count the subarrays of a = [0, 0, 0] whose sum is 0. Hint: list the subarrays by length.
On a 2 by 2 grid of zeros, apply +1 to the whole grid, then +2 to rows [1, 2) and columns [0, 1). Give the final grid. Hint: which cell gets both updates?
Explain why the 2D difference array needs a padding row and column. Hint: where do the bottom-right corners of a rectangle that reaches the last row or column go?

Show the answer

The prefix array is 0, 2, 1, 5, 5, 8. The sum over [1, 4) is pre[4] - pre[1] = 5 - 2 = 3, which is -1 + 4 + 0.
The updates give d[0] = 1, d[6] = -1, d[2] = 5, d[4] = -5 + -2 = -7, d[5] = 2. The running sums are 1, 1, 6, 6, -1, 1, so the final array is [1, 1, 6, 6, -1, 1].
There are 6 subarrays, with lengths 1 (3 of them), 2 (2 of them) and 3 (1 of them). All have sum 0, so the answer is 6.
The cell at row 1, column 0 gets both updates. Its value is 1 + 2 = 3. The final grid is [[1, 1], [3, 1]].
A rectangle that reaches the last row has its bottom corners at row n. Those corners must be written somewhere, so the array needs row n. The same holds for the last column. The padding row and column absorb the corners, and the answer is read only from rows 0 to n - 1 and columns 0 to m - 1.

Summary

Prefix sums turn a range sum into two lookups, and difference arrays turn many range updates into two point updates each. Both need one fixed convention for ranges, and half-open ranges with n + 1 entries avoid most of the edge-case bugs. The 2D versions use inclusion-exclusion for queries and four corners for updates. The hash map version counts pairs of prefixes, and the lookup must come before the insert. Test each structure against a brute force on random small inputs before you rely on it.