差分与前缀和的简单记录

WeLikeStudying · 2022-07-20 07:52:44 · 题解

• 感谢奆佬，奆佬，奆佬的提醒，祝愿其信息学之路光芒璀璨。
• 有同志觉得这样做并没有必要，不过我其实只是想增加对差分与前缀和的了解而已，愚蠢的事情，我早已做过很多，不必怕多这一。

qwq 1

• 树状数组维护单点修改，求 k 阶前缀和。
• 设 f(n) 的 k 阶前缀和为 \sigma^kf(n)。 \sigma^kf(n)=\sum_{i=0}C(k+i-1,k-1)f(n-i)
• 容易根据组合意义（或推式子）归纳证明，你会发现 C(k+i-1,k-1) 是一个关于 i 的 k 次多项式，直接代入换成 C(k-(n-i)+n-1,k-1)，然后你发现它也是一个关于 n-i 的多项式，且对于单独的 n，各项系数固定，且我们可以一开始 O(nk^2) 预处理各项系数。
• 那么现在我们的任务只剩下分别维护 n^if(n) 的前缀和了对吧，强行树状数组分别维护即可，总的复杂度应该是 O(nk^2+qk\log n)，代码实现。不如根号。

qwq 2

• 维护单点修改，求 k 阶差分。
• 设 f(n) 的 k 阶差分为 \delta^kf(n)。 \delta^kf(n)=\sum_{i=0}C(k,i)(-1)^{k-i}f(n+i)
• 这玩意你要树状数组？直接暴力更新复杂度就有 O(nk+qk)，直接略去。

qwq 3

• 用多项式似乎可以快速求出一个数组的 k 阶差分或前缀和（在 k 很大时），原因已经被你看到了。

水题

• 不知道怎么变黑的，做完了就把它降紫。
• 假设我们区间加直接对数组 f 进行维护，那么我们相当于查询： \sum_{i=l}^r\sum_{j=1}^{n-i+1}\sum_{k=j}^{j+i-1}f(k)
• 利用这题的做法，我们可以将问题化为： \sum_{i=l}^r\sum_{j=1}^{n-i+1}\sigma f(j+i-1)-\sigma f(j-1) \sum_{i=l}^r\sigma^2 f(n)-\sigma^2 f(i-1)-\sigma^2 f(n-i) (r-l+1)\sigma^2 f(n)-\sigma^3 f(r-1)+\sigma^3 f(l-2)-\sigma^3 f(n-l)+\sigma^3f(n-r-1)
• 强行设差分数组 g(n)=f(n)-f(n-1)，我们要求的： (r-l+1)\sigma^3 g(n)-\sigma^4 g(r-1)+\sigma^4 g(l-2)-\sigma^4 g(n-l)+\sigma^4g(n-r-1)
• 因此我们的问题即为单点修改，查询单点的四次前缀和还是不如根号，代码实现。