树状数组区间修改 一维&二维差分
_Cheems
·
·
个人记录
树状数组的区间修改
差分数组 c[i]=a[i]-a[i-1]，则有 a[i]=c[1]+c[2]+...+c[i]。
因此，a[1]+a[2]+...+a[x]
=c[1]+c[1]+c[2]+...+c[1]+c[2]+...c[x]
=x*c[1]+(x-1)*c[2]+...+c[x]
=\sum_{i=1}^{x}(x-i+1)*c[i]
运用数学思想，将变量和常量拆开得：
=\sum_{i=1}^{x}(x+1)*c[i]-\sum_{i=1}^{x}i*c[i]
不妨设 A=\sum_{i=1}^{x}c[i]，B=\sum_{i=1}^{x}i*c[i]，则：
=(x+1)*A-B
我们只需用树状数组维护 A 和 B 即可。
二维差分
通过定义理解二维差分较难，不妨画图看看。
首先我们知道，给 c[i][j]+k，则等同于将左上角为 (i,j)、右下角为 (n,m) 的矩阵的每个数 +k。
那么，考虑给左上角为 (x1,y1)、右下角为 (x2,y2) 的矩阵 +k，如何操作？
-
c[x1][y1]+k
-
c[x1][y2+1]-k
-
c[x2+1][y1]-k
-
c[x2+1][y2+1]+k
可画图理解。简单地说，就是先加（第一步）；加了发现有的不该加就减去（二三步）；由于减了两次，所以还要加回去（第四步）。
至于初始化，有一种巧妙做法：初始化数组为 0，在 i,j 加入 k ，等同于将左上角为 (i,j)、右下角为 (i,j) 的矩阵加 k，很好写。
二维区间修改
结合上述两种思想。
\sum_{i=1}^{x}\sum_{j=1}^{y}a[i][j]
=\sum_{i=1}^{x}\sum_{j=1}^{y}\sum_{k=1}^{i}\sum_{h=1}^{j}c[i][j]
建议画图看看，c[i][j] 被多少个 a[i][j] 使用？每个 c[i][j] 被用了(x-i+1)(y-j+1) 次。
然后把 i、j 单独拎出来。
=\sum_{i=1}^{x}\sum_{j=1}^{y}((x+1)*(y+1)*c[i][j]-(y+1)*c[i][j]*i-(x+1)*c[i][j]*j+c[i][j]*i*j)
像一维一样，设四个树状数组维护即可。