前缀和与差分 图文并茂 超级详细整理(全网最通俗易懂) 太过爱你忘了你带给我的痛 2021-07-25 02:40 595阅读 0赞 > 前缀和是指某序列的前n项和,可以把它理解为数学上的数列的前n项和,而差分可以看成前缀和的逆运算。合理的使用前缀和与差分,可以将某些复杂的问题简单化。 ### 前缀和: ### -------------------- ![加粗样式][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70] ## **前缀和算法有什么好处?** ## **先来了解这样一个问题:** 输入一个长度为n的整数序列。接下来再输入m个询问,每个询问输入一对l, r。对于每个询问,输出原序列中从第l个数到第r个数的和。 我们很容易想出暴力解法,遍历区间求和。 **代码如下:** int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); while(m--) { int l,r; int sum=0; scanf("%d%d",&l,&r); for(int i=l;i<=r;i++) { sum+=a[i]; } printf("%d\n",sum); } 这样的时间复杂度为`O(n*m)`,如果`n`和`m`的数据量稍微大一点就有可能超时,而我们如果使用前缀和的方法来做的话就能够将时间复杂度降到`O(n+m)`,大大提高了运算效率。 **具体做法:** 首先做一个预处理,定义一个`sum[]`数组,`sum[i]`代表`a`数组中前`i`个数的和。 **求前缀和运算:** const int N=1e5+10; int sum[N],a[N]; //sum[i]=a[1]+a[2]+a[3].....a[i]; for(int i=1;i<=n;i++) { sum[i]=sum[i-1]+a[i]; } **然后查询操作:** scanf("%d%d",&l,&r); printf("%d\n", sum[r]-sum[l-1]); 对于每次查询,只需执行`sum[r]-sum[l-1]` ,时间复杂度为`O(1)` **原理** `sum[r] =a[1]+a[2]+a[3]+a[l-1]+a[l]+a[l+1]......a[r]`; `sum[l-1]=a[1]+a[2]+a[3]+a[l-1]`; `sum[r]-sum[l-1]=a[l]+a[l+1]+......+a[r]`; **图解** ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 1] 这样,对于每个询问,`只需要执行 sum[r]-sum[l-1]`。输出原序列中从第`l`个数到第r个数的和的时间复杂度变成了`O(1)`。 我们把它叫做**一维前缀和**。 **总结:** ![20201217171740805.png][] **练习一道题目** 输入一个长度为n的整数序列。 接下来再输入m个询问,每个询问输入一对l, r。 对于每个询问,输出原序列中从第l个数到第r个数的和。 **输入格式** 第一行包含两个整数n和m。 第二行包含n个整数,表示整数数列。 接下来m行,每行包含两个整数l和r,表示一个询问的区间范围。 **输出格式** 共m行,每行输出一个询问的结果。 **数据范围** 1≤l≤r≤n, 1≤n,m≤100000, −1000≤数列中元素的值≤1000 **输入样例:** 5 3 2 1 3 6 4 1 2 1 3 2 4 **输出样例:** 3 6 10 **代码:** #include <iostream> using namespace std; const int N = 100010; int n, m; int a[N], s[N]; int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]); for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i]; // 前缀和的初始化 while (m -- ) { int l, r; scanf("%d%d", &l, &r); printf("%d\n", s[r] - s[l - 1]); // 区间和的计算 } return 0; } ## 二维前缀和 ## **如果数组变成了二维数组怎么办呢?** **先给出问题:** 输入一个n行m列的整数矩阵,再输入q个询问,每个询问包含四个整数x1, y1, x2, y2,表示一个子矩阵的左上角坐标和右下角坐标。对于每个询问输出子矩阵中所有数的和。 同一维前缀和一样,我们先来定义一个二维数组`s[][]`, `s[i][j]`表示二维数组中,左上角`(1,1)`到右下角`( i,j )`所包围的矩阵元素的和。接下来推导二维前缀和的公式。 先看一张图: ![20201214201734653.png][] **紫色面积**是指`(1,1)`左上角到`(i,j-1)`右下角的矩形面积, **绿色面积**是指`(1,1)`左上角到`(i-1, j )`右下角的矩形面积。**每一个颜色的矩形面积都代表了它所包围元素的和。** ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 2] **从图中我们很容易看出**,整个外围蓝色矩形面积`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 ] + a[i] [j] - s[i-1][ j-1]` **接下来回归问题**去求以`(x1,y1)`为左上角和以`(x2,y2)`为右下角的矩阵的元素的和。 **如图:** ![20201214204543274.png][] **紫色面积**是指 `( 1,1 )`左上角到`(x1-1,y2)`右下角的矩形面积 ,**黄色面积**是指`(1,1)`左上角到`(x2,y1-1)`右下角的矩形面积; **不难推出:** ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 3] 绿色矩形的面积 = 整个外围面积`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]` **总结:** ![2020121717185394.png][] **练习一道完整题目:** 输入一个n行m列的整数矩阵,再输入q个询问,每个询问包含四个整数x1, y1, x2, y2,表示一个子矩阵的左上角坐标和右下角坐标。 对于每个询问输出子矩阵中所有数的和。 **输入格式** 第一行包含三个整数n,m,q。 接下来n行,每行包含m个整数,表示整数矩阵。 接下来q行,每行包含四个整数x1, y1, x2, y2,表示一组询问。 **输出格式** 共q行,每行输出一个询问的结果。 **数据范围** 1≤n,m≤1000, 1≤q≤200000, 1≤x1≤x2≤n, 1≤y1≤y2≤m, −1000≤矩阵内元素的值≤1000 **输入样例:** 3 4 3 1 7 2 4 3 6 2 8 2 1 2 3 1 1 2 2 2 1 3 4 1 3 3 4 **输出样例:** 17 27 21 **代码:** #include<iostream> #include<cstdio> using namespace std; const int N=1010; int a[N][N],s[N][N]; int main() { int n,m,q; 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]); 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]+a[i][j]-s[i-1][j-1]; while(q--) { int x1,y1,x2,y2; scanf("%d%d%d%d",&x1,&y1,&x2,&y2); printf("%d\n",s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]); } return 0; } ## 差分 ## -------------------- ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 4] ## 一维差分 ## 类似于数学中的求导和积分,**差分可以看成前缀和的逆运算。** **差分数组:** 首先给定一个原数组`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[3] =a [3] - a[2]`; `........` `b[n] = a[n] - a[n-1]`; **图示:** ![20201215214337143.png][] 我们只要有`b`数组,通过前缀和运算,就可以在`O(n)` 的时间内得到`a`数组 。 **知道了差分数组有什么用呢?** 别着急,慢慢往下看。 **话说有这么一个问题:** 给定区间`[l ,r ]`,让我们把`a`数组中的`[ 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)`。有没有更高效的做法吗? **考虑差分做法**,(差分数组派上用场了)。 **始终要记得,a数组是b数组的前缀和数组**,比如对`b`数组的`b[i]`的修改,会影响到`a`数组中从`a[i]`及往后的每一个数。 首先让差分`b`数组中的 `b[l] + c` ,通过前缀和运算,`a`数组变成 `a[l] + c ,a[l+1] + c,,,,,, a[n] + c`; 然后我们打个补丁,`b[r+1] - c`, 通过前缀和运算,`a`数组变成 `a[r+1] - c,a[r+2] - c,,,,,,,a[n] - c`; **为啥还要打个补丁?** **我们画个图理解一下这个公式的由来:** ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 5] `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)`, 大大提高了效率。 **总结:** ![在这里插入图片描述][20201217172005485.png] **题目练习:** **AcWing 797. 差分** 输入一个长度为n的整数序列。 接下来输入m个操作,每个操作包含三个整数l, r, c,表示将序列中\[l, r\]之间的每个数加上c。 请你输出进行完所有操作后的序列。 **输入格式** 第一行包含两个整数n和m。 第二行包含n个整数,表示整数序列。 接下来m行,每行包含三个整数l,r,c,表示一个操作。 **输出格式** 共一行,包含n个整数,表示最终序列。 **数据范围** 1≤n,m≤100000, 1≤l≤r≤n, −1000≤c≤1000, −1000≤整数序列中元素的值≤1000 **输入样例:** 6 3 1 2 2 1 2 1 1 3 1 3 5 1 1 6 1 **输出样例:** 3 4 5 3 4 2 **AC代码** //差分 时间复杂度 o(m) #include<iostream> using namespace std; const int N=1e5+10; int a[N],b[N]; int main() { int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); b[i]=a[i]-a[i-1]; //构建差分数组 } int l,r,c; while(m--) { scanf("%d%d%d",&l,&r,&c); b[l]+=c; //表示将序列中[l, r]之间的每个数加上c b[r+1]-=c; } for(int i=1;i<=n;i++) { b[i]+=b[i-1]; //求前缀和运算 printf("%d ",b[i]); } return 0; } ## 二维差分 ## 如果扩展到二维,我们需要让二维数组被选中的子矩阵中的每个元素的值加上`c`,是否也可以达到`O(1)`的时间复杂度。答案是可以的,**考虑二维差分**。 `a[][]`数组是`b[][]`数组的前缀和数组,那么`b[][]`是`a[][]`的差分数组 原数组: `a[i][j]` 我们去构造差分数组: `b[i][j]` 使得`a`数组中`a[i][j]`是`b`数组左上角`(1,1)`到右下角`(i,j)`所包围矩形元素的和。 **如何构造`b`数组呢?** 其实关于差分数组,我们并不用考虑其构造方法,因为我们使用差分操作在对原数组进行修改的过程中,实际上就可以构造出差分数组。 同一维差分,我们构造二维差分数组目的是为了 让原二维数组`a`中所选中子矩阵中的每一个元素加上`c`的操作,可以由`O(n*n)`的时间复杂度优化成`O(1)` 已知原数组`a`中被选中的子矩阵为 以`(x1,y1)`为左上角,以`(x2,y2)`为右上角所围成的矩形区域; **始终要记得,a数组是b数组的前缀和数组**,比如对`b`数组的`b[i][j]`的修改,会影响到`a`数组中从`a[i][j]`及往后的每一个数。 假定我们已经构造好了`b`数组,类比一维差分,我们执行以下操作 来使被选中的子矩阵中的每个元素的值加上`c` `b[x1][y1] + = c`; `b[x1,][y2+1] - = c`; `b[x2+1][y1] - = c`; `b[x2+1][y2+1] + = c`; 每次对`b`数组执行以上操作,**等价于:** for(int i=x1;i<=x2;i++) for(int j=y1;j<=y2;j++) a[i][j]+=c; **我们画个图去理解一下这个过程:** ![20201217171134926.png][] `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`,红色内的相当于**被减了两次**,再加上一次`c`,才能使其恢复。 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 6] **我们将上述操作封装成一个插入函数:** 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)`为右上角面积内元素(其实就是一个小方格的面积)去插入 `c=a[i][j]`,等价于原数组`a`中`(i,j)` 到`(i,j)`范围内 加上了 `a[i][j]` ,因此执行`n*m`次插入操作,就成功构建了差分`b`数组. **这叫做曲线救国。** **代码如下:** for(int i=1;i<=n;i++) { for(int j=1;j<=m;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]` 二维差分数组的构造同一维差分思维相同,因次在这里就不再展开叙述了。 **总结:** ![在这里插入图片描述][20201217172035975.png] **题目练习:** **AcWing 798. 差分矩阵** 输入一个n行m列的整数矩阵,再输入q个操作,每个操作包含五个整数x1, y1, x2, y2, c,其中(x1, y1)和(x2, y2)表示一个子矩阵的左上角坐标和右下角坐标。 每个操作都要将选中的子矩阵中的每个元素的值加上c。 请你将进行完所有操作后的矩阵输出。 **输入格式** 第一行包含整数n,m,q。 接下来n行,每行包含m个整数,表示整数矩阵。 接下来q行,每行包含5个整数x1, y1, x2, y2, c,表示一个操作。 **输出格式** 共 n 行,每行 m 个整数,表示所有操作进行完毕后的最终矩阵。 **数据范围** 1≤n,m≤1000, 1≤q≤100000, 1≤x1≤x2≤n, 1≤y1≤y2≤m, −1000≤c≤1000, −1000≤矩阵内元素的值≤1000 **输入样例:** 3 4 3 1 2 2 1 3 2 2 1 1 1 1 1 1 1 2 2 1 1 3 2 3 2 3 1 3 4 1 **输出样例:** 2 3 4 1 4 3 4 1 2 2 2 2 **AC代码:** include<iostream> #include<cstdio> using namespace std; const int N=1e3+10; int a[N][N],b[N][N]; void insert(int x1,int y1,int x2,int y2,int c) { b[x1][y1]+=c; b[x2+1][y1]-=c; b[x1][y2+1]-=c; b[x2+1][y2+1]+=c; } int main() { int n,m,q; cin>>n>>m>>q; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j]; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { insert(i,j,i,j,a[i][j]); //构建差分数组 } } while(q--) { int x1,y1,x2,y2,c; cin>>x1>>y1>>x2>>y2>>c; insert(x1,y1,x2,y2,c); } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1]; } } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { printf("%d ",b[i][j]); } printf("\n"); } return 0; } 如果我的文章对你有帮助,请点点关注,你的关注是对我创作的最大支持。 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 7] [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]: /images/20210724/04257db1adaa456999daa1ba2d2b4ef0.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 1]: /images/20210724/99a715da452743d9ab5a1e9b3c513ee8.png [20201217171740805.png]: /images/20210724/ddc0631c34594b4d9f6edfd70d43582c.png [20201214201734653.png]: /images/20210724/2148706e3a7d4e80a68b7c8fc5e227ff.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 2]: /images/20210724/c85a0515426140eb9918f3eb09abd877.png [20201214204543274.png]: /images/20210724/22d9e98ca5f34e2bb043293517ac5cb0.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 3]: /images/20210724/3c8a0e587b89436d84d6c64bf4d5d7ad.png [2020121717185394.png]: /images/20210724/5f36b5cea4ba4821bbd61df4de8b59cf.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 4]: /images/20210724/a65ce229e2304f0db3e1eb668efae0b3.png [20201215214337143.png]: /images/20210724/29d87cacec87478e808c84c6fc07f1c4.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 5]: /images/20210724/b7dc21a567bf4895ab4bf44339dacdbf.png [20201217172005485.png]: /images/20210724/32b91c3179a74f52ad156c073646283d.png [20201217171134926.png]: /images/20210724/0d7696afeda54c14a7be335e6a384e6d.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 6]: /images/20210724/84f65e0d2c8e492880fe7f4083e1d1f8.png [20201217172035975.png]: /images/20210724/89e9ad592acc4698ba269ded06b31f9d.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 7]: /images/20210724/b235180fa3df4d9abaaf9e054d5d48b3.png
还没有评论,来说两句吧...