差分序列

发表于 更新于 分类于 ， 阅读次数： 本文字数： 582 阅读时长 ≈ 2 分钟

本文将介绍差分序列的定义及其应用。

差分序列（数组）

差分序列的定义

给定一个序列 a, a[i] 表示序列的第 i 个元素（编号从 0 开始），则其差分序列为：

1
2
d[0] = a[0]  (i == 0)
d[i] = a[i] - a[i-1]  (i > 0)

差分序列示例

索引 i 0 1 2 3 4 5 6 7
原始序列 a[i] 0 2 5 4 9 7 10 0
差分序列 d[i] 0 2 3 -1 5 -2 3 -10

现在假设将区间 a[1, 4] 所有的数都加上 3，则：

索引 i 0 1 2 3 4 5 6 7
原始序列 a[i] 0 2+3=5 5+3=8 4+3=7 9+3=12 7 10 0
差分序列 d[i] 0 2+3=5 3 -1 5 -2-3=-5 3 -10

然后将区间 a[3, 5] 所有的数都减去 5，则：

索引 i 0 1 2 3 4 5 6 7
原始序列 a[i] 0 2+3=5 5+3=8 4+3=7-5=2 9+3=12-5=7 7-5=2 10 0
差分序列 d[i] 0 2+3=5 3 -1-5=-6 5 -2-3=-5 3+5=8 -10

差分序列的性质

仔细观察上面的示例，可以发现：

1
2
3
a[2] = d[2] + a[1]
     = d[2] + d[1] + a[0]
     = d[2] + d[1] + d[0]

根据定义，对原序列区间操作后，原序列最终各项值为：

1
2
a[0] = d[0]  (i == 0)
a[i] = d[i] + a[i-1]  (i > 0)

也即 a[i] 为 d[i] 的前缀和：

1
a[i] = d[0] + ... + d[i]

差分序列的应用

基于差分序列的性质，它主要用于快速处理区间加减操作和单点查询

快速处理区间加减操作

假如现在对 a[L, R] 区间上所有的数加上 delta，由以上的性质可知，第一个受影响的差分数组中的元素为 d[L]，即令 d[L] += delta，那么后面数列元素在计算过程中都会加上 delta；最后一个受影响的差分数组中的元素为d[R]，所以令 d[R+1] -= delta，即可保证不会影响到 R 以后数列元素的计算。这样我们不必对区间内每一个数进行处理，只需处理两个差分后的数即可。

简单来说，当对 a[L, R] 区间所有数进行加 delta 操作时，只需:

1
2
d[L] += delta
d[R+1] -= delta

那么此时计算 a[L] ... a[R] 都会加上 delta，这里用 (d[L] + delta) 表示归约后的 d[L]，则有：

1
2
3
4
a[L] = (d[L] + delta) + a[L-1]
a[L+1] = d[L+1] + a[L] = d[L+1] + (d[L] + delta) + a[L-1]
...
a[R] = d[R] + a[R-1] = d[R] + ... + (d[L] + delta) + a[L-1]

单点查询（求差分序列前缀和）

改变 d 数组

1
2
for i in range(1, n):
    d[i] += d[i-1]

改变 a 数组

1
2
3
a[0] = d[0]
for i in range(1, n):
    a[i] = d[i] + a[i-1]

References

https://www.cnblogs.com/COLIN-LIGHTNING/p/8436624.html