我们上节课学了一维的差分，但其实还有二维差分，只是比较难写。

差分

二维差分的定义

二维差分是指对于一个n*m的矩阵a，要求支持操作pro(x1,y1,x2,y2,a)，表示对于以(x1,y1)为左上角，(x2,y2)为右下角的矩形区域，每个元素都加上常数a。求修改后的矩阵a。

二维差分的解释

这样说似乎还是有点抽象，我们不妨以一道例题来看看

在 n×n 的格子上有 m 个地毯。
给出这些地毯的信息，问每个点被多少个地毯覆盖。

其实不难发现，这个和普通的递推好像有点相似之处，我们其实可以画个图来解释一下
注：上图来源于网络

不难发现，二维差分的关键就是在于：

mp[x1][y1]++;
mp[x1][y2+1]--;
mp[x2+1][y1]--;
mp[x2+1][y2+1]++;

所以我们直接上例题吧

例题1 地毯

在 n×n 的格子上有 m 个地毯。
给出这些地毯的信息，问每个点被多少个地毯覆盖。

这道题是十分简单的差分，直接套公式就行了

#include<bits/stdc++.h>
using namespace std;int mp[2100][2100];
int main(){int n,m;cin>>n>>m;for (int i=1;i<=m;i++){int x1,x2,y1,y2; cin>>x1>>y1>>x2>>y2;mp[x1][y1]++;mp[x1][y2+1]--;mp[x2+1][y1]--;mp[x2+1][y2+1]++;}for (int i=1;i<=n;i++){for (int j=1;j<=n;j++){mp[i][j]+=mp[i-1][j]+mp[i][j-1]-mp[i-1][j-1];cout<<mp[i][j]<<" ";}cout<<endl;}return 0;
}