【算法进阶】从一维到二维：图解二维前缀和与差分数组的“空间容斥”原理（洛谷 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 点增加或者减少，并在 r+1 点减少或者增加从而来抵消对后面所有数值的影响，使得修改仅仅局限于 [l,r] 区间内。而在二维数组，我们如果想要对一个以为左上角，以为右下角的矩阵区间进行修改，我们要看看应该怎么做才能进行正确的修改。我们以要对这个区间加 k 来演示。

首先，我们肯定是要进行 d[x1][y1]+=k 的。但是这样做之后，我们修改的影响范围就如下图所示了。我们的目标，就是要想办法让这个影响仅仅局限在以为左上角，以为右下角的矩阵区间内。

为了抵消对后面数值的影响，我们很自然就能想到在 (x2+1,y1) 和 (x1,y2+1) 进行修改，进行 d[x2+1][y1]-=k 和 d[x1][y2+1]-=k 。但是有个问题就是，我们依然对下图黄色部分，也就是以 (x2+1,y2+1) 为左上角的矩阵区间减去了两次 k ！

为了解决这个问题，我们需要再进行 d[x2+1][y2+1]+=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); cin>>n>>m; for(int i=1;i<=m;++i) { int x1,y1,x2,y2; cin>>x1>>y1>>x2>>y2; //以下进行四步区间修改 ++arr[x1][y1]; ++arr[x2+1][y2+1]; --arr[x2+1][y1]; --arr[x1][y2+1]; } for(int i=1;i<=n;++i) { for(int j=1;j<=n;++j) { //一边计算前缀和一边输出答案 arr[i][j]=arr[i-1][j]+arr[i][j-1]-arr[i-1][j-1]+arr[i][j]; cout<<arr[i][j]; if(j!=n) cout<<" "; } cout<<'\n'; } }

这里我个人将 arr 数组进行复用，不用单独开两个数组来存差分和前缀和，直接一个数组就可以解决，我个人认为是更省内存，更好的解法。