二维前缀和

二维前缀和用来维护某一个矩阵内所有数字的和。(必须是矩阵，而不能是一个不规则图形，你可以理解为一个长方形)。

定义：$sum_{i,\ j}$ 即以 $(1,1)$ 为 左上角 ，以 $(i,j)$ 为 右下角 构成的 矩阵 内的所有元素的和。

它的维护是这样的：

$$sum_{i,\ j}=sum_{i-1,\ j}+sum_{i,\ j-1}-sum_{i-1,\ j-1}+a_{i,\ j} $$

输入的推导

第一部分

$sum_{i,\ j}$ ：表示以 $(1,1)$ 为左上角，$(i,\ j)$ 为右下角构成的矩阵的数字之和。

即 蓝 + 黄 + 绿 + 橙 四部分的和。

第二部分

$sum_{i-1,\ j}$ ：表示以 $(1,1)$ 为左上角，$(i-1,\ j)$ 为右下角构成的矩阵的数字之和。 0. 即 蓝 + 黄 两部分的和。

第三部分

$sum_{i,\ j-1}$ ：表示以 $(1,1)$ 为左上角，$(i,\ j-1)$ 为右下角构成的矩阵的数字之和。

即 蓝 + 绿 两部分的和。

第四部分

$sum_{i-1,\ j-1}$ ：表示以 $(1,1)$ 为左上角，$(i-1,\ j-1)$ 为右下角构成的矩阵的数字之和。

即 蓝 这部分的和。

总结

$sum_{i,\ j}=sum_{i-1,\ j}+sum_{i,\ j-1}-sum_{i-1,\ j-1}+a_{i,\ j}$

即 蓝 + 黄 + 绿 + 橙 = (蓝 + 黄) + (蓝 + 绿) - 蓝 + 橙 最终求得了 $sum_{i,\ j}$

子矩阵的和的计算

注意这里必须依赖定义计算，也就是需要获取子矩阵的左上角和右下角坐标，其余不能直接套公式。

$$sum_{x_2,\ y_2}-sum_{x_1-1,\ y_2}-sum_{x_2,\ y_1-1}+sum_{x_1-1,\ y_1-1} $$

其中 $(x_1,\ y_1)$ 为待计算的子矩阵的左上角坐标，$(x_2,\ y_2)$ 为待计算的子矩阵的右下角的坐标。

子矩阵和的推导

第一部分

$sum_{x_2,\ y_2}$: 以 $(1,1)$ 为左上角，$(x_2,\ y_2)$ 为右下角的矩阵元素之和，即图中 绿 + 蓝 + 橙 + 黄 四部分的和。

第二部分

$sum_{x_1-1,\ y_2}$: 以 $(1,1)$ 为左上角，$(x_1-1,\ y_2)$ 为右下角的矩阵元素之和，即图中 绿 + 蓝 两部分的和。

第三部分

$sum_{x_2,\ y_1-1}$: 以 $(1,1)$ 为左上角，$(x_2,\ y_1-1)$ 为右下角的矩阵元素之和，即图中 绿 + 橙 两部分的和。

第四部分

$sum_{x_1-1,\ y_1-1}$: 以 $(1,1)$ 为左上角，$(x_1-1,\ y_1-1)$ 为右下角的矩阵元素之和，即图中 绿 一部分的和。

总结

因此公式

$$sum_{x_2,\ y_2}-sum_{x_1-1,\ y_2}-sum_{x_2,\ y_1-1}+sum_{x_1-1,\ y_1-1} $$

可以概括为 绿 + 蓝 + 橙 + 黄 - (绿 + 蓝) - (绿 + 橙) + 绿 = 黄。

概括起来就是总的减去上面的减去左边的，加上多减去的部分。

应用

• 同一维前缀和一样，有的时候题目会直接可以获取到矩阵的左上角以及右下角坐标，然后套用模板求解。(若给定矩阵不是左上角和右下角，需要自己转换)
• 通过枚举左上角或右下角，同时知道所求矩阵的长和宽，类似于一维计算另一个端点的方法，计算出另一个角的横纵坐标，然后使用公式求解。
• 也可以用来维护某一个矩阵内某个数值的个数，例如维护一个矩阵内有几个奇数。