区间加多项式问题的研究

问题描述

给定一个长度为 $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)$ 的时间复杂度内展开。但是这种形式的式子普遍可以转化为卷积¹，从而能够利用 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$ 无关。考虑求区间和的一种离线算法：扫描线算法。

为了方便，我们先只考虑单点查询。由于需要支持修改过程中的查询，所以对每个操作记录一个时间戳 $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$²。伯努利数可以通过多项式逆元快速计算，具体可以查看这里。或者当 $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！³又是熟悉的面孔。故技重施，令 $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。