Prefix sums

Prefix sums let a program answer many questions of the form "what is the sum of elements $l$ to $r$?" with one subtraction each, after one pass over the array. If the values change between the questions, use a Fenwick tree instead.

Explanation

A shop receipt has four lines: 3, 5, 2 and 4 euros. Next to each line the till prints the running total: 3, 8, 10 and 14. Each running total is the one before it plus the price on its line, for example 8 + 2 = 10.

Fig. 1. Each running total is the one before it plus the price on its line.

Now a group of friends shop together and pay with one receipt of 8 lines: 4, 2, 7, 1, 5, 3, 6 and 2 euros. Each friend's items went through the till one after another, so each friend's share is a range of lines in a row. Ann's items are lines 3 to 6. How much does she owe?

Fig. 2. Ann's items are lines 3 to 6, shaded blue.

Adding her lines, 7 + 1 + 5 + 3 = 16, is fine once. But a program may get a receipt of a million lines and a million such questions. Adding up each range again can take a million times a million, 10^{12} additions, which is far too slow. Most of that work adds the same lines over and over.

The till prints running totals on this receipt too: 4, 6, 13, 14, 19, 22, 28 and 30. The total next to line 6 is 22, everything up to and including line 6. Ann's lines start at line 3, so remove the total next to line 3, which is 13. That gives 22 − 13 = 9, but Ann's items cost 16. The 9 covers only lines 4, 5 and 6. The 13 included line 3 itself, so Ann's 7 euros were taken away together with lines 1 and 2.

Fig. 3. The totals at lines 6 and 3 are 22 and 13. Subtracting them leaves only the blue lines 4 to 6: the red line 3 is lost, so 7 euros of Ann's 16 are missing.

Which total holds exactly the lines before Ann's? The one next to line 2, the last line that isn't hers: 6. Now 22 − 6 = 16, the same as adding her lines. It works because the total at line 6 is the lines before Ann's plus Ann's lines, so removing the lines before leaves only hers.

A friend whose items start at line 1 has nothing before them. So write a 0 before the first total, as the total before anything was bought.

These running totals are the prefix sums of the array, the list of prices in order. One pass over the array builds them. Then each question about a range of elements in a row is answered with one subtraction: the prefix sum at its last element minus the prefix sum just before its first.

The steps below build all the prefix sums of the receipt and then answer Ann's question and two more.

The prefix sum before line 1 is 0: nothing has been bought yet.

Line 1 costs 4, so the prefix sum at line 1 is 0 + 4 = 4.

Line 2 costs 2, so the prefix sum at line 2 is 4 + 2 = 6.

Line 3 costs 7, so the prefix sum at line 3 is 6 + 7 = 13.

Line 4 costs 1, so the prefix sum at line 4 is 13 + 1 = 14.

Line 5 costs 5, so the prefix sum at line 5 is 14 + 5 = 19.

Line 6 costs 3, so the prefix sum at line 6 is 19 + 3 = 22.

Line 7 costs 6, so the prefix sum at line 7 is 22 + 6 = 28.

Line 8 costs 2, so the prefix sum at line 8 is 28 + 2 = 30.

Lines 3 to 6: the prefix sum at line 6 minus the one before line 3 gives 22 − 6 = 16.

Lines 1 to 4: the prefix sum at line 4 minus the one before line 1 gives 14 − 0 = 14.

Lines 5 to 8: the prefix sum at line 8 minus the one before line 5 gives 30 − 14 = 16.

1/12

Fig. 4. The prefix sums of the receipt. The dark blue prefix sum is the new one, and the light blue price and prefix sum are the two it is built from. In the last three steps, the light blue prices are the lines of a question and the two outlined prefix sums are the ones it subtracts.

The steps wrote 9 prefix sums, including the 0, with 8 additions, and then answered three questions with one subtraction each. The same 9 numbers answer every one of the 36 possible ranges of lines on this receipt.

Counting in a range

Prefix sums also count. Suppose lines 2, 4 and 5 of the receipt were on discount, and the question is how many of Ann's items were. Write 1 next to each discounted line and 0 next to the others: 0, 1, 0, 1, 1, 0, 0, 0. With the 0 in front, their prefix sums start 0, 0, 1, 1, 2.

With several kinds of items, one row of marks per kind counts each kind.

Implementation

In code, line i of the receipt is the element a[i], and its prefix sum is s[i], the sum of a[1] to a[i]. The 0 in front is s[0] = 0. The sum of elements l to r is s[r] - s[l - 1].

The elements are numbered from 1, as the lines of the receipt are. So the program reads them into a[1] to a[n] and leaves a[0] unused, and s has n + 1 cells, s[0] to s[n]. Then a question with l = 1 reads s[0] like any other cell.

1. Read: read n and the elements into a[1] to a[n].

2. Build: set s[0] = 0 and, for i from 1 to n, s[i] = s[i - 1] + a[i].

3. Answer: for each question l, r, print s[r] - s[l - 1].

The input gives n, then n numbers, then the number of questions q and q lines l r. For the 8-line receipt and the three questions from Fig. 4 it is:

8
4 2 7 1 5 3 6 2
3
3 6
1 4
5 8

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

int main() {
    // fast input: needed when there are a million numbers to read
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // read
    int n;
    cin >> n;
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    // build
    vector<long long> s(n + 1);
    s[0] = 0;
    for (int i = 1; i <= n; i++) s[i] = s[i - 1] + a[i];

    // answer
    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << s[r] - s[l - 1] << '\n';
    }
}

Building the prefix sums takes $O(n)$ time, one addition per element, and each question takes $O(1)$, one subtraction, so with q questions the program runs in O(n + q) instead of O(n \cdot q) for adding up each range.

Sums in a table

Prefix sums also work for a table a of n rows and m columns. Let P[i][j] be the sum of the rectangle from the top-left cell (1, 1) to the cell (i, j), with row 0 and column 0 filled with zeros. Fig. 5 shows a table of 4 rows and 5 columns, with its table P on the right.

The question is the sum of rows 2 to 3, columns 2 to 4: 2 + 6 + 5 + 8 + 9 + 7 = 37. Start with the big rectangle up to (3, 4), P[3][4] = 60. Remove the rows above, the rectangle up to (1, 4) with P[1][4] = 9, and the columns to the left, the rectangle up to (3, 1) with P[3][1] = 17. The corner up to (1, 1), P[1][1] = 3, is in both of them, so it was removed twice and is added back once: 60 − 9 − 17 + 3 = 37.

Fig. 5. The table a and its table P. The dark blue 60 and 3 are added and the light blue 9 and 17 are subtracted: 60 − 9 − 17 + 3 = 37. The corner 3 is inside both subtracted rectangles, so it is added back once.

The table P is built row after row, and each cell needs the same add-back. For example, P[2][2] = a[2][2] + P[1][2] + P[2][1] - P[1][1] = 2 + 4 + 12 − 3 = 15: the corner 3 is inside both P[1][2] and P[2][1]. In general P[i][j] = a[i][j] + P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1], and the sum of rows r1 to r2 and columns c1 to c2 is P[r2][c2] - P[r1 - 1][c2] - P[r2][c1 - 1] + P[r1 - 1][c1 - 1].

Each question is a line r1 c1 r2 c2. For the question above the input is:

4 5
3 1 4 1 5
9 2 6 5 3
5 8 9 7 9
3 2 3 8 4
1
2 2 3 4

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // read
    int n, m;
    cin >> n >> m;
    vector<vector<long long>> a(n + 1, vector<long long>(m + 1));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) cin >> a[i][j];

    // build
    vector<vector<long long>> P(n + 1, vector<long long>(m + 1, 0));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            P[i][j] = a[i][j] + P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1];

    // answer
    int q;
    cin >> q;
    while (q--) {
        int r1, c1, r2, c2;
        cin >> r1 >> c1 >> r2 >> c2;
        cout << P[r2][c2] - P[r1 - 1][c2] - P[r2][c1 - 1] + P[r1 - 1][c1 - 1] << '\n';
    }
}

Building P takes O(n \cdot m) time, and each question takes $O(1)$.

Adding to a range: the difference array

Sometimes all the changes come before the questions. A small hotel has nights 1 to 8 and three bookings: 3 guests for nights 2 to 5, 2 guests for nights 4 to 7, and 1 guest for nights 1 to 3. How many guests sleep in the hotel each night? Writing each booking into every night it covers takes $O(n)$ per booking. An extra array and its prefix sums do it with two changes per booking.

For each booking "add x to nights l to r", make two marks in an array d: d[l] += x where the booking starts, and d[r + 1] -= x right after it ends. Then take the prefix sums of d. The +x enters the sum at night l and stays in it until the -x cancels it at night r + 1, so each night from l to r gets exactly x more. This array of marks is the difference array.

For the hotel the marks are +3 at 2 and −3 at 6, +2 at 4 and −2 at 8, +1 at 1 and −1 at 4. After all of them, d[1] to d[9] are 1, 3, 0, 1, 0, −3, 0, −2, 0. Their prefix sums give 1, 4, 4, 5, 5, 2, 2, 0 guests on nights 1 to 8. On night 4 the prefix sum is 1 + 3 + 0 + 1 = 5: the single guest's +1 was cancelled by the −1 at night 4, and the 3-guest and 2-guest bookings are both still counted.

Fig. 6. Each booking puts a plus where it starts and a minus right after it ends: the first booking's +3 at 2 and −3 at 6 are dark blue. The prefix sums of the marks, in the bottom row, give the number of guests on each night; night 4 has 5.

Each change is a line l r x, and the program prints the final value of every element. Index r + 1 can be n + 1, so d has n + 2 cells. For the hotel the input is:

8 3
2 5 3
4 7 2
1 3 1

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // read
    int n, k;
    cin >> n >> k;
    vector<long long> d(n + 2, 0);

    // mark
    for (int j = 0; j < k; j++) {
        int l, r;
        long long x;
        cin >> l >> r >> x;
        d[l] += x;
        d[r + 1] -= x;
    }

    // build
    vector<long long> s(n + 1, 0);
    for (int i = 1; i <= n; i++) s[i] = s[i - 1] + d[i];

    // answer
    for (int i = 1; i <= n; i++) cout << s[i] << (i < n ? ' ' : '\n');
}

Each change takes $O(1)$ and the prefix sums take $O(n)$, so k changes cost O(n + k). This only works when all the changes come before the questions. In a table, a rectangle gets four marks: +x at (r1, c1), -x at (r1, c2 + 1) and at (r2 + 1, c1), and +x at (r2 + 1, c2 + 1); the table P of the marks then gives the final values.

Common mistakes

• Leaving s[0] unset in a local array, so every question with l = 1 prints garbage. Use a vector, which starts filled with zeros, or set s[0] = 0.

• Keeping the prefix sums in int, which overflows as soon as a sum passes about 2.1 \cdot 10^9. Use long long for s and for the answer.

• Leaving out - P[i - 1][j - 1] in the build line of a table, so the corner is counted twice and every prefix sum is too big. Subtract the corner, as in the formula above.

• Forgetting d[r + 1] -= x in a difference array, so every booking seems to last until the end. Make both marks for each change.

Similar techniques

A Fenwick tree or a segment tree is needed when changes and questions are mixed, such as "set element $i$ to $x$" followed by a sum. Suppose line 4 of the receipt changes from 1 euro to 6 after the prefix sums are written. Then 22 − 6 still says Ann owes 16, but she now owes 21: the prefix sums at lines 4 to 8 all hold the old price. Rebuilding them takes $O(n)$ after each change; these structures do both a change and a question in O(\log n).

A sparse table answers the minimum or maximum of a range in $O(1)$. A minimum can't be subtracted away, so prefix sums don't help there.

Two pointers find a window that grows and shrinks, such as the shortest range with sum at least $X$ when no number is negative. Prefix sums give the sum of a window once it is chosen; two pointers choose the window.

XOR undoes itself the way subtraction undoes addition, so prefix sums also work with XOR in place of addition: the XOR of elements $l$ to $r$ is the prefix XOR at $r$ XOR the prefix XOR at l - 1.

Practice