前缀和 & 差分

Summary

前缀和（Prefix Sum）预处理数列前若干项之和，把区间求和的查询降到常数时间：记前 k 项之和为 Sk，则从 a 到 b 的区间和等于 Sb 减去 S(a-1)。差分（Difference）是与前缀和互逆的策略，可看作求和的逆运算，由相邻两项之差 Ak=Sk-S(k-1) 还原出原数列，常用于对某段区间整体加减的批量修改。文末给出 std 的 partial_sum 与 adjacent_difference 两个对应的 STL 函数。

参考资料

• 前缀和 & 差分 - OI Wiki

前缀和

前缀和（Prefix Sum）可以简单理解为「数列的前 $n$ 项的和」，是一种重要的预处理方式，能大大降低查询的时间复杂度。

$$S_k=\sum_{i=1}^k A_i=A_1+A_2+\dots+A_k$$ $$\sum_{i=a}^b A_i=S_b-S_{a-1}$$

差分

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

$$A_k=S_k-S_{k-1}$$

STL

• std::partial_sum
• std::adjacent_difference

例题

洛谷 P8218 【深进1.例1】求区间和

给定由 $n$ 个正整数组成的序列 $a_1, a_2,\dots, a_n$ 和 $m$ 个区间 $[l_i,r_i]$，分别求这 $m$ 个区间的区间和。