前缀和&差分&二维前缀和
前缀和是一个数组的某项下标之前的所有数组元素的和。
差分是一个数组相邻两元素的差,一般为下标靠后的减去靠前的一个。
若用D(a)表示a的前缀和数组,F(a)表示a的差分数组
1.D(x)=a
2.F(d)=a
d[i]=a[i]+a[i-1]+a[i-2]+……+a[1],d[i-1]=a[i-1]+a[i-2]+……+a[1];
F(d): x[i]=d[i]-d[i-1]=(a[i]+a[i-1]+a[i-2]+……+a[1])-(a[i-1]+a[i-2]+……+a[1])=a[i];
前缀和推广到二维中则
由于我们需要用已求得的d[l][r]来求出d[i][j],所以可以用以下方式预处理出二维前缀和。参照下图,根据容斥原理(多加了的要减回来)
计算sum[l,r][m,n]:
举个栗子
给定矩阵
1 4 8
6 7 2
3 9 5
得到对应差分数组
1 3 4
5 -2 -9
-3 5 1
当我们想要将一个矩阵加上x时
0 0 0 0 0
0 +x 0 0 -x
0 0 0 0 0
0 0 0 0 0
0 -x 0 0 +x
通过这个修改差分
就可以得到
0 0 0 0 0
0 x x x 0
0 x x x 0
0 x x x 0
0 0 0 0 0
于是区间修改就完成了