某天无聊，就把某题的结论扩展了一小下，其实也挺 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)$ 的求法。
