..
0x03 前缀和与差分
前缀和
对于一个给定的数列 $A$，它的前缀和数列 $S$ 是通过递推能求出的基本信息之一：
\[S[i]=\sum_{j=1}^i{A[j]}\]一个部分和，即数列 $A$ 某个下标区间内的数的和，可表示为前缀和相减的形式：
\[sum(l,r)=\sum_{i=l}^r{A[i]=S[r]-S[l-1]}\]在二位数组（矩阵）中，可类似地求出二维前缀和，进一步求出二位部分和。
【例题】激光炸弹
差分
对于一个给定的数列 $A$，它的差分数列 $B$ 定义为：
\[B[1] = A[1], B[i] = A[i] - A[i - 1] (2 \leq i \leq n)\]容易发现，“前缀和” 与 “差分” 是一对互逆运算，差分序列 $B$ 的前缀和序列就是原序列 $A$，前缀和序列 $S$ 的差分序列也是原序列 $A$。
把序列 $A$ 的区间 $[l, r]$ 加 $d$（即把 $A_l, A_{l + 1}, \cdots, A_r$ 都加上 $d$），其差分序列 $B$ 的变化为 $B_l$ 加 $d$，$B_{r + 1}$ 减 $d$，其他位置不变。
这有助于我们在很多题目中，把原序列上的 “区间操作”转化为查分序列上的 “单点操作” 进行计算，降低求解难度。