I. In-Class Exercises

Programming Exercises

1. Arithmetic Skill Test 2: L2211
2. Territory Selection: L2212

II. Knowledge Summary

✨ Core Concepts of 2D Prefix Sum

2D Prefix Sum is the extension of 1D prefix sum to two dimensions, used to efficiently compute the sum of elements in any rectangular region of a 2D array.

Core idea:

1. Preprocessing phase: Build a prefix sum array where prefix[i][j] stores the sum of all elements from the top-left corner (1,1) to (i,j)
2. Query phase: Use the prefix sum array to compute the sum of any rectangular region in O(1) time

✨ Inclusion-Exclusion Principle

The inclusion-exclusion principle is the mathematical foundation of 2D prefix sum, used in both building and querying.

Inclusion-Exclusion When Building the Prefix Sum

To compute prefix[i][j] (the total sum from (1,1) to (i,j)), we can piece it together from already computed prefix sums:

1+-------+-------+
2|       |       |
3|   A   |   B   |
4|       |       |
5+-------+-------+
6|       | (i,j) |
7|   C   |   D   |
8|       |       |
9+-------+-------+

• prefix[i-1][j] = A + B (above)
• prefix[i][j-1] = A + C (left)
• prefix[i-1][j-1] = A (top-left corner)

Above + Left = (A+B) + (A+C) = A+B+C + one extra A, so we subtract the top-left corner, then add the current cell D's value a[i][j].

Build formula:

prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + a[i][j];

Inclusion-Exclusion When Querying a Range Sum

To compute the sum of the rectangular region from (x1, y1) to (x2, y2), the approach is similar — subtract the excess from the larger rectangle:

1+-------+-------+
2|       |       |
3|   A   |   B   |
4|       |       |
5+-------+-------+
6|       |///////|
7|   C   |// D //|  <-- D is the target region
8|       |///////|
9+-------+-------+

• prefix[x2][y2] = A+B+C+D (total)
• prefix[x1-1][y2] = A+B (excess above)
• prefix[x2][y1-1] = A+C (excess left)
• prefix[x1-1][y1-1] = A (top-left corner, subtracted one extra time, needs to be added back)

Query formula:

sum = prefix[x2][y2] - prefix[x1-1][y2] - prefix[x2][y1-1] + prefix[x1-1][y1-1];

✨ Code Implementation of 2D Prefix Sum

Convention: Array indices start from 1 for data storage. Row 0 and column 0 serve as boundaries (with value 0), so computing prefix[i-1][j] does not go out of bounds.

1#include <bits/stdc++.h>
2using namespace std;
3
4int a[1005][1005];
5int prefix[1005][1005];
6
7int main() {
8    int n, m, q;
9    cin >> n >> m >> q;
10
11    // Read data (indices start from 1)
12    for (int i = 1; i <= n; ++i)
13        for (int j = 1; j <= m; ++j)
14            cin >> a[i][j];
15
16    // Build prefix sum
17    for (int i = 1; i <= n; ++i)
18        for (int j = 1; j <= m; ++j)
19            prefix[i][j] = prefix[i-1][j] + prefix[i][j-1]
20                         - prefix[i-1][j-1] + a[i][j];
21
22    // Process q queries
23    while (q--) {
24        int x1, y1, x2, y2;
25        cin >> x1 >> y1 >> x2 >> y2;
26        int sum = prefix[x2][y2] - prefix[x1-1][y2]
27                - prefix[x2][y1-1] + prefix[x1-1][y1-1];
28        cout << sum << endl;
29    }
30    return 0;
31}

✨ Complexity Analysis of 2D Prefix Sum

If there are q queries, the brute force approach requires O(n x m) per query to traverse the rectangular region, totaling O(q x n x m). With prefix sum, preprocessing takes O(n x m) + queries take O(q), which is a significant advantage when q is large.

✨ Execution Examples for 2D Prefix Sum

Using a 3x4 array as an example, here is the complete build and query process.

Original array a (indices start from 1):

        Col 1  Col 2  Col 3  Col 4
Row 1  [  1    2    3    4  ]
Row 2  [  5    6    7    8  ]
Row 3  [  9   10   11   12  ]

Step 1: Build the Prefix Sum Array

Compute row by row, column by column, applying the formula prefix[i][j] = above + left - top-left + current at each step:

Prefix sum array:

        Col 1  Col 2  Col 3  Col 4
Row 1  [  1    3    6   10  ]
Row 2  [  6   14   24   36  ]
Row 3  [ 15   33   54   78  ]

The meaning of prefix[i][j]: the sum of all elements from (1,1) to (i,j). For example, prefix[2][3] = 24 = 1+2+3+5+6+7 = 24.

Step 2: Query a Range Sum

Query: sum of the rectangular region from (2,2) to (3,4)

Target region:

        Col 2  Col 3  Col 4
Row 2  [  6    7    8  ]
Row 3  [ 10   11   12  ]

Applying the formula:

sum = prefix[3][4] - prefix[1][4] - prefix[3][1] + prefix[1][1]
    = 78         - 10         - 15         + 1
    = 54

Verification: 6 + 7 + 8 + 10 + 11 + 12 = 54 ✓

What each part represents:

• prefix[3][4] = 78: total sum of the entire 3x4 region
• prefix[1][4] = 10: excess from the top — row 1 (1+2+3+4)
• prefix[3][1] = 15: excess from the left — column 1 (1+5+9)
• prefix[1][1] = 1: top-left corner was subtracted one extra time, add it back

✨ Common Mistakes with 2D Prefix Sum

1. Out-of-bounds due to 0-based indexing: When computing prefix[i-1][j], if i=0 it goes out of bounds. It is recommended to store data starting from index 1, so row 0 and column 0 are naturally 0
2. Confusing build and query formulas: The build formula ends with + a[i][j], while the query formula ends with + prefix[x1-1][y1-1]. The sign patterns are different, so memorize them separately
3. Incorrect coordinate offset in queries: The formula subtracts x1-1 and y1-1 (the row above and column to the left of the top-left corner). Do not write x1 and y1 instead
4. Insufficient array size: When indices start from 1, the array size must be at least 1 larger than the data range. Global arrays are automatically initialized to 0, but local arrays need manual initialization
5. Integer overflow: When array elements are large and the rectangular region is large, the prefix sum may exceed the int range, requiring long long

III. Homework

Programming Exercises

1. Maximum Square: L2213
2. Maximum Weighted Rectangle: L2214