二维前缀和怎么算？如何 O(1) 查询任意子矩阵的和？

简化版

二维前缀和把一维推广到矩阵:P[i][j] 表示从左上角 (0,0) 到 (i-1,j-1) 的矩形区域和。用容斥递推:P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + a[i-1][j-1]。之后查询任意子矩阵 (r1,c1) 到 (r2,c2) 的和,也用容斥 O(1) 算出。预处理 O(mn),每次查询 O(1)。

详细版

构建(P 大小 (m+1)×(n+1),首行首列为 0):

int[][] P = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++)
    for (int j = 1; j <= n; j++)
        P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + a[i-1][j-1];

查询子矩阵 (r1,c1) 到 (r2,c2)(含两端,0-indexed):

int sum = P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1];

构建的容斥:上面的矩形 + 左边的矩形 - 重复减掉的左上角 + 当前格。
查询的容斥:大矩形 - 上方多余 - 左方多余 + 被减两次的左上角。

完整版教学

一、从一维到二维:面积的累加

一维前缀和记「从头到某位置的累加和」;二维前缀和记「从左上角到某个格子围成的矩形的和」。P[i][j] = 以 (0,0) 为左上角、(i-1,j-1) 为右下角的矩形里所有元素的和。有了这些「矩形和」,任意子矩阵的和就能通过几个矩形的加减算出来——这就是二维前缀和的思路,核心工具是容斥原理。

二、构建公式:容斥拼矩形

要算 P[i][j](左上到 (i-1,j-1) 的矩形和),可以用已经算好的更小矩形拼:

P[i][j] = P[i-1][j]      // 上面那块矩形
        + P[i][j-1]      // 左边那块矩形
        - P[i-1][j-1]    // 上面和左边重叠的左上角块，被加了两次，减掉一次
        + a[i-1][j-1]    // 当前格子本身

「上块 + 左块」会把左上角那块重复算一次,所以要减掉一个 P[i-1][j-1],再加上当前格。这是容斥的加加减减,画个图就很清楚。

三、查询公式:大矩形减多余

查询子矩阵 (r1,c1) 到 (r2,c2) 的和,思路是「用大矩形减去多余部分」:

sum = P[r2+1][c2+1]   // 从原点到右下角的大矩形
    - P[r1][c2+1]     // 减去上方多出来的横条
    - P[r2+1][c1]     // 减去左方多出来的竖条
    + P[r1][c1]       // 上方和左方都减了左上角那块，多减了一次，加回来

「减上条、减左条」会把左上角那块减两次,所以要加回一个 P[r1][c1]。这和构建公式是同一个容斥思想,方向相反。

四、下标偏移:为什么用 (m+1)×(n+1)

和一维一样,二维前缀和也用多一圈 0的设计:P 的大小是 (m+1)×(n+1),第 0 行和第 0 列全是 0。这样:

构建时 P[i-1][j] 等在 i=1/j=1 时不会越界(有那圈 0 兜底)。
查询时 (r1,c1) 从 0 开始也不用特判(P[r1][...] 在 r1=0 时是 0)。

原数组下标 a[i-1][j-1] 对应前缀和下标 P[i][j],这个偏移一位的对应关系要牢记,是二维前缀和最容易搞错的地方。

五、走一个例子

a = 3 1 4        P（多一圈0）= 0  0  0  0
    1 5 9                     0  3  4  8
    2 6 5                     0  4 10 23
                              0  6 18 36
（如 P[2][2]=P[1][2]+P[2][1]-P[1][1]+a[1][1]=4+4-3+5=10；P[3][3]=36 正好是全矩阵和）
查子矩阵 (0,0)~(1,1)（即 3 1 / 1 5，和=3+1+1+5=10）：
  P[2][2] - P[0][2] - P[2][0] + P[0][0] = 10 - 0 - 0 + 0 = 10 ✓

六、复杂度与应用

构建 O(mn)、每次查询 O(1)、空间 O(mn)。
应用:
- 子矩阵和查询(LeetCode 304)。
- 和为 target 的子矩阵个数:枚举上下边界,把每列压成一维,转成「和为 K 的子数组」用前缀和 + 哈希。
- 最大子矩阵和、矩阵区域统计等。

七、从公式证明到手算闭环

这道题成立的核心是：pre[i][j] 表示左上角 (0,0) 到原矩阵 (i-1,j-1) 的矩形和，重叠区域必须用容斥补回。先明确每个数组槽或哈希键的数学含义，代码中的下标偏移才不是死记硬背。

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

带数字推演：矩阵 [[1,2],[3,4]] 的整块和为 10；查询第二列用 10-4=6，其中 4 是第一列之和。手算时同时列出原数组、辅助状态和本轮新增答案，能够直接发现端点偏一、初始化遗漏以及更新顺序错误。

核对维度	本题结论
正确性依据	`pre[i][j]` 表示左上角 `(0,0)` 到原矩阵 `(i-1,j-1)` 的矩形和，重叠区域必须用容斥补回
复杂度	预处理 O(mn)，矩形查询 O(1)，额外空间 O(mn)
关键边界	额外的第 0 行和第 0 列消除分支；四个坐标必须明确是否包含端点；m×n 累计同样要考虑溢出

记忆钩子：不要先背代码，先说清辅助状态“代表哪一段”；公式只是把重叠部分消掉或把边界影响传播出去。

八、实现边界与测试策略

实现时最需要警惕的是：额外的第 0 行和第 0 列消除分支；四个坐标必须明确是否包含端点；m×n 累计同样要考虑溢出。这不是语法细节，而是决定算法是否仍满足题目语义的前提。

提交前应分别验证：

空数组或最小合法规模，确认哨兵位置和初始化。
查询或更新紧贴左、上边界，确认没有访问负下标。
查询或更新紧贴右、下边界，确认“终点后一位”不会越界。
包含 0、负数或重复前缀的样例，确认频次与取模语义。
大数输入，确认累计和、乘积或答案数量的整数类型足够。

如果需求从离线变成在线，或从单次恢复变成更新查询交错，原方法可能不再合适。此时应根据操作类型改用树状数组、线段树、二维结构或其他能维护动态状态的数据结构，而不是强行沿用静态前缀模型。

九、常见误区与追问

误区：二维前缀和只需减去上方和左方。 两块被减区域有交集，左上重叠必须加回来。
误区：查询公式可以随意交换坐标。 必须先保证 r1≤r2、c1≤c2，且端点语义一致。
误区：二维前缀和支持 O(1) 更新。 单点变化会影响右下整个区域，普通结构更新不是 O(1)。
追问：为什么使用 (m+1)×(n+1)？ 零边界让贴边矩形也套同一公式。
追问：稀疏大矩阵怎么办？ 可离线压缩坐标，或按查询结构选择二维树状数组。
追问：怎样验证容斥符号？ 画出大矩形，减上、减左、补回被减两次的左上交集。

十、加强记忆

二维前缀和 P[i][j] = 左上角到 (i-1,j-1) 的矩形和,用容斥构建:P[i-1][j] + P[i][j-1] - P[i-1][j-1] + a[i-1][j-1](上块+左块-重叠左上角+当前)。查询子矩阵 (r1,c1)~(r2,c2):P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1](大矩形-上条-左条+左上角)。用 (m+1)×(n+1) 多一圈 0 免边界特判,a[i-1][j-1]↔P[i][j] 偏移一位。构建 O(mn)、查询 O(1)。

简化版

详细版