前缀和

一维前缀和

假设我们有一个数组$A$：
$A_1, A_2, …, A_n$
那么我们可以定义一个前缀和数组$S$：
$S_i=A_1+A_2+…+A_i$
注意：$S_0=0$
这就完了。
前缀和不是一个模版，而是一个公式。

还有两个问题：

1. 如何求$S_i$:

递推for(int i = 1; i <= n; i++) S[i] = S[i-1] + A[i];

2. 作用：

求原数组中一段数的和
如果没有前缀和数组，就只能一位一位的加，从$A_l$加到$A_r$，时间复杂度是O(n)，非常慢。
但用前缀和数组S，答案就是$S_r-S_{l-1}$。
因为$S_r = A_1+A_2+…+A_r$
$S_{l-1} = A_1+A_2+…+A_{l-1}$
它们相减，把$S_r$中$A_1$~$A_{l-1}$的部分消掉了，还剩$A_l+…+A_r$，多么简单，时间复杂度O(1)，多么迅速。

二维前缀和

它是求矩阵中一段子矩阵的和
$S_{i,j}$就是他左上角的全部都加起来
假设要求的子矩阵，左上角坐标是$(x_1, y_1)$，右下角坐标是$(x_2, y_2)$。
那么他就等于$S_{x_2,y_2} - S_{x_2,y_1-1} - S_{x_1-1,y_2} + S_{x_1-1,y_1-1}$（怎么推出来的不管）

怎么求$S_{i,j}$

递推：

for (int i = 1; i <= n; i++){
    for (int j = 1; j <= m' j++){
        S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + A[i][j];
    }
}

前缀和至此就弄完了（竟然这么简单）

差分

差分和前缀和是逆运算。

一维差分

还是假设我们有一个数组$A$
构造一个数组$B$
使得$A$是$B$的前缀和数组
这时$B$就是$A$的差分数组

作用：

如果要把原数组$[l, r]$区间内的所有数都加上$d$，假设有q次，挨个加最后是O(nq)的时间复杂度，很慢。
这时，我们可以把$b_l+d$，把$b_{r+1}-d$最后再根据b数组推出原数组，O(n + q)的时间复杂度，真快。

构造方式很简单

把差分数组都初始成0
可以看成给$[i, i]$范围内都加上$A_i$

二位差分

构造方式

根本不用构造。

假设要操作的子矩阵，左上角坐标是$(x1,y1)$，右下角坐标是$(x2,y2)$。
那么可以转换为$b_{x_1,y_1}+=c, b_{x_2+1,y_1}-=c, b_{x_1,y_2+1}-=c, b_{x_2+1,y_2+1}+=c$（怎么推出来的也不管）
----------------------------------------end(最短的一篇了吧)----------------------------------------