Chapter 9: Prefix Sum & Difference Array

These two techniques are inverse operations:

• Prefix sum helps you query ranges quickly.
• Difference array helps you apply range updates quickly.

9.1 1D Prefix Sum: O(1) Range Queries

Let the original array be A. Define a prefix sum array S where S[i] equals the sum of the first i elements:

$S[i] = A[1] + A[2] + \dots + A[i]$

9.1.1 Recurrence

$S[i] = S[i-1] + A[i]$

(We usually index from 1 for convenience and let S[0] = 0.)

9.1.2 Core Trick

To compute the sum of A[l] through A[r]:

$Sum(l, r) = S[r] - S[l-1]$

Template

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    int n, m;
    cin >> n >> m;
    vector<long long> s(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        s[i] = s[i - 1] + x;
    }
    while (m--) {
        int l, r;
        cin >> l >> r;
        cout << s[r] - s[l - 1] << '\n';
    }
    return 0;
}

9.2 2D Prefix Sum: Matrix Queries

Problem: given a matrix, find the sum of elements in the submatrix defined by (x1, y1) to (x2, y2).

Extend the 1D idea: let S[i][j] be the sum of the rectangle from (1, 1) to (i, j).

Construction formula (Principle of Inclusion-Exclusion)

$S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + A[i][j]$

• Add the top rectangle S[i-1][j].
• Add the left rectangle S[i][j-1].
• Subtract the overlapped top-left S[i-1][j-1].
• Add the current cell A[i][j].

Query

To get the sum of (x1, y1) through (x2, y2):

$Sum = S[x2][y2] - S[x1 - 1][y2] - S[x2][y1 - 1] + S[x1 - 1][y1 - 1]$

You subtract the top and left extras, then add back the top-left corner that was subtracted twice.

9.3 1D Difference Array: O(1) Range Updates

Problem: start with an array of zeros. Perform M operations, each adding V to all elements in [l, r]. At the end, output the array.

Brute force takes O(MN). A difference array works in O(M).

Definition

The difference array D is the inverse of prefix sum:

$D[i] = A[i] - A[i-1]$

Core operations

To add V to [l, r], touch only two points:

1. D[l] += V → from l onward, the prefix sums rise by V.
2. D[r+1] -= V → from r+1 onward, cancel the earlier increment.

Code

vector<int> d(20, 0);
 
void add(int l, int r, int v) {
    d[l] += v;
    d[r + 1] -= v;
}
 
int main() {
    add(2, 5, 3);
    add(4, 8, -2);
    vector<int> a(20);
    for (int i = 1; i <= 10; i++) {
        a[i] = a[i - 1] + d[i];
        cout << a[i] << " ";
    }
}

Perform a prefix sum over D to recover A.

9.4 2D Difference Array

Problem: add V to every number in the submatrix (x1, y1) to (x2, y2).

Analogous to 1D, touch four corners:

1. D[x1][y1] += V
2. D[x1][y2+1] -= V
3. D[x2+1][y1] -= V
4. D[x2+1][y2+1] += V

After all updates, run a 2D prefix sum over D to produce the final matrix.

🧠 Summary & Practice

Prefix sums and difference arrays are the go-to tools for range queries and updates.

• Many queries, few updates → use prefix sum.
• Many updates, final single query → use difference array.

Question: What if you need frequent updates and frequent queries? Prefix sums are too slow (O(N) per update). You must move on to segment trees or Fenwick trees (covered later).

Exercises:

1. P8218 Range Sum (Luogu): a template for 1D prefix sums.
2. P1719 Maximum Weighted Rectangle: apply 2D prefix sums to optimize O(N^4) down to O(N^3).
3. P2367 Chinese Score: a classic difference array problem (range addition).

Once you master array techniques, it is time to reason about sets: how to quickly tell if two elements share the same group? How to merge two factions? Stay tuned for union-find.