Acwing-基础算法课笔记之基础算法（差分）
Acwing-基础算法课笔记之基础算法（差分）
- 一、一维差分
- 1、差分的概念
- 2、差分思想
- 二、二维差分
- 操作流程
一、一维差分
1、差分的概念
对于一个给定的序列a，它的差分序列b定义为：
b
[
1
]
=
a
[
1
]
b[1]=a[1]
b[1]=a[1]，
b
[
i
]
=
a
[
i
]
−
a
[
i
−
1
]
b[i]=a[i]-a[i-1]
b[i]=a[i]−a[i−1]，
(
2
⩽
i
⩽
n
)
(2\leqslant i\leqslant n)
(2⩽i⩽n)
b是a的差分序列，a是b的前缀和序列，差分与前缀和是一对互逆运算。
a
[
1
]
=
b
[
1
]
a[1]=b[1]
a[1]=b[1]，
a
[
2
]
=
b
[
2
]
+
a
[
1
]
=
b
[
2
]
+
b
[
1
]
a[2]=b[2]+a[1]=b[2]+b[1]
a[2]=b[2]+a[1]=b[2]+b[1]，
a
[
3
]
=
b
[
3
]
+
a
[
2
]
=
b
[
3
]
+
b
[
2
]
+
b
[
1
]
a[3]=b[3]+a[2]=b[3]+b[2]+b[1]
a[3]=b[3]+a[2]=b[3]+b[2]+b[1]，证毕
2、差分思想
把序列a的区间
[
l
,
r
]
[l,r]
[l,r]加d，等价于其差分序列b的点
b
[
l
]
b[l]
b[l]加d，点
b
[
r
+
1
]
b[r+1]
b[r+1]减d，其他位置不变。即把原序列的“区间操作”转化为差分序列的“两点操作”。多次区间操作完成后，再利用前缀和还原。时间复杂度从
O
(
n
2
)
O(n^2)
O(n2)降为
O
(
n
)
O(n)
O(n)
二、二维差分
操作流程
| （x1,y1） | * | * | * | * | |||
| * | * | * | * | * | |||
| * | * | * | * | * | |||
| * | * | * | * | （x2,y2） | |||
①
b
[
x
1
,
y
1
]
+
=
c
b[x1,y1]+=c
b[x1,y1]+=c：坐标
(
x
1
,
y
1
)
(x1,y1)
(x1,y1)右下区域的所有数加
c
c
c；
②
b
[
x
2
+
1
,
y
1
]
−
=
c
b[x2+1,y1]-=c
b[x2+1,y1]−=c：坐标
(
x
2
+
1
,
y
1
)
(x2+1,y1)
(x2+1,y1)右下区域的所有数减
c
c
c；
③
b
[
x
1
,
y
2
+
1
]
−
=
c
b[x1,y2+1]-=c
b[x1,y2+1]−=c：坐标
(
x
1
,
y
2
+
1
)
(x1,y2+1)
(x1,y2+1)右下区域的所有数减
c
c
c；
④
b
[
x
2
,
y
2
]
+
=
c
b[x2,y2]+=c
b[x2,y2]+=c：坐标
(
x
2
,
y
2
)
(x2,y2)
(x2,y2)右下区域的所有数多减了
c
c
c，所以要全部加
c
c
c。