差分笔记
差分笔记
差分可看作前缀和的逆运算
对于一个数组a[n]有：
a[0] a[1] a[2] a[3] ......a[n-2] a[n-1]
构造一个差分数组b[n]使得其中每一项都为数组a每项的差：
b[0]=a[0]
b[1]=a[1]-a[0]
......
b[n-2]=a[n-2]-a[n-3]
b[n-1]=a[n-1]-a[n-2]
不难看出b的前缀和为a中的每一项
a[n]=b[0]+b[1]+b[2]+......+b[n]
应用：一维差分
若想对a中 a[l]~a[r] 之间的每个数都加上c
则可以做以下操作：
b[l]+=c
b[r+1]-=c
这样的话：
a[l]=b[0]+b[1]+......+b[l-1]+b[l]+c=a[l]+c
a[l+1]+c=b[0]+b[1]+......+b[l-1]+b[l]+c+b[l+1]
......
a[r]+c=b[0]+b[1]+......+b[l]+c......+b[r-1]+b[r]
a[r+1]=b[0]+b[1]+......+b[l]+c......+b[r-1]+b[r]+b[r+1]-c
差分的非朴素构造：
对于一个一维数组，可以通过上面的简单构造b数组来实现
若为非一维数组则可以如下方法进行构造：以二维数组为例
将数组a[i] [j] 假设为全0数组，则b[i] [j]也为全0
这样对a[i] [j]中的每一项之间进行插入操作
b[i][j]+=c //将ij矩形内的数加上常数c
b[i-1][j]-=c
b[i][j-1]-=c//减去(i-1,j) (i,j-1)矩形内增加的常数c
b[i-1][j-1]+=c//(i-1,j-1)//矩形内的数做过+c—c—c的操作，需要再次—c恢复到初始状态
将a[i] [j] 的每个数之间插入a[i] [j]的值即为b[i] [j]的值
例如在a[0] [0]与a[1] [0]之间插入a[1] [0]的值（在假设a数组为全0的情况下）
应用：二维差分
在a[i] [j] ~ a[l] [r]区间内的所有数加上常数c
首先对a数组进行插入值的初始化：
void insert (int i,int j,int l,int r,int c){//i>l;j>r
b[i][j]+=c;
b[i-1][j]-=c;
b[i][j-1]-=c;
b[i-1][j+1]+=c;
}//定义插入函数
//假定a数组为a[m][n]
for (int u=0;u<m;u++)
for (int v=0;v<n;v++)
intsert (u,v,u,v,a[u][v]);//对b数组初始化
再对a数组间的指定段进行插入操作
则可得到答案