前缀和 & 差分

参考资料

• 前缀和 & 差分 - 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$ 个区间的区间和。