差分
差分和前缀和互为逆运算,即差分数组的前缀和数组为原数组,前缀和数组的差分数组为原数组。两者都利用了容斥原理,这一点在二维平面(或二维数组)中体现的更加明显。
- 一维差分
定义:差分就是将数列中的每一项分别与前一项数做差。
例子:
一个序列1 2 5 4 7 3,差分后得到1 1 3 -1 3 -4 -3
性质:
1.差分数组求前缀和可以得到原序列
2.将愿序列区间[L,R]中的元素全部+1,可以转化操作为差分数组L处+1,R+1处-1.
3.按照性质2得到,每次修改原序列一个区间+1,那么每次差分序列修改处增加的和减少的相同。
- 二维差分
其实二维差分和一维差分一样,就是更新时一维是更新两个点,二维的更新四个点(四个跟x,y相近的点),然后询问某一个点的值都是前缀和。
根据二维前缀和表示的是右上角矩形的和,由于差分只涉及前面相邻的数(有一维可以推出),并且由前面范围的数相加得到这个位置的数。那么类比二维前缀和和一维差分,可以简单推测出二维差分的公式:
a是原矩阵,p是差分矩阵
p[i][j] = a[i][j] + a[i-1][j-1] - a[i][j-1] - a[i-1][j]
那么如何从差分矩阵得到原矩阵呢?
a[i][j] = p[i][j] + p[i-1][j] + p[i][j-1] - p[i-1][j-1]
对(x1,y1)-(x2,y2)的矩阵+1,对差分矩阵进行更新就可以了。
++p[x1][y1];
++p[x2+1][y2+1];
--p[x1][y2+1];
--p[x2+1][y1];
更新的是以(x1,y1)和(x2,y2)为两个对顶角的矩形。
例题:https://ac.nowcoder.com/acm/contest/7501/J
#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <stdlib.h> #include <sstream> #include <map> #include <set> typedef long long ll; using namespace std; ll mp[1005][1005]; ll chafen[1005][1005]; int main() { int T; cin >> T; while (T--) { ll n,m,a,b; cin >> n >> m >> a >> b; for (int i=1;i<=n;i++) { for (int j=1;j<=m;j++) { cin >> mp[i][j]; //输入原数组 } } //i和j的大小到n+1,m+1 for (int i=1;i<=n;i++) { for (int j=1;j<=m;j++) { chafen[i][j] = mp[i][j] + mp[i-1][j-1] - mp[i-1][j] - mp[i][j-1]; //构造差分数组 } } /* (i,j) - (i+a-1,j+b-1) i+a-1 <= n -> i<=n+1-a j+b-1 <= m -> j<=m+1-j */ int flag=1; for (int i=1;i<=n+1-a;i++) { for (int j=1;j<=m+1-b;j++) { ll c=chafen[i][j]; if(c<0) { flag=0; break; } else //如果当前的差分数组不小于0,那么说明这个点是可以更新的(把i,j -> i+a,j+b范围 都 减掉当前差分数组的值),因为是一个一个遍历的,当前的差分数组的值,其实就是原数组的值 { chafen[i][j]=0; chafen[i+a][j+b]-=c; chafen[i][j+b]+=c; chafen[i+a][j]+=c; } } if(flag==0) break; } /*最后看看是否全为0,如果还有不为0的,说明并不能完全转化*/ for (int i=1;i<=n;i++) { for (int j=1;j<=m;j++) { if(chafen[i][j]!=0) { flag=0; break; } } if(flag==0) break; } if(flag==0) cout << "QAQ" << endl; else cout << "^_^" << endl; } return 0; }