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 × mgrid of plots;a[i][j]is the harvest of the plot in rowi, columnj. Answerqquestions: 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 31 2 3 45 6 7 89 1 2 32 2 3 31 1 3 41 3 2 4 |
165122 |
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).
qdrones each addxkg 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
-
Count
#cells in rectangles of a character grid.Answer
Use <code>a[i][j] = (grid[i][j] == '#')</code> and the same 2D prefix table. -
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). -
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. -
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
- Sum of any submatrix, many times? Build a 2D prefix table in O(n·m); each query is O(1) with inclusion-exclusion.
- Explain inclusion-exclusion for two sets. |A ∪ B| = |A| + |B| − |A ∩ B|; the rectangle query is the same idea for overlapping strips.
- Add a value to many rectangles, then print the matrix? 2D difference array: 4 marks per update, one 2D prefix sweep.
- 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.