前缀和与差分

前缀和

定义

对于一个给定的数列 $A$，可以计算得到它对应的前缀和数列 $S$，其中 $S$ 的第 $i$ 项是数列 $A$ 的前 $i$ 项之和。

即

$$S[i] = \sum_{j = 1}^i A[j]$$

理解

前缀和可以简单理解为「数列的前 $n$ 项的和」，是一种重要的预处理方式。
根据定义，前缀和数列可以通过递推的方式计算得到：

$$S[i] = \sum_{j = 1}^i A[j] = \left \{ \begin{array}{ll} A[i], \ i = 1 \\ S[i-1] + A[i], \ i > 1 \end{array} \right.$$

因此，可以在线性时间内得到前缀和数列。

具体应用

基于前缀和数列 $S$，可以通过一次减法代替累加操作，得到原数列 $A$ 的区间和（下标 $l$ 到 $r$ 的元素和），能够大大降低查询的时间复杂度。
即

$$sum(l,r) = \sum_{i = l}^r A[i] = S[r] - S[l-1]$$

拓展应用

二维前缀和

对于一个给定的二维数组 $A$，可以计算得到它对应的二维前缀和 $S$，其中 $S[i][j]$ 是 $A$ 的前 $i$ 行前 $j$ 列之和。

即

$$S[i][j] = \sum_{x = 1}^i \sum_{y = 1}^j A[x][y]$$

与一维前缀和类似，二维前缀和涉及到两个关键问题：如何计算 和 如何应用。

1. 如何计算？

二维前缀和可以基于容斥原理进行递推得到：

$$S[i][j] = \sum_{x = 1}^i \sum_{y = 1}^j A[x][y] = \left \{ \begin{array}{llll} A[i][j], \ i = 1 \And j = 1 \\ S[i][j-1] + A[i][j], \ i = 1 \And j > 1 \\ S[i-1][j] + A[i][j], \ i > 1 \And j = 1 \\ S[i-1][j] + S[i][j-1] - S[i-1][j-1] + A[i][j], \ i > 1 \And j > 1 \end{array} \right.$$

2. 如何应用？

基于二维前缀和 $S$ 和容斥原理，可以通过三次加（减）法代替累加操作，得到原二维数组 $A$ 的区域和（以$(x_1, y_1)$为左上顶点，以$(x_2, y_2)$为右下顶点的子矩阵中的元素和），能够大大降低查询的时间复杂度。

即

$$sum(x_1, y_1, x_2, y_2) = \sum_{x = x_1}^{x_2} \sum_{y = y_1}^{y_2} A[x][y] = S[x_2][y_2] - S[x_1-1][y_2] - S[x_2][y_1-1] + S[x_1-1][y_1-1]$$

差分

定义

对于一个给定的数列 $A$，可以计算得到它对应的差分数列 $D$，其中 $D$ 的第 $1$ 项是数列 $A$ 的第 $1$ 项，$D$ 的第 $i$ 项（$i > 1$）是数列 $A$ 的第 $i$ 项与第 $i - 1$ 项之差。

即

$$D[i] = \left \{ \begin{array}{ll} A[i], \ i = 1 \\ A[i] - A[i-1], \ i > 1 \end{array} \right.$$

理解

差分也是一种重要的预处理方式，与前缀和是一对互逆运算，两者之间存在如下的转换关系：

1. 差分数列的前缀和数列是原数列，即

   $$A[i] = \sum_{j = 1}^i D[j]$$

2. 前缀和数列的差分数列是原数列，即

   $$A[i] = \left \{ \begin{array}{ll} S[i], \ i = 1 \\ S[i] - S[i-1], \ i > 1 \end{array} \right.$$

具体应用

基于差分数列 $D$，可以将原数列上的“区间加操作”转化为差分数列上的“单点操作”，能够大大降低操作的时间复杂度。

将原数列 $A$ 中下标处于 $[l,r]$ 范围内的元素都加上 $num$，这一“区间加操作”在差分数列 $D$ 上对应的变化是“单点操作”，即 $D_l$ 加 $num$，$D_{r+1}$ 减 $num$，其他位置不变。因此，可以通过差分数列上的“单点操作”代替原数列上的“区间加操作”。如果要获得经过多次“区间加操作”后的原数列，只需要对经过多次“单点操作”后的差分数列计算一次前缀和数列即可。