前缀和
- 概念：前缀和是指是一个数组的某项下标 i 之前(包括此项元素)的所有数组元素的和，前缀和问题一般分为一维前缀和与二维前缀和
- 一维前缀和：是指求解序列的前 i 项和，可以把它理解为数学上的数列的前 i 项和
- 二维前缀和：是指求解矩阵中以(x1, x2)为左上角，以(x2, y2)为右下角的子矩阵元素和，可以形象的理解为求子矩阵的面积
- 前缀和优点：合理使用前缀和可以将一些复杂的操作简单化，从而提高算法的效率
一维前缀和
首先考虑一个基础例子：
给定一个长度为 n 的序列，我们有 m 个询问，对于每一个询问，我们需要求给定的区间 [l, r] 的元素和。
基础思路：
对于一个区间，我们很容易想到可以通过暴力解法，遍历区间累加求和，代码如下：
int n, m, l, r, sum;
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
while(m--) {
sum = 0;
scanf("%d%d", &l, &r);
for(int i = l; i <= r; i++) {
sum += a[i];
}
printf("%d\n", sum);
}存在的问题：
暴力解法的时间复杂度为 O(nm) ，显然对于 n 和 m 较大一点的数据点，暴力解法很容易超时，而如果我们使用前缀和的方法求解，则可以把时间复杂度降至 O(n+m)，大大提高了算法的效率。
一维前缀和做法：
首先我们需要对原数组 a 做一个预处理，定义数组 s[ ] ，s[i] 表述数组 a 的前 i 项和，根据数学推算可以得到如下规律：
s[ 1 ] = a[ 1 ]
s[ 2 ] = a[ 1 ] + a[ 2 ] = s[ 1 ] + a[ 2 ]
s[ 3 ] = a[ 1 ] + a[ 2 ] + a[ 3 ] = s[ 2 ] + a[ 3 ]
……
s[ n ] = a[ 1 ] + a[ 2 ] + a[ 3 ] + …… + a[ n ] = s[ n-1 ] + a[ n ]
对于数组 s ，我们可以得到递推公式 s[i] = s[i-1] + a[i] ，因此可以得到如下预处理代码：
const int maxn = 1e5+10;
int a[maxn], s[maxn]; //s[i]=a[1]+a[2]+a[3].....a[i];
for(int i = 1; i <= n; i++) {
s[i] = s[i-1] + a[i];
}回到我们的例子，根据数学推算可发现，对于每次查询，我们只需执行s[r]-s[l-1] 
由此我们可以写出以下查询代码：
scanf("%d%d", &l, &r);
printf("%d\n", s[r]-s[l-1]);对于每次查询，时间复杂度为O(1)，m 次查询的时间复杂度为O(m)，预处理的时间复杂度为O(n)，所以总时间复杂度为O(n+m)。
二维前缀和
如果数组变成了二维该怎么办？
一维前缀和可以拓展到二维，先看一个例子：对于一个 n 行 m 列的矩阵，我们有 q 个询问，每个询问包含四个整数x1, y1, x2, y2，表示一个子矩阵的左上角坐标和右下角坐标，对于每个询问，我们需要输出子矩阵中所有数的和。
基础思路：
同样我们也可以快速思考出暴力解法，直接遍历矩阵中的所有元素进行求和，代码如下：
int n, m, q, x1, y1, x2, y2, sum, a[maxn][maxm];
scanf("%d%d%d", &n, &m, &q);
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
scanf("%d", &a[i][j]);
}
}
while(q--) {
sum = 0;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
for(int i = x1; i <= x2; i++) {
for(int j = y1; j <= y2; j++) {
sum += a[i][j];
}
}
printf("%d\n", sum);
}存在的问题：
暴力解法的时间复杂度为 O(nmq) ，显然对于 n 、 m 、q 较大一点的数据点，暴力解法很容易超时，而如果我们使用前缀和的方法求解，则可以把时间复杂度降至 O(nm + q)，提高了算法的效率。
二维前缀和做法：
同一维前缀和一样，我们需要对原数组 a 做一个预处理，定义数组 s[ ][ ] ，s[i][j] 表述二维数组 a 中， 左上角(1,1)到右下角( i,j )所包围的矩阵元素的和，接下来推导二维前缀和的预处理递推公式：
根据图例可知， 紫色面积是指(1,1)左上角到(i,j-1)右下角的矩形面积，绿色面积是指(1,1)左上角到(i-1, j )右下角的矩形面积，红色面积是指(1,1)左上角到(i-1, j-1 )右下角的矩形面积，每一个颜色的矩形面积都代表了它所包围元素的和 。 从图中我们很容易看出，整个外围蓝色矩形面积s[i][j] = 绿色面积s[i-1][j] + 紫色面积s[i][j-1] - 重复加的红色的面积s[i-1][j-1]+小方块的面积a[i][j]。
因此我们得到二维前缀和的预处理递推公式为s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j]，实现代码如下：
const int maxn = 1e5+10;
const int maxm = 1e5+10;
int a[maxn][maxm], s[maxn][maxm]; //s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[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];
}
}回到我们的问题： 求以(x1,y1)为左上角和以(x2,y2)为右下角的矩阵的元素的和 。
紫色面积是指 ( 1,1 )左上角到(x1-1,y2)右下角的矩形面积 ，黄色面积是指(1,1)左上角到(x2,y1-1)右下角的矩形面积，红色面积是指(1,1)左上角到(x1-1,y1-1)右下角的矩形面积。不难推出， 绿色矩形的面积 = 整个外围面积s[x2, y2] - 黄色面积s[x2, y1 - 1] - 紫色面积s[x1 - 1, y2] + 重复减去的红色面积 s[x1 - 1, y1 - 1] 。
根据图例我们可以写出二维前缀和的查询公式， 以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为： s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1] 。由此我们可以写出以下查询代码：
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
printf("%d\n", s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1]);对于每次查询，时间复杂度为O(1)，q 次查询的时间复杂度为O(q)，预处理的时间复杂度为O(nm)，所以总时间复杂度为O(nm + q)。
差分
- 概念：差分可以看成前缀和的逆运算，差分问题一般分为一维差分和二维差分
- 差分优点：可在
O(1)时间实现区间增减，提高算法效率
一维差分
差分数组推导：
差分可以看成前缀和的逆运算。首先给定一个原数组a ：a[1], a[2], a[3],……,a[n];，我们构造一个数组b ： b[1] ,b[2] , b[3],……, b[i];，使得 a[i] = b[1] + b[2 ]+ b[3] +,,,,,, + b[i]，也就是说，a数组是b数组的前缀和数组，反过来我们把b数组叫做a数组的差分数组。我们可发现，每一个a[i]都是b数组中从头开始的一段区间和。那么如何构造差分数组b？最直接的方法如下：
a[0 ]= 0
b[1] = a[1] - a[0]
b[2] = a[2] - a[1]
……
b[n] = a[n] - a[n-1]
我们只要有b数组，通过前缀和运算，就可以在O(n) 的时间内得到a数组。
差分数组运用：
考虑一个例子，在给定的数组a中，我们有 m 次修改，每次都给一个区间[l,r]的所有数字都加上c,即 a[l] + c , a[l+1] + c , a[l+2] + c ,,,,,, a[r] + c。暴力做法是for循环l到r区间，时间复杂度O(n)，如果执行m次这样的操作，时间复杂度就会变成O(n*m)，当 n 、m 都比较大的时候，很容易超时。
如果需要更高效的算法，差分数组就可以派上用场了。始终要记得，a数组是b数组的前缀和数组，如果对b数组的b[i]做出更新(比如加上c)，在前缀和反推a数组时会把该更新应用从a[i]开始的往后的每一个数。
如果 b[i] 变为 b[i] + c
a[i] = a[i-1] + b[i] + c = b[1] + b[2] + …… + b[i] + c
a[i+1] = a[i] + b[i+1] = b[1] + b[2] + …… + b[i] + b[i+1] + c
a[i+2] = a[i+1] + b[i+2] = b[1] + b[2] + …… + b[i] + b[i+1] + b[i+2] + c
……
对于区间[l,r]的修改，我们只需要打上一个补丁：首先让差分b数组中的 b[l] + c，接着让b[r+1] - c。我们可以发现，第一步把a数组变成 a[l] + c ,a[l+1] + c,,,,,, a[n] + c，第二步把a数组变成 a[r+1] - c,a[r+2] - c,,,,,,,a[n] - c。即做出类似如下图例的操作：
b[l] + c，效果使得a数组中 a[l]及以后的数都加上了c(红色部分)，但我们只要求[l,r]区间加上c, 因此还需要执行 b[r+1] - c,让a数组中a[r+1]及往后的区间再减去c(绿色部分)，这样对于a[r] 以后区间的数相当于没有发生改变。因此我们可以得出一维差分结论：给a数组中的[l, r]区间中的每一个数都加上c,只需对差分数组b做 b[l] + = c, b[r+1] - = c（减去一个数的操作类似）。时间复杂度为O(1), 大大提高了算法的效率。
二维差分
拓展到二维的情况：
如果扩展到二维，问题就会变成让二维数组被选中的子矩阵中的每个元素的值加上c，该问题同样也可以使用二维差分达到O(1)的时间复杂度。对于给定的数组 a[][] ，我们同样也去构建一个数组b[][]，使得a数组中a[i][j]是b数组左上角(1,1)到右下角(i,j)所包围矩形元素的和，此时b[][]则是a[][]的差分数组。
如何构造二维差分数组？
其实无论是一维差分还是二维差分，我们并不用考虑其构造方法，因为我们在使用差分操作在对原数组进行修改的过程中（a[i]可理解为给区间[i,i]加上a[i]），实际上就可以构造出差分数组。
二维差分推导：
同一维差分，我们构造二维差分数组目的是为了让原二维数组a中所选中子矩阵中的每一个元素加上c的操作，始终要记得，a数组是b数组的前缀和数组，对b数组的b[i][j]的修改，会影响到a数组中从a[i][j]及往后的每一个数。
已知原数组a中被选中的子矩阵为 以(x1,y1)为左上角，以(x2,y2)为右下角所围成的矩形区域，假定我们已经构造好了b数组，类比一维差分，我们可以执行以下操作来使被选中的子矩阵中的每个元素的值加上c
b[x1][y1] += cb[x1][y2+1] -= cb[x2+1][y1] -= cb[x2+1][y2+1] += c
每次对b数组执行以上操作，等价于以下代码，上述操作时间复杂度为O(1)：
for(int i = x1; i <= x2; i++) {
for(int j = y1; j <= y2; j++) {
a[i][j]+=c;
}
}我们画一个图去理解这个过程：
b[x1][y1] +=c；对应下图1 ,让整个a数组中蓝色矩形面积的元素都加上了c。b[x1][y2+1]-=c；对应下图2 ,让整个a数组中绿色矩形面积的元素再减去c，使其内元素不发生改变。b[x2+1][y1]-=c； 对应下图3 ,让整个a数组中紫色矩形面积的元素再减去c，使其内元素不发生改变。b[x2+1][y2+1]+=c；对应下图4,让整个a数组中红色矩形面积的元素再加上c，红色内的相当于被减了两次，所以要再加上一次
我们将上述过程封装成代码：
void insert(int x1,int y1,int x2,int y2,int c)
{
//对b数组执行插入操作，等价于对a数组中的(x1,y1)到(x2,y2)之间的元素都加上了c
b[x1][y1]+=c;
b[x2+1][y1]-=c;
b[x1][y2+1]-=c;
b[x2+1][y2+1]+=c;
}我们可以先假想 a 数组为空，那么 b 数组一开始也为空，但是实际上 a 数组并不为空，因此我们每次让以(i,j)为左上角到以(i,j)为右下角面积内元素(其实就是一个小方格的面积)去插入 a 数组的初始值a[i][j]，等价于原数组 a 中 (i,j) 到 (i,j) 范围内加上了 a[i][j] ，因此执行n*m次插入操作，就成功构建了差分b数组，时间复杂度为O(nm)。
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
scanf("%d", &a[i][j]);
insert(i,j,i,j,a[i][j]); //构建差分数组
}
}
当然关于二维差分操作也有直接的构造方法，公式如下：b[i][j]=a[i][j]−a[i−1][j]−a[i][j−1]+a[i−1][j−1]
参考资料
版权属于：PCsky
本文链接：http://hyouka.club/index.php/archives/195/
转载时须注明出处及本声明