求和录（一）

本博文仍在施工中，如果作者有时间的话。

引子

生活中无处不存在着求和问题，包括离散和 $\Sigma$ 和连续和 $\int$ ，本集合文章会收录本人在学习生活中遇到的一些求和问题，并加以总结。

一阶离散和和连续和的联系

本节是作者在高中闲暇时间发现的离散序列中的类似 积分、求导、分部积分 等操作。

离散差分 <——> 导数

对于一个序列 $a_1 \ , \ a_2 \ , \ a_3 \cdots a_n$ ， 我们定义向前差分为：

$$\Delta a_i = a_{i+1} - a_i \ , \ i<n$$

同理，向后差分为：

$$\Delta a_i = a_i - a_{i-1} \ , \ i>1$$

这里我们为了统一操作，我们只考虑向前差分，并记 $\Delta^0 a_i$ 为原序列。

如果将 $\Delta a_i$ 再次求差分，我们得到：

$$\Delta^2 a_i =\Delta(\Delta a_i) = \Delta a_{i+1} - \Delta a_i= a_{i+2} - 2a_{i+1} + a_i$$

类似的我们有：

$$\begin{aligned} \Delta^3 a_i &= \Delta^2 a_{i+1} - \Delta^2 a_i = a_{i+3} - 3a_{i+2} + 3a_{i+1} - a_i \\ \Delta^4 a_i &= \Delta^3 a_{i+1} - \Delta^3 a_i = a_{i+4} - 4a_{i+3} + 6a_{i+2} - 4a_{i+1} + a_i \\ \end{aligned}$$

显然直接归纳有：

$$\Delta^n a_i = \sum_{k=0}^{n} (-1)^k \binom{n}{k} a_{i+n-k}$$

这里不用数学归纳法，简单地证明上式：

对于 $n$ 阶差分 $\Delta^n a_i = \Delta^{n-1} a_{i+1} - \Delta^{n-1} a_{i}$ ，然后继续向上延伸，考虑以下三角形：

$$\begin{aligned} &a_1 & &a_2 & &a_3 & &a_4 & &a_5 & &a_6 & &a_7 \\ & &\Delta a_1 & &\Delta a_2 & &\Delta a_3 & &\Delta a_4 & &\Delta a_5 & &\Delta a_6 & & \\ & & &\Delta^2 a_1 & &\Delta^2 a_2 & &\Delta^2 a_3 & &\Delta^2 a_4 & &\Delta^2 a_5 & & & \\ & & & &\Delta^3 a_1 & &\Delta^3 a_2 & &\Delta^3 a_3 & &\Delta^3 a_4 & & & & \\ & & & & &\Delta^4 a_1 & &\Delta^4 a_2 & &\Delta^4 a_3 & & & & & & \\ & & & & & & \Delta^5 a_1 & &\Delta^5 a_2 & & & & & & & \\ & & & & & & & \vdots & & & & & & & & \\ & & & & & & & \Delta^n a_{1} & & & & & & & & \end{aligned}$$

对于原序列上的某个元素 $a_j \ , \ j\in[i,i+n]$ 那么其在这个三角形上到 $\Delta^n a_i$ 路径，有 $\binom{n}{i+n-j}$ 条，又由于差分前的负号正负交替出现，那么其对应的系数为 $(-1)^{i+n-j} \times \binom{n}{i+n-j}$ ，那么对于该范围的j有：

$$\Delta^n a_i = \sum_{k=0}^{n} (-1)^k \binom{n}{k} a_{i+n-k}$$

注意由 $\Delta^n a_i$ 和 $a_j \ , \ j\in[i,i+n]$ 组成的三角形为边界是 $(a_j \ , \ j\in[i,i+n])$ 、 $(\Delta^p a_i \ , \ p\in[1,n])$ 、 $(\Delta^q a_{n-q+i} , q\in[0,n])$ ，其路径不能超过边界！！！

这里为了理解，我们举两个例子。

• 我们求 $\Delta^2 a_3$ 的 $a_4$ 对应的系数，首先其路径有 $\binom{2}{2+3-4} = \binom{2}{1} = 2$ 条，然后其符号为 $(-1)^{1}=-1$ ，那么系数为 $-2$ 。
• 我们求 $\Delta^3 a_1$ 的 $a_3$ 对应的系数，路径 $\binom{3}{3+1-3}=3$ 条，符号为 $(-1)^{1}=-1$ ，系数为 $-3$ 。

差分的性质

• $$\Delta(a_i±b_i) = \Delta a_i ± \Delta b_i$$
• $$\Delta(c \cdot a_i) = c \cdot \Delta a_i$$
• $$\Delta(a_i \cdot b_i) = a_{i+1} \Delta b_i + b_i \Delta a_i = b_{i+1} \Delta a_i + a_i \Delta b_i$$
• $$\Delta(\frac{a_i}{b_i}) = \frac{1}{b_{i+1}b_{i}}(b_{i+1} \Delta a_i - a_{i+1} \Delta b_i)$$

这里对差分的乘法和除法性质进行证明：

• 对于乘法：

$$\begin{aligned} \Delta(a_i \cdot b_i) &= a_{i+1}b_{i+1} - a_ib_i \\ &= a_{i+1}(b_{i+1} - b_i) + b_i(a_{i+1} - a_i) = a_{i+1} \Delta b_i + b_i \Delta a_i \\ &= b_{i+1}(a_{i+1} - a_i) + a_i(b_{i+1} - b_i) = b_{i+1} \Delta a_i + a_i \Delta b_i \\ &= \frac{a_{i+1}+a{i}}{2} \Delta b_i + \frac{b_{i+1}+b_i}{2} \Delta a_i \\ \end{aligned}$$

• 对于除法：

$$\begin{aligned} \Delta(\frac{a_i}{b_i}) &= \frac{a_{i+1}}{b_{i+1}} - \frac{a_i}{b_i} = \frac{a_{i+1}b_i - a_ib_{i+1}}{b_{i+1}b_i}\\ &= \frac{(b_{i+1}a_{i+1}-b_{i+1}a_i)-(a_{i+1}b_{i+1}-a_{i+1}b_i)}{b_{i+1}b_i{i}} \\ &= \frac{b_{i+1} \Delta a_i - a_{i+1} \Delta b_i}{b_{i+1}b_i} \\ \end{aligned}$$

差分和导数

以上公式可以看出差分和导数是十分相似：导数告诉我们函数在某一个点的变化趋势，而差分告诉我们一个序列在某个关系位置的变化量。如果序列 $a_i$ 来自某个函数 $f(x)$ 的整数映射 $a_i=f(i)$ ，那么差分：

$$\Delta a_i = f(i+1) - f(i) \approx f'(i)$$

可以看作 $f’(i)$ 的离散近似值。进一步的高阶差分，也对应着高阶导数的离散类比，这也是数值计算中常用的有限差分方法的基础。

不过要注意的是，在大多数情况下，我们处理的序列只是一个数组，各项之间未必有函数关系。这时差分仅仅是一种代数操作，不能直接等同于导数。只有在我们认为序列来源于某个底层函数，或者希望用差分来近似导数时，这种对应才有意义。

因此，差分既可以看作是一种离散世界里独立的运算工具，又可以看作是连续世界导数的影子。它正好搭起了一座桥梁，把离散数学、算法设计和微积分联系了起来。

离散求和 <——> 积分

我们定义 $S_i=\sum_{j=1}^{i} a_j$ 为 $a_i$ 的前缀和， 其的差分为 $\Delta S_i = S_{i+1} - S_i = a_{i+1}$ ，同样地区间求和可以表示为 $S_{l,r}=\sum_{i=l}^{r} a_i = S_r - S_{l-1}$ 。

差分和求和

对于一阶的差分 $\Delta a_i = a_{i+1}-a_i$ 我们对其左右两边从1到n同时求和，得到：

$$\begin{aligned} \sum_{i=1}^{n} \Delta a_i &= \sum_{i=1}^{n} (a_{i+1}-a_i) \\ &= a_2 - a_1 + a_3 - a_2 + \cdots a_{n+1} - a_n\\ &= a_{n+1} - a_1 \end{aligned}$$

同理对于高阶差分 $\Delta^p a_i = \Delta^{p-1} a_{i+1} - \Delta^{p-1} a_i$ ，我们对其左右两边从1到i-1同时求和，得到：

$$\Delta^{p-1} a_{i} =\Delta^{p-1} a_{1} + \sum_{j=1}^{i-1} \Delta^p a_j$$

那么我们如果直到某个序列的p阶差分，以及以上p-1（含0）阶所有的首项，那么我们可以求出该序列的 $a_n$ 。

我们知道

$$\Delta^{p-1} a_{k} =\Delta^{p-1} a_{1} + \sum_{t=1}^{k-1} \Delta^p a_t$$

继续对上式左右两边同时求和，得到：

$$\begin{aligned} \sum_{k=1}^{j-1} \Delta^{p-1} a_{k} &= \Delta^{p-2} a_j - \Delta^{p-2} a_1 \\ &= \sum_{k=1}^{j-1} (\Delta^{p-1} a_{1} + \sum_{t=1}^{k-1} \Delta^p a_t) \\ &= (j-1)\Delta^{p-1} a_{1} + \sum_{k=1}^{j-1} \sum_{t=1}^{k-1} \Delta^p a_t \\ \end{aligned}$$

即， $\Delta^{p-2} a_j = \Delta^{p-2} a_1 + (j-1)\Delta^{p-1} a_{1} + \sum_{k=1}^{j-1} \sum_{t=1}^{k-1} \Delta^p a_t$

继续对上式左右两边同时求和，得到：

$$\begin{aligned} \sum_{j=1}^{i-1} \Delta^{p-2} a_{j} &= \Delta^{p-3} a_i - \Delta^{p-3} a_1 \\ &= \sum_{j=1}^{i-1} (\Delta^{p-2} a_1 + (j-1)\Delta^{p-1} a_{1} + \sum_{k=1}^{j-1} \sum_{t=1}^{k-1} \Delta^p a_t) \\ &=(i-1)\Delta^{p-2} a_1 + \sum_{j=1}^{i-1} (j-1)\Delta^{p-1} a_{1} + \sum_{j=1}^{i-1} \sum_{k=1}^{j-1} \sum_{t=1}^{k-1} \Delta^p a_t \\ &=(i-1)\Delta^{p-2} a_1 + \binom{i-1}{2}\Delta^{p-1} a_{1} + \sum_{t=1}^{i-3} \binom{i-1-t}{2} \Delta^p a_t \\ \end{aligned}$$

那么我们不难归纳，对于任意整数 $r\ , \ r\in[1,p]$有：

$$\begin{aligned} \Delta^{p-r} a_i &= \sum_{j=0}^{r-1} \binom{n-1}{j} \Delta^{p-r+j} a_1 + \sum_{i_1=r}^{n-1}\sum_{i_2=r-1}^{i_1-1} \cdots \sum_{i_r=1}^{i_{r-1}-1} \Delta^p a_{i_r} \\ &=\sum_{j=0}^{r-1} \binom{n-1}{j} \Delta^{p-r+j} a_1 + \sum_{i=1}^{n-r}\binom{n-1-i}{r-1} \Delta^p a_i \\ \end{aligned}$$

这里说明下为什么 $\sum_{i_1=r}^{n-1}\sum_{i_2=r-1}^{i_1-1} \cdots \sum_{i_r=1}^{i_{r-1}-1} \Delta^p a_{i_r} = \sum_{i=1}^{n-r}\binom{n-1-i}{r-1} \Delta^p a_i$

我们由于这个式子求出来必定是在 $\Delta^p a_i$ 前带了个系数，我们不妨直接考虑以上求和串对于各项的贡献。由于最内层的求和 $\sum_{i_r=1}^{i_{r-1}-1}$ 实际上是将差分枚举，各项的系数仍然是1，直接考虑外层对系数的贡献。我们尝试固定 $i_r=1$ 观察 $\Delta^p a_1$ 的系数，从1开始计数，有：

$$\begin{aligned} \sum_{i_1=r}^{n-1}\sum_{i_2=r-1}^{i_1-1}\cdots \sum_{i_{r-1=2}}^{i_{r-2}-1} 1 &= \sum_{i_1=r}^{n-1}\sum_{i_2=r-1}^{i_1-1}\cdots \sum_{i_{r-2=3}}^{i_{r-3}-1} (i_{r-2}-2) \\ &= \sum_{i_1=r}^{n-1} \cdots \sum_{i_{r-3=4}}^{i_{r-4}-1} \frac{(i_{r-3}-2)(i_{r-3}-3)}{2} \\ &= \sum_{i_1=r}^{n-1} \cdots \sum_{i_{r-3=4}}^{i_{r-4}-1} \binom{i_{r-3}-2}{2} \\ &= \sum_{i_1=r}^{n-1} \cdots \sum_{i_{r-4=5}}^{i_{r-5}-1} \binom{i_{r-4}-2}{3} \ \ \ \ ,\ because \sum_{i=1}^{n-1}\binom{i}{m} = \binom{n}{m+1} \\ &\vdots \\ &=\binom{n-2}{r-1} \\ \end{aligned}$$

显然地，对于第i个元素 $\Delta^p a_i$ 有：

$$\begin{aligned} \sum_{i_1=r}^{n-1}\sum_{i_2=r-1}^{i_1-1}\cdots \sum_{i_{r-1=1+i}}^{i_{r-2}-1} 1 &= \sum_{i_1=r}^{n-1}\sum_{i_2=r-1}^{i_1-1}\cdots \sum_{i_{r-2=2+i}}^{i_{r-3}-1} \binom{i_{r-2}-1-i}{1} \\ &= \sum_{i_1=r}^{n-1} \cdots \sum_{i_{r-3=3+i}}^{i_{r-4}-1} \binom{i_{r-3}-1-i}{2} \\ &\vdots \\ &=\binom{n-1-i}{r-1} \\ \end{aligned}$$

于是对于$1+r\le i+r \le n \to 1\le i \le n-r$累加有： $\sum_{i=1}^{n-r}\binom{n-1-i}{r-1} \Delta^p a_i$

当 $r=p$ 时，有：

$$a_n = \Delta^0 a_n = \sum_{j=0}^{p-1} \binom{n-1}{j} \Delta^{j} a_1 + \sum_{i=1}^{n-1}\binom{n-1-i}{p-1} \Delta^p a_i$$

如果该序列有无穷阶的差分那么有：

$$a_n = \lim_{p\to \infty} ( \ \sum_{j=0}^{p-1} \binom{n-1}{j} \Delta^{j} a_1 + \sum_{i=1}^{n-1}\binom{n-1-i}{p-1} \Delta^p a_i \ ) = \sum_{j=1}^{\infty} \binom{n}{j} \Delta^{j} a_1$$

我们以0作为下标，那么有：

$$a_n = \sum_{j=0}^{\infty} \binom{n}{j} \Delta^{j} a_0 = a_0 + \sum_{j=1}^{\infty} \binom{n}{j} \Delta^{j} a_0$$

考虑该式子张开到第 $m$ 项 那么其含有余项的形式为：

$$a_n = a_0 + \sum_{j=1}^{m} \binom{n}{j} \Delta^{j} a_0 + \sum_{j=m+1}^{\infty} \binom{n}{j} \Delta^{j} a_0$$

一些有趣的例子

abc423_e

题目大意是有一个长度为N的数组A：$A1, A_2 \cdots A_n$ 以及Q个查询，每个查询给出L和R，求： $$\sum{l=L}^{R} \sum{r=l}^{R} \sum{j=l}^{r} A_j$$

• Constraints
  • $1 \leq N, Q \leq 3 \times 10^5$
  • $1 \leq A_i \leq 100$
  • $1 \leq L_i \leq R_i \leq N$
  • All input values are integers.

思路

显然地，有如此巨大数据的查询肯定是需要预处理，接下来我们考虑如何预处理。

我们先尝试着变形这个式子 $\sum_{r=l}^{R} \sum_{j=l}^{r} A_j$ ：

$$\begin{aligned} &\sum_{r=l}^{R} \sum_{j=l}^{r} A_j \\ =& \sum_{r=l}^R (A_l+ A_{l+1} + \cdots + A_r) \\ =& A_l + (A_l + A_{l+1}) + \cdots + (A_l + A_{l+1} + \cdots + A_R) \\ =& (R-l+1)A_l + (R-l)A_{l+1} + \cdots + A_R \\ =& \sum_{i=1}^{R-l+1} iA_{R-i+1} \end{aligned}$$

那么前面加上 $\sum_{l=L}^{R}$ 有：

$$\begin{aligned} & \sum_{l=L}^{R} \sum_{r=l}^{R} \sum_{j=l}^{r} A_j \\ =& \sum_{l=L}^{R} \sum_{i=1}^{R-l+1} iA_{R-i+1} \\ =& \sum_{i=1}^{R-L+1} iA_{R-i+1} + \sum_{i=1}^{R-L} iA_{R-i+1} + \cdots + \sum_{i=1}^{2} iA_{R-i+1} + \sum_{i=1}^{1} iA_{R-i+1} \\ =& A_R + (A_R + 2A_{R-1}) + \cdots \\ +& (\ A_R +2A_{R-1} + \cdots + (R-L-1)A_{L+2}+(R-L)A_{L+1}\ )\\ +& (\ A_R +2A_{R-1} + \cdots + (R-L)A_{L+1} +(R-L+1)A_{L} \ ) \\ =& \sum_{i=L}^{R} (i-L+1)(R-i+1)A_i \\ =& \sum_{i=L}^R (-i^2 +i(R+L) -(R+1)(L-1)\ ) A_i \\ =& (R+L)\sum_{i=L}^R iA_i - \sum_{i=L}^R i^2 A_i - (R+1)(L-1)\sum_{i=L}^R A_i \end{aligned}$$

那么我们只需要将 A[i] i*A[i] i*i*A[i] 预处理出来，在加上系数计算即可。