前缀和/差分

提示

本文中，若无特殊说明，$a$ 代表原数组，$b$ 代表前缀和数组，$c$ 代表差分数组，$b'$ 和 $c'$ 分别代表二阶前缀和数组和二阶差分数组。

本文中，若无特殊说明，数组下标为 $0$ 的位置值是 $0$。

注意

本文中，二阶前缀和和二阶差分并不等同于二维前缀和和二维差分。

一般情况

前缀和，顾名思义，就是前缀的和。它适用于快速区间求和，其单次询问复杂度为 $O(1)$。一个前缀和数组的定义如下：

$$b_i=\begin{cases}a_i & i=1\\b_{i-1}+a_i & i>1\end{cases}$$

要求区间 $[l,r]$ 的和，也是非常简单，计算 $b_r-b_{l-1}$ 即可。

差分，就是前缀和的逆运算。它适用于快速区间加法（减法就是加负数，当然也可以），其单次操作复杂度为 $O(1)$​。一个差分数组的定义如下：

$$c_i=\begin{cases}a_i & i=1\\a_i-a_{i-1} & i>1\end{cases}$$

给区间 $[l,r]$ 的数加上 $k$ ，只需执行 $c_l\gets c_l+k$ 和 $c_{r+1}\gets c_{r+1}-k$ 即可。

执行完所有操作后，对前缀和数组或差分数组进行逆运算，就能得到原数组。