二维差分数组构造:
(bleft [ i ight ]left [ j ight ]=aleft [ i ight ]left [ j ight ]-aleft [ i-1 ight ]left [ j ight ]-aleft [ i ight ]left [ j-1 ight ]+aleft [ i-1 ight ]left [ j-1 ight ])
这个式子配着二维前缀和还是挺好理解哒~
(b)为差分数组,(a)为原数组
二维差分的维护:
一维差分是在需要更新的位置开始,在不需要的位置结束,那么二维的也一样。
例如:我们要在以(x1,y1)为左上角,以(x2,y2)为右下角的矩阵区间的所数都加上一个值(x)
(x1,y1) | ||||
(x2,y2) | ||||
如果我们要在区间开始的位置(+x),根据前缀和的思想,它影响的就是整个表格区域
那么就多影响了下面的图标区域:
(x1,y1) | ||||
(x2,y2) | ||||
所以在上述图标部分(-a)消除(+a)的影响:
(bleft [ x1 ight ]left [y1 ight ]+=x)
(bleft [ x1 ight ]left [y2+1 ight ]-=x)
(bleft [ x2+1 ight ]left [y1 ight ]-=x)
(bleft [ x2+1 ight ]left [y2+1 ight ]-=x)多减的加上