发表于 更新于

前缀和/差分数组

快速计算某个区域元素的和

1
2
3
for(i=1;i<=n;i++){
	dif[i]=dif[i-1]+a[i-1];
}

​ 这里我们用到了两个数组，一个是前缀和数组，还有一个是目标数组，即将每一小段的和储存在前缀和数组中，当我们需要多次求子数组的和时，我们可以通过两个下标的差值来求出子段和。

​ 比如有一个数组中的元素[2,8,3,5,7],其前缀和数组为[0,2,10,13,18,25]（注意，差分数组的第一位默认初始化）则第3到第5个元素之和为

1
sum=dif[5]-dif[2];

现在我们来讨论一下二维数组中的前缀和数组，比如给你两个坐标，左上角和右下角，求出该区块中所有元素之和。

1
2
3
4
5
for(i=1;i<=n;i++){
		for(j=1;j<=n;j++){
			dif[i][j]=dif[i-1][j]+dif[i][j-1]-dif[i-1][j-1]+a[i][j];
		}
	}

同理一维数组，我们先求出该二维数组的前缀和数组，我们可以将它想象为一个个矩形，每个区间的值就是面积，那么从(0，0)到(i，j)的面积可以简化为从(0，0)到(i-1，j)的面积加上从0，0到(i，j-1)的面积在减去重复的(i-1，j-1)，最后再加上i，j所代表的面积，即a[i] [j]。

与上面不同的是，这里的dif数组的值直接代表了从（0，0）坐标点到目标点的总和，那么求某区块的和也就简单了，这里直接给出结论，相信聪明的你一定能够推导出来的。

1
sum=dif[x1][y1]-dif[x0-1][y1]-dif[x1][y0-1]+dif[x0-1][y0-1];

差分数组

快速修改某个区域的元素

同样，我们也用到了两个数组，一个是差分数组，还有一个是目标数组。那么什么是差分数组呢，就是数组里的每个元素对应目标数组中当前下标的元素减去前一个下标元素的值。值得注意的是，差分数组的第一个元素与目标数组的第一个元素的值相同。比如数组[2,3,8,5,7]对应的差分数组为[2,1,5,-3,2]。当我们要对某个区间的元素做同时加减的操作时，我们只要改变差分数组中开始下标的值与结束下标下一位的值即可。

1
2
3
4
5
6
7
for(i=1;i<=n;i++){
    cin>>a[i];
    if(i==1)dif[i]=a[i];
    else dif[i]=a[i]-a[i-1];
}
cin>>x1>>x2>>k;
dif[x1]+=k;dif[x2+1]-=k;//这里展示的是同时加上k的操作，若为减去k，则与之相反即可

这样当我们频繁地修改某区间的元素时，复杂组仅为O(1)，大大提高了速度