前缀和

前缀和数组 $S_i = \sum_{k=1}^{i} a_k$，任意区间和 $[l, r]$ 等于 $S_r - S_{l-1}$。

差分

差分是前缀和的逆运算：对区间 $[l, r]$ 加 $v$，只需 $d_l \mathrel{+}= v$，$d_{r+1} \mathrel{-}= v$。