UOJ Logo EntropyIncreaser的博客

博客

浅谈高阶前缀和的动态维护

2018-05-29 19:36:49 By EntropyIncreaser

某天无聊,就把某题的结论扩展了一小下,其实也挺 naive 的,姑且发到这里娱乐一下吧……

摘要

对于单点修改,区间查询的问题在树状数组上可以实现。而对于区间修改通过线段树可以实现,区间查询本质上是维护一个 2 阶前缀和的问题,这个问题后来也被提出在树状数组上的解决方法。

而到拓展到高维的情况,或者对于更高阶的前缀和,仍然可以通过树状数组解决。下文我们对于一个 $\ell$ 维 $k$ 阶前缀和问题,可以在 $\Theta\left(nk\right)$ 预处理,单点操作 $\Theta\left( \left (k\log n \right)^\ell \right)$ 的效率内解决。

特别对于位置离散的情况,在一维情况下我们可以做到单点修改 $\Theta \left(k \left(\log k + \log n \right)\right)$,单点查询 $\Theta(k\log n)$ 的效率完成。

一些约定记号

$_\ell a_\mathbf{x}$ 表示一个 $\ell$ 维数组,在维度不重要的情况下会省略左下角的维度。其中 $\mathbf{x}$ 是坐标向量。

对向量的比较 $\mathbf y \le \mathbf x$ 为各分量的偏序关系比较,即

$$ \mathbf y \le \mathbf x \Leftrightarrow \forall 1 \le i \le \ell(\mathbf y_i \le \mathbf x_i) $$

定义两个数列的卷积 $(a * b)_n = \sum_{i = 1}^n a_i b_{n - i}$

对于一维前缀和,我们定义对于数列 $\{a_n\}$ 的前缀和 $\sigma(a)_n = \sum_{i = 1}^n a_i$ ,可以通过拆分求和符号得到性质 $\sigma(a)_n = \sigma(a)_{n - 1} + a_n$ 。

我们递归地定义 $k$ 阶前缀和 $\left\{\sigma^k(a)_n \right\}$ , 其中 $\sigma^0(a)_n = a_n$ :

$$ \sigma^k(a)_n = \sum_{i = 1}^n \sigma^{k - 1}(a)_i = \sigma^k(a)_{n - 1} + \sigma^{k - 1}(a)_n $$

对于高维数组的前缀和,我们定义为:

$$ \sigma^k(a)_{\mathbf x} = \sum_{\mathbf y \le \mathbf x} \sigma^{k - 1}(a)_{\mathbf y} $$

感觉创造了一堆冗余的东西呢……

卷积器

求和数列的重要性

考虑到卷积对点加构成分配律,那么记前缀和求和器数列为 $\sigma^k$ ,我们有

\begin{eqnarray*} \sigma^k(a + d) & = & (a + d) * \sigma^k \\ & = & \sigma^k(a) + d * \sigma^k \end{eqnarray*}

对于单点修改时,数列 $d$ 只在某个地方有值,所以等价于将 $\sigma^k$ 平移并乘上一常数。

与组合数的关联

对于求和数列,我们有它规约到组合数的通项公式:

$$\sigma^k_n = {n + k - 2 \choose n - 1}$$

由之前的定义,我们整理出求和数列的以下一些性质:

$$\sigma^k_1 = 1$$

$$\sigma^k_n = \sigma^{k - 1}_n + \sigma^k_{n - 1}$$

注意到这与组合数的性质非常相似:

$${n \choose 0} = 1$$

$${n \choose m} = {n - 1 \choose m - 1} + {n - 1 \choose m}$$

可以数学归纳法证明这一结论。

注意到当 $k$ 为常数的时候,这是一个关于 $n$ 的 $k - 1$ 次多项式。

$$ \sigma^k_n = \frac {n (n + 1) \cdots (n + k - 2)}{(k - 1)!} $$

高维推广

给出高维求和数列的通项公式:

\begin{eqnarray*} _\ell\sigma^k_{\mathbf n} & = & \prod_{i = 1}^\ell \sigma^k_{\mathbf n_i} \\ & = & \prod_{i = 1}^\ell {\mathbf n_i + k - 2 \choose k - 1} \end{eqnarray*}

注意到高维求和数列的取值是一个 $\ell$ 个元素的可重偏序集的可能取值数量,可以看出在计数时维度之间是独立的。故立得答案数量是各维度的乘积。

算法

树状数组维护多项式

根据之前的两条引理,我们可以得到:一个单点修改的 $k$ 阶前缀和的影响可以看做单点修改的一个组合数,而且恰好是 $k - 1$ 阶多项式,对于一个高维的情况,影响是在各维度上的乘积。

我们只需要 $\Theta(k^2)$ 的时间就可以计算出原多项式 $\sigma^k(x)$ ,发现系数的变换符合卷积形式,可以优化到 $\Theta(k\log k)$,不过在 $k$ 较小的时候并不重要。而在位置比较稠密的时候可以递推出每平移一格的多项式系数表达,因为 $\sigma^k(x)$ 是一个上升幂的形式,相邻平移只需要和一次多项式做乘除法。

在树状数组维护时,无论是修改还是查询,都只会进行 $\Theta(\log n)$ 次多项式加法,而询问完的多项式取值可以 $\Theta(k)$ 回答,所以这部分的时间是 $\Theta(k\log n)$ 。而对于高维的情况, 我们需要维护每一种 $x^ay^b\dots$ 的系数,总共有 $k^\ell$ 项,树状数组的时间也有变化。我们需要 $\Theta \left( (k\log n)^\ell\right)$ 的时间来完成。

如果在一维上的离散情况,我们则可以用一颗平衡树来维护,而其他部分的大致思想没有变。但考虑到位置是离散的,则不能对多项式进行预处理。

打脸

我这玩意不都被下降幂相关给研究透了吗?

例题

这玩意有什么用吗?答:当然没有啦!

1,「BJOI2018」链上二次求和

好吧……这个问题其实是我在 BJOI 之后扩展想的问题,最开始是想解决链上二次求和。

我个人的思路比较清奇,因为不喜分类讨论,故不想写那个分段二次函数插到线段树上面的方法,然后经过一波分析,发现可以用树状数组维护一个 4 阶前缀和。考场上因为之前耗在了一个被写错的 DP (而且到最后都是错的),到这道题就草草写了一个线性扫描的暴力水了 50 分。

具体的分析过程在我的这篇文章里面。

跑得常数也蛮小的,而且我消耗的内存似乎是最少的嘞

2,「APIO2016」Boat

我 yy 的算法确实是 $\Theta(n^3)$ 的,不过常数实在太大,开了各种优化也没卡过 uoj 的时限……

发现 DP 数组是一个被切成 $n + 1$ 段的函数,每段内部的函数都是很有规律的,可以归纳证明成上文“前缀和函数”的和,阶是 $n$ 级别的,即

$$f(x) = \sum_{k = 0}^n a_k \sigma^k(x)$$

那么这个时候我们就考虑别把它转成多项式,直接用这个东西的系数来存!

这样每次 DP 其实在累加前缀和的时候就是把系数都错位挪了一下,修改是 $\Theta(n)$ 的。

而对函数的一段求值也可以通过高阶前缀和间的乘除递推关系搞出 $\Theta(n)$ 的求法。

评论

jjikkollp
orzorzorz跪跪跪跪
fpdqwq
EntropyIncreaser强无敌。
yww
orzorzorz跪跪跪跪
newbiedmy
EntropyIncreaser强无敌。
HHzzkk
EntropyIncreaser强无敌
hehelego
EntropyIncreaser强无敌

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。