前缀和与差分（一维、二维）

一、一维前缀和

前缀和是快速获得一个序列的区间和的方法，通过预处理便可以O(1)复杂度获得区间和。

设前缀和数组是sum[i],对于序列a[i]，sum[1] = a[1]; sum[2] = a[1] + a[2]; sum[3] = a[1] + a[2] + a[3];……以此类推

当需要获得[l,r]区间和时，可由sum[r] - sum[l+1] 求出。

// 预处理
for (int i = 1; i <= n; i++)
{
    cin >> a[i];
    sum[i] = sum[i - 1] + a[i];
}

// 获得区间和
ans = sum[r] - sum[l - 1];

二、一维差分

查分与前缀和互为逆运算。

差分主要用于快速对原数组区间的更改，比如我要在[l,r]区间上的每个数都加上c，用前缀和就可以快速实现。

对于一个序列a[i]，假设它的差分数组是b[i]，对b[i]数组进行前缀和运算，就会得到原数组a[i]。

因为原数组是差分数组的前缀和数组，根据前缀和获得区间和的公式 ans = sum[r] - sum[l-1] 就可以直接求得差分数组了。即差分数组b[i] = a[i] - a[i-1]。

for (int i = 1; i <= n; i++)
    b[i] = a[i] - a[i - 1];

如果要将原数组[l,r]区间的所有数加c，那么我们只需要将b[l] + c 同时 b[r + 1] - c ；

举个例子：比如我们要a[3] a[4] a[5] 这三个数都加上c，三个数的求法如下：

a[3] = b[1] + b[2] + b[3] + c；

a[4] = b[1] + b[2] + b[3] + b[4] + c;

a[5] = b[1] + b[2] + b[3] + b[4] + b[5] + c;

区间之外的，a[2] = b[1] + b[2]并没有被修改，a[6] = b[1] + b[2] + b[3] + b[4] + b[5] + b[6] + c - c 也没修改。

将序列分为三个部分，左部分不进行任何改变，中间部分需要+C，因为是通过前缀和运算得到原数组，所以我们只需要给这个区间的第一个数+C。右部分中，也应该是不能有改变的，但是因为要前缀和，也会多加一个C，所以我们对其进行“补偿”，减去C，就抵消了前面的+C，来还原这部分区间。

知道如何修改区间值了，在构造差分数组时，完全不需要用a[i]来存储原数组了，可以现将b[i]初始化为0，然后每一个读入操作等价于一个修改操作，只不过这个修改操作的区间是一个点。

三、二维前缀和

一维前缀和是一个序列的和，二维就是一个矩阵中所有数的和，比如sum[i][j] 就是原二维数组 以a[0][0] 和 a[i][j]为对角的矩阵中的所有的数的和。

该怎么获得二维前缀和呢？

从图中可以看出sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j]

要获得某区间和：

根据图，(x1,y1) (x2,y2)中间矩阵的和，可以表示为sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1]

使用二维前缀和时，通常在周围补一圈0这样可以不用检测边界。

四、二维差分

与一维差分相同，二维差分是二维前缀和逆运算，对二维差分数组b[i][j]进行二维前缀和运算，可以得到原数组a[i][j]

那么该如何构造呢?

还是根据表达式sum[x2][y2] - sum[x2][y1] - sum[x1][y2] + sum[x1][y1]，此时这里x2就是i，y2就是j，x1就是i-1，y1就是j-1可得：

b[i][j] = a[i][j] - a[i][j - 1] - a[i - 1][j] + a[i - 1][j - 1]

那么二维差分如何快速对原数组区间的更改呢？与一维差分同样的思考方式：

对(x1,y1) (x2,y2)区间+C操作：

b[x1][y1] + c, b[x2 + 1][y1] - c, b[x2 + 1][y2 + 1] + c, b[x1][y2 + 1] - c

使用二维差分时，通常在周围补一圈0这样可以不用检测边界。

了解了二维差分后，也可以像一维差分一样，省去原数组a[i][j]

五、练习题

二维前缀和:

leetcode 304 https://leetcode.cn/problems/range-sum-query-2d-immutable/description/

leetcode 1130 https://leetcode.cn/problems/largest-1-bordered-square/description/

二维差分：

洛谷 P3397 https://www.luogu.com.cn/problem/P3397