区间加多项式问题的研究
riteme.site

区间加多项式问题的研究

问题描述

给定一个长度为 $n$,初始值全为 $0$ 的序列 $A[1..n]$,要求支持以下两种操作:

  • 修改操作:每次给定一个区间 $[l, r]$ 以及一个 $K$ 次多项式 $P(x)$,要求将 $[l, r]$ 的第 $k$ 项加上 $P(k)$。也就是 $A[l + k - 1]$ 加上 $P(k)$,对于所有的 $1 \leqslant k \leqslant r - l + 1$
  • 查询操作:查询操作分为两种 (i) 给定位置 $k$,要求输出 $A[k]$ 的值 (单点查询); (ii) 给定区间 $[l, r]$,要求输出区间 $[l, r]$ 内所有数之和,即 $\sum_{k = l}^r A[k]$(区间查询)。

记操作总数为 $q$,修改操作中多项式的最高次数为 $K$,并且 $K$$n$$q$ 相比较小。本文的目的是针对修改操作和区间查询给出一个 $O((n + q)K \log n)$在线算法以及一个 $O(qK \log q)$离线算法

解决方案

在线算法

我们可以首先考虑一个简化的修改操作:每次指定区间为 $[1..n]$,也就是整个序列。实际上我们只用保存一个多项式 $Q(x)$,每次修改操作就将 $P(x)$ 加到 $Q(x)$ 上,修改后的序列中 $A[k]$ 实际上就是 $Q(k)$。如果我们花费 $\Theta(nK)$ 的时间来计算一个表 $F(n, k) = \sum_{x = 1}^n x^k$,即 $x^k$ 的前缀和,就可以在单次 $\Theta(K)$ 的时间内计算出 $A$ 的区间和。

回到原先的问题,发现 $P(x)$ 不仅在序列中的起始位置变了,而且管辖范围也缩减到 $[l, r]$。为了尽可能简化问题,我们尝试对多项式进行处理。我们希望 $P(k) = A[k]$ 而不是 $P(k) = A[l + k - 1]$,不难发现我们所需要做的,就是函数的平移:$P'(x) = P(x - l + 1)$。这样做的好处在于,修改操作变为了对整个序列的修改,但是只在指定的区间有作用。经过平移之后,不同的多项式可以按照之前的方式累加并且正确地计算结果,因此,只要配合平衡树或线段树之类的数据结构即可快速解决区间问题。具体而言,就是对序列的每一个位置维护一个多项式,修改时,将平移后的多项式 $P'(x)$ 加到区间 $[l, r]$ 上的每一个位置,并利用线段树上的节点来存储必要的信息用于计算区间和。这一部分的时间复杂度是 $O(qK \log n)$,至于使用数据结构处理区间加的过程这里就不详细讨论了。

现在的问题是我们需要得到 $P'(x)$ 的系数表达形式才能方便地加减。设 $P(x) = \sum_{k = 0}^K a_k x^k$,以及平移量 $c$,那么 $P'(x) = P(x + c) = \sum_{k = 0}^K a_k (x + c)^k$。这显然可以直接用二项式定理在 $\Theta(K^2)$ 的时间复杂度内展开。但是这种形式的式子普遍可以转化为卷积1,从而能够利用 FFT 算法来加速。为了达到这一点,考虑利用二项式定理展开并进行整理:
$$ \begin{aligned} \sum_{k = 0}^K a_k(x + c) ^k & = \sum_{k = 0}^K a_k \sum_{j = 0}^k \binom{k}{j} x^j c^{k - j} = \sum_{j = 0}^K x^j \sum_{k = j}^K \binom{k}{j}a_k c^{k - j} \\ & = \sum_{j = 0}^K {x^j \over j!} \sum_{k = j}^K k!\ a_k \cdot {c^{k - j} \over (k - j)!} \\ & = \sum_{j = 0}^K {x^j \over j!} \sum_{t = 0}^{K - j} (j + t)!\ a_{j + t} \cdot {c^t \over t!} ~~~~ (t = k - j)\\ \end{aligned} $$
此时右边的式子已经变成了一个卷积的形式。令 $B_k = (K - k)! \ a_{K - k}$$C_k = c^k / k!$,那么:
$$ P'(x) = \sum_{j = 0}^K {x^j \over j!} \sum_{t = 0}^{K - j}B_{K - j - t} \cdot C_t $$
$F(n) = \sum_{k = 0}^n B_k \cdot C_{n - k}$$F(n)$ 可以用 FFT 算法在 $\Theta(K \log K)$ 的时间内计算出来,此时:
$$ P'(x) = \sum_{j = 0}^K {F(K - j) \over j!} x^j $$

因此,我们可以在 $\Theta(K \log K)$ 的时间复杂度内完成多项式平移。结合数据结构,我们可以在 $O(nK + qK(\log n + \log K)) = O((n + q)K \log n)$ 的时间复杂度解决区间加多项式问题。

离线算法

接下来的目标是让时间复杂度变得与序列长度 $n$ 无关。考虑求区间和的一种离线算法:扫描线算法。

scanline-example

(Fig.1. 扫描线算法的一个示例。$6$ 个方格代表序列 $X[1..6]$。上面的操作是将区间 $[2, 4]$ 都加上 $3$;下面的是扫描线的过程,首先将原序列视为差分序列,在位置 $2$ 加上 $3$,位置 $4$ 减去 $3$,模拟一根扫描线从 $1$ 一直扫描到 $6$,其中遇到正数就给 $A$ 加上,遇到负数则相应地减去,这样扫描线扫到哪里,$A$ 的值就是那个位置的值)

为了方便,我们先只考虑单点查询。由于需要支持修改过程中的查询,所以对每个操作记录一个时间戳 $t$,特别的,第一个操作的时间戳是 $1$。如果是修改操作,则当前时间加 $1$,而查询操作不必增加时间。这样对于每一个单点查询以及它的时间戳 $t$,只需要将所有时间戳不大于 $t$ 的区间覆盖了当前位置的修改操作的多项式加起来,就可得到当前位置的多项式,从而可以计算这个位置的值。因此我们在扫描线的过程中维护一个数据结构(平衡树/线段树),按照时间戳的顺序来维护所有的修改操作的多项式。对于每个修改操作,在区间开始的位置加一个“添加”事件,区间末尾加一个“删除”事件,执行相应的事件时就将数据结构中的对应多项式插入或删除;而对于查询操作,就只需查询前缀和即可。实际上,如果某个位置没有任何事件,那么这个位置就可以直接跳过,因为它不会对我们的数据结构产生任何影响,从而可以在 $O(qK \log q)$ 的时间复杂度下完成区间修改/单点查询问题。

现在来考虑区间查询。我们知道,利用前缀和,可以将区间和变为两个单点值之差。利用这一点,不难想到我们可以直接将多项式 $P(x)$ 变成自己的前缀和多项式,即 $P'(x) = \sum_{k = 1}^x P(k)$,这样我们维护的实际上就是原序列的前缀和序列,成功地将区间查询问题转化为了单点查询问题。我们知道,$K$ 次多项式的前缀和是 $K + 1$ 次多项式,而计算多项式前缀和有很多公式或方法:伯努利公式(又称 Faulhaber’s formula)、离散微积分、子集反演或者多项式插值。但它们都是针对 $k$ 次单项式(即 $x^k$)的公式,并且计算复杂度都是 $\Theta(k)$,如果运用到任意 $K$ 次多项式,就又需要 $\Theta(K^2)$ 的时间。

到了这种时候,我们可能又会想要 FFT 出场了。在此之前,我们需要选择一个便于变形的公式。我经过一番挑选,发现还是伯努利公式形式最优秀:
$$ \sum_{k = 1}^x k^n = 1^n + 2^n + \cdots + x^n = \frac1{n+1}\sum_{k = 0}^n \binom{n + 1}{k} B_k x^{n + 1 - k} \tag{Bernoulli's Formula} $$
其中 $B_k$ 表示伯努利数,并且 $B_1 = +1/2$2。伯努利数可以通过多项式逆元快速计算,具体可以查看这里。或者当 $K$ 足够小时,我们可以直接将需要的伯努利数存入程序。

接下来又要经过一番套路变形:
$$ \begin{aligned} \sum_{k = 1}^x P(k) & = \sum_{k = 1}^x \sum_{j = 0}^K a_j k^j = \sum_{j = 0}^K a_j \sum_{k = 1}^x k^j \\ & = \sum_{j = 0}^K {a_j \over j + 1} \sum_{k = 0}^j \binom{j + 1}{k} B_k x^{j + 1 - k} \\ & = \sum_{j = 0}^K {a_j \over j + 1} \sum_{t = 0}^j \binom{j + 1}{j - t} B_{j - t} x^{t + 1} ~~~~ (t = j - k) \\ & = \sum_{t = 0}^K x^{t + 1} \sum_{j = t}^K {a_j \over j + 1} \binom{j + 1}{j - t} B_{j - t} \\ & = \sum_{t = 0}^K {x^{t + 1} \over (t + 1)!} \sum_{j = t}^K j!\ a_j \cdot {B_{j - t} \over (j - t)!} \\ & = \sum_{t = 0}^K {x^{t + 1} \over (t + 1)!} \sum_{j = 0}^{K - t} (j + t)!\ a_{j + t} \cdot {B_j \over j!} \end{aligned} $$
Alright!3又是熟悉的面孔。故技重施,令 $C_k = (K - k)!\ a_{K - k}$$D_k = B_k / k!$,右边就变成了卷积的形式。因此我们可以在 $\Theta(K \log K)$ 的时间复杂度内计算多项式前缀和的表达式。结合之前单点查询的算法,如果允许离线操作,区间加多项式问题可以在 $O(qK \log q)$ 的时间复杂度内解决。另外,将区间和转化为单点差之后,实际上还可以使用动态开点的数据结构来实现在线算法,时间复杂度是 $O(qK \log n)$ 的。

最后,我自己使用 C++ 实现了离线算法,如果想要查看可以前往 我的 GitHub


  1. 卷积是针对两个序列 $A[0..n]$$B[0..n]$ 而言的。定义卷积 $C = A \times B$,则 $C(n) = \sum_{k = 0}^n A(k) \cdot B(n - k)$,这一过程可以视为多项式乘法,故可以使用 FFT(快速傅里叶变换)来实现,时间复杂度为 $\Theta(n \log n)$。 

  2. 有一些地方的会使用 $B_1 = -1/2$ 的伯努利数。 

  3. “But your spelling is alwrong.” —— Concrete Mathematics 


标签: 数据结构 多项式 FFT 伯努利数
创建时间: 2018.01.28
上次修改: 2018.01.28
统计: 5138 字 / 约 20 分钟


数学公式渲染引擎:

KaTeX 渲染效率很高,但是目前 KaTeX 容错性不强,因此使用 KaTeX 时可能会存在一些数学公式无法渲染的情况
先使用 KaTeX 渲染,再使用 MathJax 渲染