K阶前缀和

这是我们对前缀和的定义。而 阶前缀和就是把这个过程进行 次。那么考虑卷积。 其实可以看作 而 。 是一个所有项都为 的函数。那么 。由于卷积是有结合率的，所有 阶前缀和等同于 。而对于 的计算，可以采用多项式快速幂，但没必要。我们有生成函数 ，那么 的生成函数为 而 。这个可以通过数学归纳法证明。最后就做一次卷积就可以了。

K阶差分

那么 也可以卷积 其中 。那么 的生成函数为 。 那么进行 次操作之后 的生成函数为 那么 。卷积一下就做完了。

分析

不管是差分还是前缀和其实我们都可以 就可以了，更加无脑一点，时间复杂度也是 。