SyntaxPilot
Courses/Competitive Programming/Lesson 8

Competitive Programming · Lesson 8 of 90 · 10 min

2D prefix sums and range updates

queued

These are the notes for Competitive Programming episode 8. Episode 7's prefix sums answered range sums on a line; here we answer rectangle sums on a grid in O(1) with a 2D prefix table, built and queried with inclusion-exclusion (pictured as cropping a photo). Then the reverse: adding to whole rectangles with four corner marks and one 2D sweep, the 2D difference array. You also see a bug the sample almost hides. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.

The problem: Farm Survey

Problem H · Farm Survey (written for this course). A farm is an n × m grid of plots; a[i][j] is the harvest of the plot in row i, column j. Answer q questions: the total harvest of the rectangle with top-left (r1, c1) and bottom-right (r2, c2).

1 ≤ n, m ≤ 1000, 1 ≤ q ≤ 2·10^5, 0 ≤ a[i][j] ≤ 10^9.

Sample input Sample output
3 4 3
1 2 3 4
5 6 7 8
9 1 2 3
2 2 3 3
1 1 3 4
1 3 2 4
16
51
22

Brute force

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<ll>> a(n + 1, vector<ll>(m + 1));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) cin >> a[i][j];
    while (q--) {
        int r1, c1, r2, c2;
        cin >> r1 >> c1 >> r2 >> c2;
        ll sum = 0;
        for (int i = r1; i <= r2; i++)
            for (int j = c1; j <= c2; j++) sum += a[i][j];
        cout << sum << '\n';
    }
    return 0;
}

Correct on the sample (16 51 22), but a question can cover 10^6 cells: q · n · m = 2·10^11. A max test made in code (n = m = 1000, q = 2·10^5, near-full rectangles) got Time Limit Exceeded in the SyntaxPilot compiler.

A prefix sum per row (episode 7) still costs up to n = 1000 steps per question: 2·10^8 in total, risky. We want O(1).

The idea: cropping a photo (inclusion-exclusion)

Cropping a printed photo (only corner cuts allowed) In a grid
Start with the big piece from the corner to the crop's bottom-right P[r2][c2]
Cut off the top strip and the left strip − P[r1−1][c2] − P[r2][c1−1]
The small corner piece was in both cuts: add it back once + P[r1−1][c1−1]

Inclusion-exclusion: add, subtract, then add back what was subtracted twice.

On the sample, rows 2..3, columns 2..3:

big     P[3][3] = 1+2+3+5+6+7+9+1+2 = 36
top     P[1][3] = 1+2+3             = 6
left    P[3][1] = 1+5+9             = 15
corner  P[1][1] = 1
answer  36 − 6 − 15 + 1 = 16        (6 + 7 + 1 + 2)

2D prefix sums

P[i][j] = sum of the rectangle from (1, 1) to (i, j). Row 0 and column 0 are zeros.

P[i][j] = a[i][j] + P[i−1][j] + P[i][j−1] − P[i−1][j−1]
sum(r1, c1, r2, c2) = P[r2][c2] − P[r1−1][c2] − P[r2][c1−1] + P[r1−1][c1−1]

The sample's table:

P col 1 col 2 col 3 col 4
row 1 1 3 6 10
row 2 6 14 24 36
row 3 15 24 36 51

P[2][2] = 6 + 3 + 6 − 1 = 14 (check: 1 + 2 + 5 + 6). P[3][4] = 51, the whole farm.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<ll>> P(n + 1, vector<ll>(m + 1, 0));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            ll x;
            cin >> x;
            P[i][j] = x + P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1];
        }
    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';
    }
    return 0;
}

Sample → 16 51 22. The same max test with the table printed total 725528407750, time 9 ms.

Memory: (n+1)(m+1) long longs ≈ 8 MB for n = m = 1000. Fine for 256 MB.

The missing-corner bug (real output)

Forgetting + P[r1 - 1][c1 - 1]:

15
51
22

Only the first answer is wrong, by exactly the corner cell (1). The other two rectangles start in row 1 or column 1, where the corner term is a zero from row 0 / column 0. A sample made only of such rectangles would pass with this bug. Episode 5's stress test (random rectangles vs the brute force) catches it immediately.

The reverse problem: Spray Drones

Problem H2 · Spray Drones (written for this course). q drones each add x kg of fertiliser to every plot of a rectangle (r1, c1)..(r2, c2). Print the total on every plot.

Four corner marks

D[r1][c1]       += x    // start: spreads right and down
D[r1][c2+1]     −= x    // stop spreading right
D[r2+1][c1]     −= x    // stop spreading down
D[r2+1][c2+1]   += x    // that corner was stopped twice: add back

Then a 2D prefix sum of D (the same build formula) gives the final grid. The marks reach row n+1 and column m+1, so D is (n+2) × (m+2).

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<ll>> D(n + 2, vector<ll>(m + 2, 0));
    while (q--) {
        int r1, c1, r2, c2;
        ll x;
        cin >> r1 >> c1 >> r2 >> c2 >> x;
        D[r1][c1] += x;
        D[r1][c2 + 1] -= x;
        D[r2 + 1][c1] -= x;
        D[r2 + 1][c2 + 1] += x;
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            D[i][j] += D[i - 1][j] + D[i][j - 1] - D[i - 1][j - 1];
            cout << D[i][j] << " \n"[j == m];
        }
    return 0;
}

Input 3 5 2 / 1 1 2 3 5 / 2 2 3 4 2:

5 5 5 0 0
5 7 7 2 0
0 2 2 2 0

The overlap (rows 2, columns 2..3) gets 5 + 2 = 7. The in-place sweep works because, in row-major order, D[i−1][j], D[i][j−1] and D[i−1][j−1] are already prefix sums when D[i][j] is computed.

Solutions in C++, Java and Python (Farm Survey)

C++: the 2D prefix program above.

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        DataInputStream in = new DataInputStream(new BufferedInputStream(System.in, 1 << 16));
        StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(in)));
        st.nextToken(); int n = (int) st.nval;
        st.nextToken(); int m = (int) st.nval;
        st.nextToken(); int q = (int) st.nval;
        long[][] P = new long[n + 1][m + 1];
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) {
                st.nextToken();
                P[i][j] = (long) st.nval + P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1];
            }
        StringBuilder out = new StringBuilder();
        while (q-- > 0) {
            st.nextToken(); int r1 = (int) st.nval;
            st.nextToken(); int c1 = (int) st.nval;
            st.nextToken(); int r2 = (int) st.nval;
            st.nextToken(); int c2 = (int) st.nval;
            out.append(P[r2][c2] - P[r1 - 1][c2] - P[r2][c1 - 1] + P[r1 - 1][c1 - 1]).append('\n');
        }
        System.out.print(out);
    }
}

Python

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n, m, q = int(data[0]), int(data[1]), int(data[2])
    pos = 3
    P = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        row, up = P[i], P[i - 1]
        for j in range(1, m + 1):
            row[j] = int(data[pos]) + up[j] + row[j - 1] - up[j - 1]
            pos += 1
    out = []
    for _ in range(q):
        r1, c1, r2, c2 = (int(x) for x in data[pos:pos + 4])
        pos += 4
        out.append(P[r2][c2] - P[r1 - 1][c2] - P[r2][c1 - 1] + P[r1 - 1][c1 - 1])
    print("\n".join(map(str, out)))

main()

(Python builds 10^6 cells in about a second; for tight limits use C++.)

Brute force vs optimal

Brute force Prefix per row 2D prefix / 2D difference
Per query / update O(n·m) O(n) O(1)
Preprocessing none O(n·m) O(n·m)
Total at n = m = 1000, q = 2·10^5 2·10^11 (TLE) 2·10^8 (risky) ≈ 1.2·10^6
Extra memory none (n)(m+1) (n+1)(m+1) or (n+2)(m+2)

Common mistakes (and the real messages)

Mistake What you see Why Fix
No + P[r1-1][c1-1] 15 51 22 instead of 16 51 22 corner subtracted twice add the corner back
P[r1][c2], P[r2][c1] wrong answers removes row r1 / column c1 of your own rectangle use r1 − 1, c1 − 1
D of size (n+1) × (m+1) out-of-bounds (with _GLIBCXX_DEBUG) or silent corruption D[r2+1][c2+1] with r2 = n size (n+2) × (m+2)
int grid negative or wrong sums 10^6 cells × 10^9 = 10^15 long long
Build without − P[i−1][j−1] table too big corner counted twice the 4-term build formula

Mini project: best k × k plot

Find the k × k square with the largest harvest. With the 2D table, each of the (n−k+1)(m−k+1) squares costs O(1):

ll best = LLONG_MIN;
for (int i = k; i <= n; i++)
    for (int j = k; j <= m; j++)
        best = max(best, P[i][j] - P[i - k][j] - P[i][j - k] + P[i - k][j - k]);

On the sample with k = 2, the best square is rows 1..2, columns 3..4: 3 + 4 + 7 + 8 = 22.

Practice

  1. Count # cells in rectangles of a character grid.

    Answer Use <code>a[i][j] = (grid[i][j] == '#')</code> and the same 2D prefix table.

  2. Write the sum of rows 2..3, columns 3..4 of the sample, using the table.

    Answer P[3][4] − P[1][4] − P[3][2] + P[1][2] = 51 − 10 − 24 + 3 = 20 (7 + 8 + 2 + 3).

  3. After Spray Drones, answer rectangle-sum questions on the result.

    Answer Build the final grid with the 2D difference array, then build a 2D prefix table of that grid. O(n·m + q) overall.

  4. What goes wrong if a question gives r1 > r2 (corners in the wrong order)?

    Answer It is not: the formula assumes r1 ≤ r2 and c1 ≤ c2. Normalise with <code>if (r1 > r2) swap(r1, r2);</code> when the input does not guarantee it.

Quick quiz

P[i][j] = sum of (1,1)..(i,j). Which formula gives the sum of rows 2..3, columns 3..4?

A) P[3][4] − P[2][4] − P[3][3] + P[2][3] · B) P[3][4] − P[1][4] − P[3][2] + P[1][2] · C) P[3][4] − P[1][4] − P[3][2] − P[1][2] · D) P[3][4] − P[2][3]

Answer

B. Subtract the strip above (row r1 − 1 = 1) and the strip to the left (column c1 − 1 = 2), then add back the corner P[1][2].

Interview questions

  1. Sum of any submatrix, many times? Build a 2D prefix table in O(n·m); each query is O(1) with inclusion-exclusion.
  2. Explain inclusion-exclusion for two sets. |A ∪ B| = |A| + |B| − |A ∩ B|; the rectangle query is the same idea for overlapping strips.
  3. Add a value to many rectangles, then print the matrix? 2D difference array: 4 marks per update, one 2D prefix sweep.
  4. Largest-sum k × k square? 2D prefix sums and an O(1) check per square: O(n·m).

Glossary

Term Meaning Example
Grid / matrix A table of values in rows and columns the 3 × 4 farm
Submatrix / rectangle query Sum over rows r1..r2 and columns c1..c2 (2,2)-(3,3) → 16
2D prefix sum P[i][j] = sum of (1,1)..(i,j) P[2][2] = 14
Inclusion-exclusion Add, subtract, add back what was subtracted twice 36 − 6 − 15 + 1
Strip The rows above or the columns left of a rectangle P[r1−1][c2]
2D difference array Corner marks whose 2D prefix sum is the updated grid +x, −x, −x, +x
Row-major order Filling a grid row by row, left to right the build loops
In place Overwriting an array with its result D[i][j] += …
Normalise Reorder inputs to fit the formula's assumptions swap so r1 ≤ r2

Summary

  • Rectangle sums by looping cost O(q·n·m); a 2D prefix table makes each one O(1).
  • Build: P = a + above + left − corner. Query: P[r2][c2] − P[r1−1][c2] − P[r2][c1−1] + P[r1−1][c1−1].
  • Row 0 and column 0 are zeros; use long long.
  • Rectangle updates: four corner marks, then one 2D prefix sweep; size (n+2) × (m+2).
  • Samples can hide the missing-corner bug: stress-test.

Next episode: coordinate compression: huge coordinates, small arrays.