前缀和与差分

• OI-Wiki 前缀和 & 差分

1 前缀和

前缀和是一种重要的预处理，能大大降低查询的时间复杂度。可以简单理解为“数列的前 $n$​ 项的和”。

C++ 标准库中实现了前缀和函数 std::partial_sum，定义于头文件 <numeric> 中。

* 1.1 二维/多维前缀和

* 1.2 基于 DP 计算高维前缀和

* 1.3 树上前缀和

2 差分

差分是一种和前缀和相对的策略，可以当做是求和的逆运算。

这种策略的定义是令 $b_{i}= \begin{cases}a_{i}-a_{i-1} & i \in[2, n] \\ a_{1} & i=1\end{cases}$
简单性质：

• $a_{i}$ 的值是 $b_{i}$ 的前缀和，即 $a_{n}=\sum_{i=1}^{n} b_{i}$
• 计算 $a_{i}$ 的前缀和 \operatorname{sum}=\sum_{i=1}^{n} a_{i}=\sum_{i=1}^{n} \sum_{j=1}^{i} b_{j}=\sum_{i}^{n}(n-i+1) b_{i}

它可以维护多次对序列的一个区间加上一个数，并在最后询问某一位的数或是多次询问某一位的数。注意修改操作一定要在查询操作之前。

譬如使 $[l, r]$ 中的每个数加上一个 $k$, 即

$b_{l} \leftarrow b_{l}+k, b_{r+1} \leftarrow b_{r+1}-k$

其中 $b_{l}+k=a_{l}+k-a_{l-1}, b_{r+1}-k=a_{r+1}-\left(a_{r}+k\right)$
最后做一遍前缀和就好了。

C++ 标准库中实现了差分函数 std::adjacent_difference，定义于头文件 <numeric> 中。

* 2.1 树上差分

* 2.1.1 点差分

* 2.1.2 边差分