Prefix Sums and Difference Arrays

10 Sep 2024

1. Introduction

Prefix sums and difference arrays are two fundamental techniques for range problems. They both turn work over an entire interval into work at a few positions:

Prefix sums are suitable for many range queries.
Difference arrays are suitable for many range updates.

When an array and the number of operations are both large, scanning every element in each interval is usually too slow. A prefix sum answers one range-sum query in O(1) after O(n) preprocessing. A difference array records one range update in O(1), then restores the final array with one O(n) pass.

The key distinction is when the work is done. A prefix sum computes accumulated values in advance so later queries are fast. A difference array records changes only at interval boundaries and applies their effects together at the end. Before choosing either technique, first identify whether the problem repeatedly asks about intervals or repeatedly changes them.

2. Prefix Sums

2.1 Principle

Let the original array be a[1], a[2], ..., a[n]. Define the prefix-sum array s as follows:

s[0] = 0
s[i] = s[i - 1] + a[i]

Here, s[i] is the sum of the first i elements. The sum over an interval [l, r] is therefore:

a[l] + a[l + 1] + ... + a[r] = s[r] - s[l - 1]

For example, if the array is [2, 1, 3, 4, 2], its prefix sums are [0, 2, 3, 6, 10, 12]. To find the sum of [2, 4], there is no need to calculate 1 + 3 + 4 again. Instead, calculate s[4] - s[1] = 10 - 2 = 8.

The subtraction removes the part of the array that comes before the required interval. s[r] contains elements 1 through r, while s[l - 1] contains elements 1 through l - 1. Their difference leaves exactly the elements from l through r. Setting s[0] to 0 also means that the same formula works when l is 1.

2.2 Range-Sum Queries

The following program reads an array and answers q range-sum queries. Building the prefix sums takes O(n), and each query takes O(1).

#include <bits/stdc++.h>
using namespace std;

const int N = 100000 + 10;
long long a[N], s[N];

int main() {
    int n, q;
    cin >> n >> q;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }

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

The prefix sums use long long. Even when one element fits in an int, the sum of many elements may not.

The trade-off is that changing one value in the original array can change many later prefix sums. Prefix sums are therefore best for a static array that is read once and queried many times.

3. Difference Arrays

3.1 Principle

A difference array records the change between adjacent elements:

d[1] = a[1]
d[i] = a[i] - a[i - 1]  (i > 1)

Taking a prefix sum of the difference array restores the original array:

a[i] = d[1] + d[2] + ... + d[i]

Its most useful basic application is range addition. To add v to every value in [l, r], make only these two changes:

d[l] += v
d[r + 1] -= v

Why does this work? From position l onward, the prefix sum is v larger than before. At position r + 1, subtracting v cancels that effect, so the change stops immediately after r. Each range update therefore takes O(1).

For example, the difference array of [3, 5, 2, 6, 4] is [3, 2, -3, 4, -2]. To add 10 to [2, 4], change only d[2] += 10 and d[5] -= 10. The difference array becomes [3, 12, -3, 4, -12]. Its prefix sums are [3, 15, 12, 16, 4], so only positions 2 through 4 increased by 10.

Because r + 1 can be n + 1, allocate one extra array position. When restoring the result, iterate only through n.

3.2 Example: Range Addition, Then Find the Minimum

The following program reads initial scores, performs several range additions, restores every final score, and finds the minimum.

While reading the initial array, the program uses d[i] += x and d[i + 1] -= x. This treats the value x at position i as a one-element update over [i, i], so the initial values and all later updates can be handled in the same difference array.

#include <bits/stdc++.h>
using namespace std;

const int N = 5000000 + 20;
long long d[N];

int main() {
    int n, q;
    cin >> n >> q;

    for (int i = 1; i <= n; i++) {
        long long x;
        cin >> x;
        d[i] += x;
        d[i + 1] -= x;
    }

    while (q--) {
        int l, r;
        long long v;
        cin >> l >> r >> v;
        d[l] += v;
        d[r + 1] -= v;
    }

    long long answer = LLONG_MAX;
    for (int i = 1; i <= n; i++) {
        d[i] += d[i - 1];
        answer = min(answer, d[i]);
    }

    cout << answer;
    return 0;
}

4. How to Choose

Use a prefix sum when the array barely changes but you need many range sums.
Use a difference array when you need many range additions and can restore the array after all updates.

A basic difference array is intended for the second situation: apply all updates first, then restore the final result. If a problem requires an updated range sum immediately after every change, it is outside the basic setting covered here.

Prefix sums and difference arrays are simple ideas, but they establish an important habit: represent an interval through accumulated values or boundary changes instead of processing every element in it.

Prefix Sums and Difference Arrays

Related Posts