Python差分
差分数组
- 对于一个数组 a [ ] a[] a[]，差分数组 d i f f [ ] diff[] diff[] 的定义是： d i f f [ i ] = a [ i ] − a [ i − 1 ] diff[i]=a[i]-a[i-1] diff[i]=a[i]−a[i−1]
- 对差分数组做前缀和可以还原为原数组： d i f f [ 1 ] + d i f f [ 2 ] + d i f f [ 3 ] + . . . + d i f f [ i ] = a [ 1 ] + ( a [ 2 ] − a [ 1 ] ) + ( a [ 3 ] − a [ 2 ] ) + . . . + ( a [ i ] − a [ i − 1 ] ) = a [ i ] diff[1]+diff[2]+diff[3]+...+diff[i]=a[1]+(a[2]-a[1])+(a[3]-a[2])+...+(a[i]-a[i-1])=a[i] diff[1]+diff[2]+diff[3]+...+diff[i]=a[1]+(a[2]−a[1])+(a[3]−a[2])+...+(a[i]−a[i−1])=a[i]
- 原数组执行区间加法 [ l , r ] [l,r] [l,r] 都加上 x x x，对于差分数组而言： d i f f [ l ] + = x , d i f f [ r + 1 ] − = x diff[l]+=x, diff[r+1]-=x diff[l]+=x,diff[r+1]−=x
- 差分数组可以实现快速的区间加法，最终只需要对差分数组求前缀和就能得到原数组
- 无法边修改边查询，只能先修改，后查询
- d i f f [ l ] + = x diff[l]+=x diff[l]+=x：相当于从 l l l 往后全部的数字都加上 x x x
- d i f f [ r + 1 ] − = x diff[r+1] -=x diff[r+1]−=x：相当于从 r + 1 r+1 r+1 往后全部数字都减去 x x x
# 构造差分数组
diff = [0] * (n + 1)
diff[0] = a[0]
for i in range(1, n):
diff[i] = a[i] - a[i - 1]
# 区间更新
for _ in range(m):
x, y, z = map(int, input().split())
x, y = x - 1, y - 1
diff[x] += z
diff[y + 1] -= z
# 求前缀和
a[0] = diff[0]
for i in range(1, n):
a[i] = a[i - 1] + diff[i]
二维差分数组
-
差分数组的前缀和 = 原数组
-
因此先回顾二维数组前缀和： s u m i , j = s u m i − 1 , j + s u m i , j − 1 − s u m i − 1 , j − 1 + a i , j sum_{i,j}=sum_{i-1,j}+sum_{i,j-1}-sum_{i-1,j-1}+a_{i,j} sumi,j=sumi−1,j+sumi,j−1−sumi−1,j−1+ai,j
-
上述的 s u m sum sum 替换成 a a a， a a a 替换成 d i f f diff diff，就可以得到二维差分数组： d i f f i , j = a i , j − a i − 1 , j − a i , j − 1 + a i − 1. j − 1 diff_{i,j}=a_{i,j}-a_{i-1,j}-a_{i,j-1}+a_{i-1.j-1} diffi,j=ai,j−ai−1,j−ai,j−1+ai−1.j−1
-
矩阵 ( x 1 , y 1 ) − ( x 2 , y 2 ) (x_1,y_1)-(x_2,y_2) (x1,y1)−(x2,y2) 需要增加元素 x x x：
d i f f [ x 1 ] [ y 1 ] + = x diff[x_1][y_1]+=x diff[x1][y1]+=x
d i f f [ x 1 ] [ y 2 + 1 ] − = x diff[x_1][y_2+1]-=x diff[x1][y2+1]−=x
d i f f [ x 2 + 1 ] [ y 1 ] − = x diff[x_2+1][y_1]-=x diff[x2+1][y1]−=x
d i f f [ x 2 + 1 ] [ y 2 + 1 ] + = x diff[x_2+1][y2+1]+=x diff[x2+1][y2+1]+=x
详见个人博客：差分