Efficient Prefix Sum Algorithm and Its Application in 2D Matrices

Core Logic and Mathematical Principles

The prefix sum is an efficient preprocessing technique, fundamentally based on the Inclusion-Exclusion Principle applied to discrete grid integration. By trading space for time, this method reduces the query complexity of interval or region sums from a brute-force enumeration of $O(N)$ or $O(N \times M)$ to $O(1)$.

In one-dimensional space, the prefix sum is defined as the cumulative sum of the first $i$ elements of a sequence. For the original array $A$, its prefix sum array $S$ satisfies:

$$S[i] = \sum_{k=1}^{i} A[k]$$

Using the discrete form of the Fundamental Theorem of Calculus, the sum of the continuous segment in the interval $[l, r]$ can be calculated directly using the difference of the prefix sums at the two endpoints:

$$\sum_{k=l}^{r} A[k] = S[r] - S[l-1]$$

In two-dimensional space, the prefix sum extends to the sum of matrix regions. Define $S[i][j]$ as the algebraic sum of all elements in the submatrix with $(1,1)$ as the top-left corner and $(i,j)$ as the bottom-right corner. The sum of elements in any rectangular region $[x_1, y_1] \sim [x_2, y_2]$ essentially represents a definite integral on the two-dimensional plane. By overlapping and clipping geometric shapes, we can partition the boundaries of multidimensional spaces and utilize the Inclusion-Exclusion Principle to extract any submatrix in constant time.

State Design and Algorithm Derivation

1. State Recursion for 2D Prefix Sum

Define the state $S[i][j]$ to represent the sum of the submatrix $\sum_{u=1}^{i} \sum_{v=1}^{j} A[u][v]$. Given $S[i-1][j]$ (the upper rectangle), $S[i][j-1]$ (the left rectangle), and $S[i-1][j-1]$ (the overlapping diagonal rectangle), the inclusion of the current grid $A[i][j]$ leads to double counting of the overlapping region. According to the Inclusion-Exclusion Principle, the recursion formula for the current state is:

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

2. Derivation of $O(1)$ Matrix Region Sum Queries

Given the top-left coordinates $(x_1, y_1)$ and bottom-right coordinates $(x_2, y_2)$ of the queried submatrix, the target region sum is equivalent to the total matrix with $(x_2, y_2)$ as the bottom-right corner, minus the unrelated upper region $[1, x_1-1] \times [1, y_2]$, and minus the unrelated left region $[1, x_2] \times [1, y_1-1]$. At this point, the upper left block $[1, x_1-1] \times [1, y_1-1]$ has been subtracted twice, and must be added back once. Therefore, the precise mathematical expression for the sum of any submatrix region is:

$$\text{Sum}(x_1, y_1, x_2, y_2) = S[x_2][y_2] - S[x_1-1][y_2] - S[x_2][y_1-1] + S[x_1-1][y_1-1]$$

C++ Standard Source Code

#include <iostream>
#include <vector>

using namespace std;

// Complete implementation demonstrating 2D prefix sums
void solveMatrixSum() {
    int n, m, q;
    if (!(cin >> n >> m >> q)) return;

    // Using 1-indexed boundaries to avoid the overhead of checking for i-1 out of bounds
    vector<vector<long long>> a(n + 1, vector<long long>(m + 1, 0));
    vector<vector<long long>> s(n + 1, vector<long long>(m + 1, 0));

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

    // Preprocess the 2D prefix sum, time complexity O(N * M)
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            // Critical pitfall: ensure no integer overflow in right-side calculations, use long long for s array
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
        }
    }

    // O(1) online queries
    for (int i = 0; i < q; ++i) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;

        // Core formula of the Inclusion-Exclusion Principle, a single sign error leads to WA
        long long ans = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
        cout << ans << "\n";
    }
}

int main() {
    // Force disable synchronization of input and output streams to speed up IO performance
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    solveMatrixSum();

    return 0;
}

NOIP Practical Pitfall Guide

Integer Overflow This is a common basic error in prefix sum problems. Even if the original matrix elements $A[i][j] \le 10^5$, when the matrix size reaches $10^3 \times 10^3$, the maximum prefix sum can reach $10^{11}$, far exceeding the int type limit of $2 \times 10^9$. The prefix sum array s and the query result variable must be explicitly declared as long long. When performing modulo operations on large prefix sums (e.g., modulo $10^9+7$), due to the presence of subtraction terms in the Inclusion-Exclusion formula, computing (s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]) % MOD can easily yield negative results. Use (ans % MOD + MOD) % MOD to ensure non-negative results**.
Out-of-Bounds Access and Uninitialized Zero Index If you are accustomed to using 0-indexed arrays, the $i-1$ and $j-1$ in the recursion formula will trigger serious out-of-bounds access (Segmentation Fault) when $i=0$ or $j=0$. Adding an if(i > 0) check inside the loop would disrupt modern CPU branch prediction and pipeline optimization, significantly slowing down execution. The standard engineering practice is to enforce the use of 1-indexed arrays and explicitly zero out all elements in the 0th row and 0th column as natural boundary sentinels.

Classic NOIP/Luogu Problems

1. Luogu P2280 [HNOI2003] Laser Bomb

Problem Description: A new type of laser bomb can destroy all targets within a $R \times R$ square. Now there are $N$ targets on the map, each with coordinates $(x,y)$ and value $v$. Find the maximum total value of targets that can be destroyed by one bomb.
Essential Problem: Maximum area sum query with a fixed two-dimensional window size.
Core Problem-Solving Idea: Since the map boundaries are fixed (usually around $5000 \times 5000$), a two-dimensional grid can be established. Each target's value is added to the corresponding coordinate point, and then the entire map is preprocessed to obtain the two-dimensional prefix sum. Given that the bomb covers a square, its physical boundaries must be noted: if the bomb's coverage radius is $R$, it is equivalent to querying all $R \times R$ submatrices' weights in the two-dimensional prefix sum matrix. Iterate through all possible bottom-right corner coordinates $(i, j)$ and calculate the area sum in $O(1)$ time while maintaining the global maximum value. The complexity of the entire problem is optimized from a brute-force $O(N \cdot R^2)$ to $O(M^2 + N)$, where $M$ is the size of the map boundary.

2. Luogu P1387 Largest Square

Problem Description: Given a $N \times M$ binary matrix, find the maximum side length of a square that contains only 1s.
Essential Problem: Deterministic verification using two-dimensional prefix sums or combined with dynamic programming.
Core Problem-Solving Idea: This problem can verify whether a submatrix is entirely composed of 1s in $O(1)$ time using prefix sums. Preprocess the binary matrix to obtain its two-dimensional prefix sum. If a submatrix of size $L \times L$ contains all 1s, the area sum of that submatrix must strictly equal $L^2$. By enumerating the top-left corner coordinates $(i, j)$ and the side length $L$ of the square, use the two-dimensional prefix sum formula for $O(1)$ verification. Furthermore, to avoid the $O(N^3)$ complexity of triple loops, binary search or dynamic programming can be combined to optimize: by introducing binary search for the square side length $L$, the total time complexity can be constrained to $O(N M \log(\min(N, M)))$, ensuring full score.