高效前缀和算法及其在二维矩阵中的应用

核心逻辑与数学原理

前缀和是一种高效的预处理技术，其物理本质是容斥原理（Inclusion-Exclusion Principle）在离散网格积分上的应用。通过空间换时间，这种方法将区间或区域和的查询复杂度从暴力枚举的 $O(N)$ 或 $O(N \times M)$ 降至 $O(1)$。

在一维空间中，前缀和定义为序列前 $i$ 个元素的累加和。对于原始数组 $A$，其前缀和数组 $S$ 满足：

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

利用微积分基本定理的离散化形式，区间 $[l, r]$ 的连续子段和可通过两个端点的前缀和差值直接计算：

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

在二维空间中，前缀和扩展为矩阵区域和。定义 $S[i][j]$ 为以 $(1,1)$ 为左上角、$(i,j)$ 为右下角的子矩阵内所有元素的代数和。任意矩形区域 $[x_1, y_1] \sim [x_2, y_2]$ 的元素和，其本质是二维平面上的定积分。通过几何图形的重叠与裁剪，可将多维空间边界切分，利用容斥原理在常数时间内提取任意子矩阵。

状态设计与算法推导

1. 二维前缀和的状态递推

定义状态 $S[i][j]$ 表示子矩阵 $\sum_{u=1}^{i} \sum_{v=1}^{j} A[u][v]$ 的和。当已知 $S[i-1][j]$（上方矩形）、$S[i][j-1]$（左方矩形）以及 $S[i-1][j-1]$（对角线重叠矩形）时，当前网格 $A[i][j]$ 的加入会导致重叠区域被重复计算。依据容斥原理，当前状态的递推方程为：

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

2. $O(1)$ 矩阵区域和查询推导

给定查询子矩阵的左上角坐标 $(x_1, y_1)$ 与右下角坐标 $(x_2, y_2)$。目标区域和等价于以 $(x_2, y_2)$ 为右下角的总矩阵，减去上方不相关区域 $[1, x_1-1] \times [1, y_2]$，减去左方不相关区域 $[1, x_2] \times [1, y_1-1]$。此时，左上方块 $[1, x_1-1] \times [1, y_1-1]$ 被扣除了两次，必须补回一次。因此，任意子矩阵区域和的精确数学表达式为：

$$\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++ 标准源码

#include <iostream>
#include <vector>

using namespace std;

// 演示二维前缀和的完整工程实现
void solveMatrixSum() {
    int n, m, q;
    if (!(cin >> n >> m >> q)) return;

    // 采用 1-indexed 边界，规避 i-1 越界检查的 if 分支分支预测失败开销
    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];
        }
    }

    // 预处理二维前缀和，时间复杂度 O(N * M)
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            // 致命踩坑点：必须确保右侧运算不发生整数溢出，s 数组采用 long long 存储
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
        }
    }

    // O(1) 在线查询
    for (int i = 0; i < q; ++i) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;

        // 容斥原理核心公式，错一个正负号直接 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() {
    // 强制关闭输入输出流同步，加速 IO 性能
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    solveMatrixSum();

    return 0;
}

NOIP 实战避坑指南

整型溢出（Integer Overflow） 这是前缀和题型中最常犯的低级错误。哪怕原始矩阵元素 $A[i][j] \le 10^5$，当矩阵规模达到 $10^3 \times 10^3$ 时，前缀和最大值可达 $10^{11}$，远超 int 类型的 $2 \times 10^9$ 上限。前缀和数组 s 以及查询结果变量必须强制声明为 long long。在进行大模数取模前缀和（如模 $10^9+7$）时，由于容斥原理公式中存在减法项，计算 (s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]) % MOD 极易产生负数。必须使用 (ans % MOD + MOD) % MOD 进行正数化规整**。
边界越界与 0 号下标未初始化 若习惯使用 0-indexed 数组，递推方程中的 $i-1$ 和 $j-1$ 会在 $i=0$ 或 $j=0$ 时触发严重的内存越界访问（Segmentation Fault）。若在循环内加 if(i > 0) 判定，会破坏现代 CPU 的分支预测与流水线优化，大幅拉低运行速度。标准工程规范是强制使用 1-indexed 数组，并将所有第 0 行、第 0 列元素显式清零，作为天然的边界哨兵。

经典 NOIP/洛谷真题

1. 洛谷 P2280 [HNOI2003] 激光炸弹

题意描述：一种新型激光炸弹可以摧毁一个 $R \times R$ 正方形内的所有目标。现在地图上有 $N$个目标，每个目标有其坐标 $(x,y)$ 和价值 $v$。求一颗炸弹最多能摧毁的目标总价值。
问题本质：二维固定窗口大小的最大区域和查询。
核心解题思路：由于地图边界固定（通常为 $5000 \times 5000$ 级别），可以建立一个二维网格。将每个目标的价值累加到对应的坐标点上，随后对整张地图预处理出二维前缀和。由于炸弹覆盖的是正方形，其物理边界需要注意：若炸弹覆盖半径为 $R$，其等价于在二维前缀和矩阵中查询所有大小为 $R \times R$ 的子矩阵的权值和。遍历所有可能的右下角坐标 $(i, j)$，在 $O(1)$ 时间内计算出区域和并维护全局最大值。整题复杂度由暴力的 $O(N \cdot R^2)$ 优化至 $O(M^2 + N)$，其中 $M$ 为地图边界大小。

2. 洛谷 P1387 最大正方形

题意描述：给定一个 $N \times M$ 的 01 矩阵，求一个只包含 1 的最大正方形边长。
问题本质：二维前缀和判定性检验或结合动态规划。
核心解题思路：本题可以通过前缀和在 $O(1)$ 时间内验证一个子矩阵是否全为 1。预处理 01 矩阵的二维前缀和。若一个大小为 $L \times L$ 的子矩阵内所有元素均为 1，则该子矩阵的区域和必然严格等于 $L^2$。可以通过枚举正方形的左上角坐标 $(i, j)$ 和边长 $L$，利用二维前缀和公式进行 $O(1)$ 校验。更进一步，为避免 $O(N^3)$ 的三重循环卡常，可以结合二分答案或动态规划优化：在外层引入二分正方形边长 $L$，将总时间复杂度压制在 $O(N M \log(\min(N, M)))$，确保满分通过。