Prefix Sums and the Difference Array

Lesson 2 of 7 · Advanced techniques

If we have to compute the sum of a part of an array many times, we do not add everything up again each time: we compute the sums of all initial parts of the array once (the prefix sums), and then we get the sum of any part with one subtraction, in O(1) time.

Before you start: prior knowledge you need – arrays, matrices.
How to learn: retype and run every example, and solve the tasks at the end on your own first; open the hint and the solution only after that. All programs are in C++.

Prefix sums

For an array a[1..n] we define p[0] = 0 and p[i] = a[1] + a[2] + … + a[i]. It is computed in one pass: p[i] = p[i − 1] + a[i]. The sum of the part from l to r is then

a[l] + … + a[r] = p[r] − p[l − 1]

i0123456
a[i]314159
p[i]034891423

For example, the sum a[2..5] = 1 + 4 + 1 + 5 = 11 = p[5] − p[1] = 14 − 3.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<long long> p(n + 1, 0);          // p[0] = 0
    for (int i = 1; i <= n; i++) {
        long long x;
        cin >> x;
        p[i] = p[i - 1] + x;                // the sum of the first i elements
    }
    while (q--) {
        int l, r;
        cin >> l >> r;                      // positions start from 1
        cout << p[r] - p[l - 1] << "\n";    // the sum a[l..r] in O(1)
    }
    return 0;
}

For the array from the table and the queries 2 5 and 1 6 the program prints 11 and 23.

The preparation takes O(n), and every query O(1) – O(n + q) in total instead of O(n · q). Indexing from 1 and p[0] = 0 remove the special case for l = 1.

The difference array: adding on an interval

The reverse problem: many times we have to add the value v to all elements from l to r, and the array is printed only at the end. Instead of changing all the elements, we write d[l] += v and d[r + 1] −= v into a helper array d. At the end, the prefix sums of the array d give how much was added to every element.

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

int main() {
    int n, q;
    cin >> n >> q;
    vector<long long> a(n + 2, 0), d(n + 2, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];
    while (q--) {
        int l, r;
        long long v;
        cin >> l >> r >> v;
        d[l] += v;                      // adding starts at l
        d[r + 1] -= v;                  // and stops after r
    }
    long long added = 0;
    for (int i = 1; i <= n; i++) {
        added += d[i];                  // the prefix sum of the difference array
        cout << a[i] + added << " ";
    }
    cout << endl;
    return 0;
}

For the input 5 2 / 1 1 1 1 1 / 1 3 2 / 2 5 10 the program prints 3 13 13 11 11.

Prefix sums in a matrix

For a matrix a[1..n][1..m] let p[i][j] be the sum of the rectangle from (1, 1) to (i, j):

p[i][j] = a[i][j] + p[i−1][j] + p[i][j−1] − p[i−1][j−1]

(we added the upper and the left part, and their common part was counted twice, so we subtract it). The sum of the rectangle from (x1, y1) to (x2, y2):

p[x2][y2] − p[x1−1][y2] − p[x2][y1−1] + p[x1−1][y1−1]

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

int main() {
    int n, m, q;
    cin >> n >> m >> q;
    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++) {
            long long x;
            cin >> x;
            p[i][j] = x + p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1];
        }
    while (q--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << p[x2][y2] - p[x1 - 1][y2] - p[x2][y1 - 1] + p[x1 - 1][y1 - 1] << "\n";
    }
    return 0;
}

For the 3×3 matrix 1 2 3 / 4 5 6 / 7 8 9 and the query 2 2 3 3 the program prints 28 (5 + 6 + 8 + 9).

Practice tasks

Every task has an example, a hint and a solution. The solutions have been checked on the examples in the text.

TASK 01Difficulty: harder

Parts with a sum of exactly K

We are given an array of n integers (they may also be negative, 1 ≤ n ≤ 2·105) and a number K. How many contiguous parts of the array have a sum of exactly K?

Example 1

Input

5 3
1 2 1 -1 3

Output

5

Example 2

Input

3 0
0 0 0

Output

6
TASK 02Difficulty: easy

The best k days in a row

We are given the earnings for n days and a number k (1 ≤ k ≤ n ≤ 106). Print the largest total earnings for k consecutive days.

Example

Input

7 3
2 -1 4 5 -3 6 1

Output

8
Common mistakes and tips
  • Store prefix sums in long long – the sum of 105 numbers up to 109 goes beyond the range of int.
  • The sum a[l..r] is p[r] − p[l − 1], not p[r] − p[l].
  • The difference array must also have room for d[r + 1], i.e. a size of at least n + 2.
  • Prefix sums do not help if the array changes between queries – then a Fenwick tree (SR) is used.

Check your knowledge

Open the quiz

Prefix sums

1. How is the sum a[l..r] computed with prefix sums?




2. How long does one sum query take after the preparation?




3. What is the difference array used for?