跳转至

序列差分#
发布于2020-12-04
上次编辑2021-04-20

Introduction

使用序列差分技术可以维护多次对序列的一个区间加上一个数，并在最后询问某一位的数或是多次询问某一位的数。

差分序列与前缀和序列#

对于序列 \(A=[a_1,\cdots,a_n]\)，它的差分序列为 \(B=[b_1,b_2,\cdots,b_n]=[a_1,a_2-a_1,\cdots,a_n-a_{n-1}]\)，即

\[ b_i=\begin{cases} a_i-a_{i-1}& (i\ge2)\\ a_1&(i=1) \end{cases} \]

对于序列 \(A\) 中的每一个元素 \(a_i\)，有

\[ \begin{aligned} a_i&=(a_i-a_{i-1})+(a_{i-1}-a_{i-2})+\cdots+(a_2-a_1)+(a_1)\\ &=b_i+b_{i-1}+\cdots+b_2+b_1 \\ &=\sum_{j=1}^ib_i \end{aligned} \]

也就说序列 \(A\) 得到的 差分序列 \(B\) 的 前缀和序列 就是序列 \(A\) 本身。

应用#

对于序列 \(A=[a_1,\cdots,a_n]\)，计算 \(A\) 中下标在 \([L,R]\) 中每一个元素加上 \(k\) 之后的结果，即计算\(A\) 变化后的序列 \(\hat{A}=[a_1,a_2,\cdots,\underbrace{a_L+k,\cdots,a_R+k},\cdots,a_n]\) 中的每一项。

首先计算 \(A\) 的差分序列 \(B\)，然后改变两个元素即可：

  • \(b_L=b_L+k\)
  • \(b_{R+1}=b_{R+1}-k\)

然后有：

  • 当 \(i \in [1,L-1]\) 时，
\[ \begin{aligned} \hat{a_i}&=b_1+b_2+\cdots+b_i\\ &=(a_1)+(a_2-a_1)+\cdots+(a_i-a_{i-1})\\ &=a_i \end{aligned} \]
  • 当 \(i \in [L,R]\) 时，
\[ \begin{aligned} \hat{a_i}&=b_1+b_2+\cdots+\boxed{b_L}+\cdots+b_i\\ &=(a_1)+(a_2-a_1)+\cdots+\boxed{(a_L-a_{L-1}+k)}+\cdots+(a_i-a_{i-1})\\ &=a_i+k \end{aligned} \]
  • 当 \(i \in [R+1,n]\) 时，
\[ \begin{aligned} \hat{a_i}&=b_1+b_2+\cdots+\boxed{b_L}+\cdots+\boxed{b_{R+1}}+\cdots+b_i\\ &=(a_1)+(a_2-a_1)+\cdots+\boxed{(a_L-a_{L-1}+k)}+\cdots+\boxed{(a_{R+1}-a_{R}-k)}+\cdots+(a_i-a_{i-1})\\ &=a_i \end{aligned} \]

使用序列差分可以将多次这样的区间变化操作降低到线性时间复杂度。

如对于下面的例子，\(A\) 为一个整数序列，\(P\) 为每次变化的区间，\(K\) 为每次增加的数。

1
2
3
A = [1, 2, 3, 4, 5]
K = [1, 2, 3]
P = [[1, 2], [2, 4], [0, 4]]

使用循环的过程为：

\[ \begin{aligned} &1, 2, 3, 4, 5\\ &1, \boxed{3, 4}, 4, 5\\ &1, 3, \boxed{6, 6, 7}\\ &\boxed{4, 6, 9, 9, 10}\\ \end{aligned} \]

代码为：

1
2
3
4
5
6
7
from typing import List
def solve_1(A: List[int], K: List[int], P: List[List[int]]) -> List[int]:
    for i, k in enumerate(K):
        for j in range(P[i][0], P[i][1] + 1):
            A[j] += k
        print(A)
    return A

时间复杂度为 \(\mathcal{O}{\sum_{i=0}^m{R_i-L_i+1}}\), \(m\) 为操作的次数，\([L_i,R_i]\) 为每次变化的下标区间。

使用序列差分的做法如下：

\[ \begin{aligned} &[1, 2, 3, 4, 5]\\ &[1, 1, 1, 1, 1, 0] \Leftarrow 差分\\ &[1, \boxed{2}, 1, \boxed{0}, 1, 0]\\ &[1, 2, \boxed{3}, 0, 1, \boxed{-2}]\\ &[\boxed{4}, 2, 3, 0, 1, \boxed{-5}]\\ &[4, 6, 9, 9, 10] \Leftarrow 前缀和 \end{aligned} \]
1
2
3
4
5
6
7
8
9
from itertools import accumulate
from typing import List
def solve_2(A: List[int], K: List[int], P: List[List[int]]) -> List[int]:
    B = [A[0]] + [A[i] - A[i - 1] for i in range(1, len(A))] + [0]
    for i, k in enumerate(K):
        B[P[i][0]] += k
        B[P[i][1] + 1] -= k
    A[::] = list(accumulate(B[:-1]))
    return A

时间复杂度为 \(\mathcal{O}(\max(m,n))\)，\(m\) 为操作的次数，\(n\) 为序列 \(A\) 的长度。

例题#

  1. https://oi-wiki.org/basic/prefix-sum/ ↩

返回顶部

在手机上阅读