前缀和与差分数组

一维前缀和

一维前缀和定义：一维数组arr的前缀和sum满足

根据上述公式求任意区间和

一维差分数组

场景：一个一维数组arr=[1,3,7,5,2],对arr进行m次操作，每次操作把arr[L,R]范围内的元素加上V

一维数组的差分数组定义：

一个数组的差分数组的前缀和就是原数组

差分标记
arr[L,R]+V<==>d[L]+V,d[R+1]−V,再对d求前缀和arr[L,R] + V <==> d[L] + V, d[R+1] – V , 再对d求前缀和arr[L,R]+V<==>d[L]+V,d[R+1]−V,再对d求前缀和

举例说明：
arr = [0, 0, 0, 0, 0, 0, 0, 0]
d = [0, 0, 0, 0, 0, 0, 0, 0]
要实现 arr[2, 4] + 1
按照上述方式
d[2] + 1 操作后  d = 0 0 1 0 0 0 0 0
              arr = 0 0 1 1 1 1 1 1
d[5] - 1 操作后  d = 0 0 1 0 0 -1 0 0
               arr = 0 0 1 1 1 0 0 0 

二维前缀和

二维数组前缀和

矩阵和定义：
sum[i][j]是从
(0,0)到
(i,j)的和

注意：
如果
i = 0 && j = 0 那么
sum[0][0] = g[0][0]
如果
i = 0 那么
sum[0][j] = sum[0][j-1] + g[0][j]
sum{0, y1}{0, y2} = sum[0][y2] - sum[0][y1]
如果
j=0 那么
sum[i][0] = sum[i-1][0] + g[i][0]
sum{x1,0}{x2, 0} = sum[x2][0] - sum[x1][0]

二维差分

已知二维数组g和它的差分数组d，对数组g进行操作g[x1,y1][x2,y2]+Vg[x_1, y_1][x_2, y_2] + Vg[x1​,y1​][x2​,y2​]+V 等价于

再对d求前缀和