前缀和与差分

前缀和的本质理解

向量法

我们都知道 $\vec{AB}=\vec{OB}-\vec{OA}$，那么把它放在数轴上，类比可知：

如果 $pre[i]=\sum _{i=1}^n a[i]$，则：

$\sum_{i=l}^ra[i]=pre[r]-pre[l-1]$

积分法

如果 $F'(x)=f(x)$，则 $\int_{a}^b f(x)=F(b)-F(a)$，也是同一个道理。

如何判断两数列相等

如果 $F=G,F'(x)=f(x),G'(x)=g(x)$，则 $f=g$，类比可知：

如果 $pre[i]=pre'[i]$，则 $a[i]=a'[i]$。

前缀和的好处

区间求值

可以 $O(1)$ 求出 $\sum_{i=l}^r a[i]$。

降低维度

对于 $\sum_{i=l}^r a[i]$，其有两个维度 $l,r$，数量级是 $n^2$，而化为 $pre[r],pre[l-1]$ 处理，维度减少了一，数量级是 $n$。

知道 $\sum_{i=l}^r a[i]$，就能得出 $pre[r],pre[l-1]$ 之间的关系。

前缀和的数学计算（可跳过）

类比积分，我们需要引入有限微积分和无限微积分的概念。

无限微积分（微分算子 D）

$\mathrm{D} f(x)=\lim_{h\to 0} \frac{f(x+h)-f(x)}{h}$

有限微积分（差分算子 $\Delta$）

$\Delta f(x)=\frac{f(x+1)-f(x)}{1}=f(x+1)-f(x)$

两者对比

众所周知：

$\mathrm{D} x^m=mx^{m-1}$

而对于有限微积分，有没有类似的结论？

事实上，引入 $x^{\underline{m}}$，称为下降阶乘幂，其定义是：

$x^{\underline{m}}=x(x-1)\cdots(x-m+1)$

则，$\Delta(x^{\underline{m}})=x(x-1)\cdots(x-m+1)-(x-1)\cdots(x-m)=mx^{\underline{m-1}}$，结论与上面类似。

运用到积分

设 $\sum_a^b g(x)\delta x=f(b)-f(a)$，其中 $\Delta f(x)=g(x)$，则由定义我们推出 $\sum_{a}^b g(x)\delta x= \sum_{a\le x <b} g(x)$。

注：这里的 $\delta$ 是 $\Delta$ 的小写，类比 $\mathrm{d}$ 是 $\mathrm{D}$ 的小写。

可以试着代入 $g(x)=x^{\underline{m}}$，则 $f(x)=\frac{x^{\underline{m+1}}}{m+1}$，则：

$\sum_{0 \le k <n}k^{\underline{m}}=f(n)-f(0)=\frac{n^{\underline{m+1}}}{m+1}$

于是我们可以试着用待定系数法（或者多项式除法）来求解 $\sum_{0\le k <n} k^a$，其中 $a$ 是正整数。

函数乘积的差分

已知 $\Delta u(x),\Delta v(x),u(x),v(x)$，求 $\Delta(u(x)v(x))$。

由定义，我们有：

$\begin{aligned} \Delta (u(x)v(x))&=u(x+1)v(x+1)-u(x)v(x)\\ &=(\Delta u(x)+u(x))(\Delta v(x)+v(x))-u(x)v(x)\\ &=u(x)\Delta v(x)+v(x)\Delta u(x) + \Delta u(x)\Delta v(x) \end{aligned}$

或者写成不对称的形式：

$u(x)\Delta v(x)+v(x+1)\Delta u(x)$

分部积分

回顾无限微积分下分部积分的法则：

$\int u\mathrm{d}v=uv-\int v\mathrm{d}u$

我们令 $\mathrm{E}$ 为移位算子，具体地，$\mathrm{E} v(x)=v(x+1)$，则有类似的法则：

$\sum u\Delta v=uv-\sum \mathrm{E}v\Delta u$

如果我们想要求 $\sum k2^k$，则：

$\begin{aligned} &\sum x2^x\delta x \quad (u=x,\Delta v=2^{x} \Rightarrow \Delta u=1,v=2^x)\\ =&x2^x-\sum \mathrm{E} 2^{x} \delta x=x2^x-2^{x+1}+C \end{aligned}$

则 $\sum_{k=0}^n k2^k=\sum_{0}^{n+1} x2^x \delta x=x2^x-2^{x+1}|_0^{n+1}=(n-1)2^{n+1}+2$。

其他方法

拉格朗日法

由上面的积分法，虽然不能精确地得出一些前缀和式的通项，但是可以由归纳法知道式子的次数是有限的。

这样我们就可以取点 $1,2,\cdots,n$，进行插值。

生成函数法

如果我们要求数列 $\{a_n\}$ 的前缀和，可以构造生成函数：

$F(x)=\sum_{i=1}^n a_i x^i$

与

$G(x)=1+x+x^2+\cdots=\frac{1}{1-x}$

相乘。如果要求 $k$ 维前缀和，则计算 $F(x)\times (\frac{1}{1-x})^k$，求 $\ln,\exp$ 即可。

如果求差分，也是类似的道理。

本质上是 $\{a_n\}$ 与 $\{1,1,\cdots\}$ 的卷积。

不同维度上的前缀和、差分

通常我们需要结合容斥原理计算。

二维前缀和

设数组 $a[n][m]$，记 $s[x][y]=\sum_{i=1}^x\sum_{j=1}^y a[i][j]$，递推求 $s[x][y]$：

$s[x][y]=s[x-1][y]+s[x][y-1]-s[x-1][y-1]+a[x][y]$

求 $(x_1,y_1),(x_2,y_2)$ 所构成的矩形的数之和：

$sum=s[x_2][y_2]-s[x_1-1][y_2]-s[x_2][y_1-1]+s[x_1-1][y_1-1]$

高维前缀和

https://gaisaiyuno.github.io/archives/cb88f9ef.html

树上差分

点差分

$d_u \to d_u +1 \quad d_v \to d_v +1\\ d_{lca} \to d_{lca} -1 \quad d_{fa(lca)}\to d_{fa(lca)}-1$

可以将每一次操作理解为从当前节点到根节点都进行了同样的改变，点差分的意义就不难理解。

边差分

$d_u \to d_u +1 \quad d_v \to d_v +1 \\ d_{lca} \to d_{lca}-2$

狄利克雷前缀和

已知 $\{a\}$ 求：

$b_k=\sum_{i|k} a_i$

首先，我们向狄利克雷卷积的定义寻求帮助：

$(f*g)(n)=\sum_{xy=n} f(x)g(y)$

令 $f(i)=a_i,g(i)=1$，即 $g=one$。莫比乌斯反演即可。

或者，我们可以从高维前缀和的角度理解，分析标准素因数分解式，这里 po 一篇洛谷的题解：

1
2
3

for(Rint i = 1;i <= tot;i ++)
	for(Rint j = 1;pri[i] * j <= n;j ++)
		a[pri[i] * j] += a[j];

前缀和处理的元素

具有加、减的性质，具体来说，具有 $\circ_{+},\circ_{-}$ 两种运算，满足 $(a \circ _{+}b)\circ_{-} b=a$。

比如说 $a\circ_{+} b= (a+b) \pmod m,a \circ_{-} b= (a-b) \pmod m$，又如 $\circ_{+}=\circ_{-}=\oplus$。

前缀和的应用

CF 796F

咕咕咕

P5994

咕咕咕