差分笔记

差分笔记

差分可看作前缀和的逆运算

对于一个数组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数组间的指定段进行插入操作

则可得到答案