二维差分
定义
类比一维差分的定义，二维差分的定义如下
bi,j=ai,j−ai−1,j−ai,j−1+ai−1,j−1
性质类似于一维差分，对 b 做二维前缀和可以直接得到原数组 a 的值。
子矩阵的修改
当我们需要在以 (x1,y1) 为左上角，(x2,y2) 为右下角形成的子矩阵全部加 c 可以通过如下式子完成。
- bx1,y1+c
- bx1,y2+1−c
- bx2+1,y1−c
- bx2+1,y2+1+c
证明可以参考下图：
类比一维差分，执行 bl+c 以后会给 al∼an 都加 c
那么在二维当中。
- bx1,y1+c，会造成图中 绿 + 蓝 + 橙 + 黄 这四部分都加 c
- bx1,y2+1−c，会造成图中 绿 + 蓝 这两部分都减 c
- bx2+1,y1−c，会造成图中 绿 + 橙 这两部分都减 c
- bx2+1,y2+1+c，会造成图中 绿 这两部分都加 c
最终通过一系列抵消操作，可以实现只给黄色区域全部加 c
还原原数组
还原原数组就是对 b 直接做二维前缀和。
执行 b[i][j] += b[i -1][j] + b[i][j - 1] - b[i - 1][j - 1]
或通过定义还原，在定义中
bi,j=ai,j−ai−1,j−ai,j−1+ai−1,j−1
则
ai,j=ai−1,j+ai,j−1−ai−1,j−1+bi,j
