通俗易懂的C++前缀和与差分算法图文示例详解

1、前缀和前缀和是指某序列的前n项和可以把它理解为数学上的数列的前n项和而差分可以看成前缀和的逆运算。合理的使用前缀和与差分可以将某些复杂的问题简单化。2、前缀和算法有什么好处先来了解这样一个问题输入一个长度为n的整数序列。接下来再输入m个询问每个询问输入一对l, r。对于每个询问输出原序列中从第l个数到第r个数的和。我们很容易想出暴力解法遍历区间求和。代码如下1234567891011121314intn,m;scanf(%d%d,n,m);for(inti1;in;i)scanf(%d,a[i]);while(m--){intl,r;intsum0;scanf(%d%d,l,r);for(intil;ir;i){suma[i];}printf(%d\n,sum);}这样的时间复杂度为O(n*m)如果n和m的数据量稍微大一点就有可能超时而我们如果使用前缀和的方法来做的话就能够将时间复杂度降到O(nm),大大提高了运算效率。具体做法首先做一个预处理定义一个sum[]数组sum[i]代表a数组中前i个数的和。求前缀和运算123456constintN1e510;intsum[N],a[N];//sum[i]a[1]a[2]a[3].....a[i];for(inti1;in;i){sum[i]sum[i-1]a[i];}然后查询操作12scanf(%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[l1]......a[r];sum[l-1]a[1]a[2]a[3]a[l-1];sum[r]-sum[l-1]a[l]a[l1]......a[r];图解这样对于每个询问只需要执行sum[r]-sum[l-1]。输出原序列中从第l个数到第r个数的和的时间复杂度变成了O(1)。我们把它叫做一维前缀和。总结练习一道题目输入一个长度为n的整数序列。接下来再输入m个询问每个询问输入一对l, r。对于每个询问输出原序列中从第l个数到第r个数的和。输入格式第一行包含两个整数n和m。第二行包含n个整数表示整数数列。接下来m行每行包含两个整数l和r表示一个询问的区间范围。输出格式共m行每行输出一个询问的结果。数据范围1≤l≤r≤n,1≤n,m≤100000,−1000≤数列中元素的值≤1000输入样例5 32 1 3 6 41 21 32 4输出样例3610代码123456789101112131415161718#include iostreamusingnamespacestd;constintN 100010;intn, m;inta[N], s[N];intmain(){scanf(%d%d, n, m);for(inti 1; i n; i )scanf(%d, a[i]);for(inti 1; i n; i ) s[i] s[i - 1] a[i];// 前缀和的初始化while(m -- ){intl, r;scanf(%d%d, l, r);printf(%d\n, s[r] - s[l - 1]);// 区间和的计算}return0;}3、二维前缀和如果数组变成了二维数组怎么办呢先给出问题输入一个n行m列的整数矩阵再输入q个询问每个询问包含四个整数x1, y1, x2, y2表示一个子矩阵的左上角坐标和右下角坐标。对于每个询问输出子矩阵中所有数的和。同一维前缀和一样我们先来定义一个二维数组s[][],s[i][j]表示二维数组中左上角(1,1)到右下角( i,j )所包围的矩阵元素的和。接下来推导二维前缀和的公式。先看一张图紫色面积是指(1,1)左上角到(i,j-1)右下角的矩形面积, 绿色面积是指(1,1)左上角到(i-1, j )右下角的矩形面积。每一个颜色的矩形面积都代表了它所包围元素的和。从图中我们很容易看出整个外围蓝色矩形面积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)为右下角的矩阵的元素的和。如图紫色面积是指( 1,1 )左上角到(x1-1,y2)右下角的矩形面积 黄色面积是指(1,1)左上角到(x2,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]总结练习一道完整题目输入一个n行m列的整数矩阵再输入q个询问每个询问包含四个整数x1, y1, x2, y2表示一个子矩阵的左上角坐标和右下角坐标。对于每个询问输出子矩阵中所有数的和。输入格式第一行包含三个整数nmq。接下来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 31 7 2 43 6 2 82 1 2 31 1 2 22 1 3 41 3 3 4输出样例172721代码1234567891011121314151617181920212223#includeiostream#includecstdiousingnamespacestd;constintN1010;inta[N][N],s[N][N];intmain(){intn,m,q;scanf(%d%d%d,n,m,q);for(inti1;in;i)for(intj1;jm;j)scanf(%d,a[i][j]);for(inti1;in;i)for(intj1;jm;j)s[i][j]s[i-1][j]s[i][j-1]a[i][j]-s[i-1][j-1];while(q--){intx1,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]);}return0;}4、差分5、一维差分类似于数学中的求导和积分差分可以看成前缀和的逆运算。差分数组首先给定一个原数组aa[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];图示:我们只要有b数组通过前缀和运算就可以在O(n)的时间内得到a数组 。知道了差分数组有什么用呢 别着急慢慢往下看。话说有这么一个问题给定区间[l ,r ]让我们把a数组中的[ l, r]区间中的每一个数都加上c,即 a[l] c , a[l1] c , a[l2] 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[l1] c,,,,,, a[n] c;然后我们打个补丁b[r1] - c, 通过前缀和运算a数组变成 a[r1] - c,a[r2] - c,,,,,,,a[n] - c;为啥还要打个补丁我们画个图理解一下这个公式的由来:b[l] c效果使得a数组中a[l]及以后的数都加上了c(红色部分)但我们只要求l到r区间加上c, 因此还需要执行b[r1] - c,让a数组中a[r1]及往后的区间再减去c(绿色部分)这样对于a[r]以后区间的数相当于没有发生改变。因此我们得出一维差分结论给a数组中的[ l, r]区间中的每一个数都加上c,只需对差分数组b做b[l] c,b[r1] - c。时间复杂度为O(1), 大大提高了效率。总结题目练习 AcWing 797. 差分输入一个长度为n的整数序列。接下来输入m个操作每个操作包含三个整数l, r, c表示将序列中[l, r]之间的每个数加上c。请你输出进行完所有操作后的序列。输入格式第一行包含两个整数n和m。第二行包含n个整数表示整数序列。接下来m行每行包含三个整数lrc表示一个操作。输出格式共一行包含n个整数表示最终序列。数据范围1≤n,m≤100000,1≤l≤r≤n,−1000≤c≤1000,−1000≤整数序列中元素的值≤1000输入样例6 31 2 2 1 2 11 3 13 5 11 6 1输出样例3 4 5 3 4 2AC代码12345678910111213141516171819202122232425262728//差分 时间复杂度 o(m)#includeiostreamusingnamespacestd;constintN1e510;inta[N],b[N];intmain(){intn,m;scanf(%d%d,n,m);for(inti1;in;i){scanf(%d,a[i]);b[i]a[i]-a[i-1];//构建差分数组}intl,r,c;while(m--){scanf(%d%d%d,l,r,c);b[l]c;//表示将序列中[l, r]之间的每个数加上cb[r1]-c;}for(inti1;in;i){b[i]b[i-1];//求前缀和运算printf(%d ,b[i]);}return0;}6、二维差分如果扩展到二维我们需要让二维数组被选中的子矩阵中的每个元素的值加上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数组类比一维差分我们执行以下操作来使被选中的子矩阵中的每个元素的值加上cb[x1][y1] c;b[x1,][y21] - c;b[x21][y1] - c;b[x21][y21] c;每次对b数组执行以上操作等价于123for(intix1;ix2;i)for(intjy1;jy2;j)a[i][j]c;我们画个图去理解一下这个过程b[x1][ y1 ] c; 对应图1 ,让整个a数组中蓝色矩形面积的元素都加上了c。b[x1,][y21]-c; 对应图2 ,让整个a数组中绿色矩形面积的元素再减去c使其内元素不发生改变。b[x21][y1]- c; 对应图3 ,让整个a数组中紫色矩形面积的元素再减去c使其内元素不发生改变。b[x21][y21]c; 对应图4,让整个a数组中红色矩形面积的元素再加上c红色内的相当于被减了两次再加上一次c才能使其恢复。我们将上述操作封装成一个插入函数:1234567voidinsert(intx1,inty1,intx2,inty2,intc){//对b数组执行插入操作等价于对a数组中的(x1,y1)到(x2,y2)之间的元素都加上了cb[x1][y1]c;b[x21][y1]-c;b[x1][y21]-c;b[x21][y21]c;}我们可以先假想a数组为空那么b数组一开始也为空但是实际上a数组并不为空因此我们每次让以(i,j)为左上角到以(i,j)为右上角面积内元素(其实就是一个小方格的面积)去插入ca[i][j]等价于原数组a中(i,j)到(i,j)范围内 加上了a[i][j],因此执行n*m次插入操作就成功构建了差分b数组.这叫做曲线救国。代码如下1234567for(inti1;in;i){for(intj1;jm;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]二维差分数组的构造同一维差分思维相同因次在这里就不再展开叙述了。总结题目练习 AcWing 798. 差分矩阵输入一个n行m列的整数矩阵再输入q个操作每个操作包含五个整数x1, y1, x2, y2, c其中(x1, y1)和(x2, y2)表示一个子矩阵的左上角坐标和右下角坐标。每个操作都要将选中的子矩阵中的每个元素的值加上c。请你将进行完所有操作后的矩阵输出。