前缀和与差分

1 前缀和

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

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

* 1.1 二维/多维前缀和

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

* 1.3 树上前缀和

2 差分

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

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

  • aia_{i} 的值是 bib_{i} 的前缀和,即 an=i=1nbia_{n}=\sum_{i=1}^{n} b_{i}
  • 计算 aia_{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][l, r] 中的每个数加上一个 kk, 即

blbl+k,br+1br+1kb_{l} \leftarrow b_{l}+k, b_{r+1} \leftarrow b_{r+1}-k

其中 bl+k=al+kal1,br+1k=ar+1(ar+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 边差分