【算法进阶】从一维到二维：图解二维前缀和与差分数组的“空间容斥”原理（洛谷 P3397 附C++代码）

题目链接P3397 地毯 - 洛谷前缀和与差分是在进行区间的查询或者修改的时候常见的优化技巧但是如果到了对一个矩阵的区间修改就很难做了。比如这道洛谷的 P3397 题目如果直接一个个元素对其修改那每次的修改都将是O($N^2$)这样实在是太慢了不能接受于是我们就需要用到二维前缀和与差分的方法来解决这种类型的题目。二维前缀和定义我们回忆一下一维前缀和的做法其实就是对一个原数组 a 不断进行累加求和得到一个新的数组 sum 满足这个公式的数组也就是从1一直加到x。那其实二维前缀和数组的定义也很好理解就是对于一个二维原数组 a 我们要不断累加求和从 (1,1) 点一直加到 (n,m) 点的和就是 sum[n][m] 的数值。也就是说它满足的公式应该是。我们画一个图就能够更好理解 sum[n][m]所求和的范围了。以下面的图例二维数组为例。比如对于 sum[4][5] 的值在原数组 a 中求和的范围就应该如下。如果是 sum[3][8] 那在原数组 a 中求和的范围如下。容易发现其实这个二维前缀和求得的值只是对以 (1,1) 点为左上角以 (n,m) 点为右下角确定的矩形的所有元素的和。那既然我们明白了这个定义那我们总要想一个办法来还原出我们需要的区间和就像一维的前缀和一样。而我们知道前缀和与差分实际上是互为逆运算的在二维的情况下也是如此这个时候要用到的就是二维的差分来解决了。二维差分定义我们先以二维前缀和 sum 来还原出原数组 a 为例看看差分基本是如何计算的再来讨论二维差分的通式。比如我们已经得到了整一个 sum 数组二维前缀和的值要计算 a[n][m] 的值。那首先我们肯定是要用到 sum[n][m] 的值来计算的因为我们只是要 a[n][m] 的值我们并不需要其他的值了所以我们要想办法去把其余的减掉。那我们其实结合二维前缀和的性质我们就能很自然地想到用到不包含我们想要的值 a[n][m] 而且包含其他几乎所有值的sum[n-1][m] 和 sum[n][m-1]减去来尝试把其余的值全部减掉。可是我们减掉这两个值后我们很敏锐能发现中间这个 sum[n-1][m-1] 这个区间也就是下图标记的部分很明显被我们减掉了两次所以我们当然要把这个 sum[n-1][m-1] 的部分再加回来一次也就得到了我们最终要求的 a[n][m] 的值也就是a[n][m]sum[n][m]-sum[n-1][m]-sum[n][m-1]sum[n-1][m-1]。这种“多减了要加回来、多加了要减去”的空间几何思想在离散数学中有一个极其优雅的专有名词——容斥原理Inclusion-Exclusion Principle。整个二维前缀和与差分的核心本质上就是容斥原理在二维矩阵上的物理映射。我们转化一下设二维差分数组为 d 由于原数组 a 本质上就是差分数组 d 的前缀和所以我们将前缀和公式逆向移项就能得到二维差分数组的定义公式d[n][m]a[n][m]-a[n-1][m]-a[n][m-1]a[n-1][m-1] 。前缀和与差分的性质与计算了解了基本定义我们需要知道关于他们的性质用处和计算了。二维前缀和二维前缀和和一维前缀和其实一样都是支持区间的快速查询。我们可以推导一下我们如果要查询以为左上角以为右下角的矩阵和应该怎么做首先和刚刚的想法一样我们肯定要用到的值来减去其他多余的部分。我们再来看看哪些部分是我们不需要的多余的。很明显这个时候我们需要减去和这两个部分了。但这个时候我们也能发现我们多减了下图所示的部分的值所以我们需要再把他们加回来。可以得到我们最终的公式就是 sum[(x1,y1),(x2,y2)]sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]sum[x1-1][y1-1] 。用于查询区间矩阵和。二维差分二位差分数组设为 d 我们知道定义之后实际上我们可以知道它和一维的差分数组的性质是一样的。一维的差分数组修改了一个点的值会让后面所有的点的值都得到和它一样的修改而二维的差分数组修改了一个 (x,y) 点的值会让以 (x,y) 为左上角的矩阵里所有值都得到修改。就像一滴墨水一样滴入一个水潭里会让后面所有的水都变黑。在一维差分数组我们对一个区间 [l,r] 进行增加或者减少数值我们要在 l 点增加或者减少并在 r1 点减少或者增加从而来抵消对后面所有数值的影响使得修改仅仅局限于 [l,r] 区间内。而在二维数组我们如果想要对一个以为左上角以为右下角的矩阵区间进行修改我们要看看应该怎么做才能进行正确的修改。我们以要对这个区间加 k 来演示。首先我们肯定是要进行 d[x1][y1]k 的。但是这样做之后我们修改的影响范围就如下图所示了。我们的目标就是要想办法让这个影响仅仅局限在以为左上角以为右下角的矩阵区间内。为了抵消对后面数值的影响我们很自然就能想到在 (x21,y1) 和 (x1,y21) 进行修改进行 d[x21][y1]-k 和 d[x1][y21]-k 。但是有个问题就是我们依然对下图黄色部分也就是以 (x21,y21) 为左上角的矩阵区间减去了两次 k 为了解决这个问题我们需要再进行 d[x21][y21]k 就能让黄色部分的影响也消失了。最后我们进行了四步的修改就成功地解决了二维矩阵区间修改的问题了洛谷 P3397 解法这也回到了我们刚刚开始提到的问题对于这种区间修改我们可以利用二维差分来解决最后进行一次二维前缀和解决即可。理解了二维前缀和与差分原理之后写起来还是很容易的代码如下附带注释#include bits/stdc.h using namespace std; int n,m; int arr[1005][1005]; int main() { ios::sync_with_stdio(false); cin.tie(0); cinnm; for(int i1;im;i) { int x1,y1,x2,y2; cinx1y1x2y2; //以下进行四步区间修改 arr[x1][y1]; arr[x21][y21]; --arr[x21][y1]; --arr[x1][y21]; } for(int i1;in;i) { for(int j1;jn;j) { //一边计算前缀和一边输出答案 arr[i][j]arr[i-1][j]arr[i][j-1]-arr[i-1][j-1]arr[i][j]; coutarr[i][j]; if(j!n) cout ; } cout\n; } }这里我个人将 arr 数组进行复用不用单独开两个数组来存差分和前缀和直接一个数组就可以解决我个人认为是更省内存更好的解法。