前缀和差分是一对逆运算1.一维前缀和有一个长度为n的数组an:a1,a2…an;对于前缀和Si a1a2…ai如何求Si,S[i] s[i-1]a[i]前缀和可以快速求出原数组里面一段数的和。比如求一段区间[l,r],如果按照原来的做法需要循环一遍O(n),有前缀和的算法这个区间的数就是(Sr) - (sl-1)。同时为了方便计算令s[0] 0.比如计算[1,l],既s[l]-s[0] s[l].其实前缀和就是一个区间相减的操作统一处理。前缀和其实是非常简单的练习题输入一个长度为 nn 的整数序列。接下来再输入 mm 个询问每个询问输入一对 l,rl,r。对于每个询问输出原序列中从第 ll 个数到第 rr 个数的和。输入格式第一行包含两个整数 nn 和 mm。第二行包含 nn 个整数表示整数数列。接下来 mm 行每行包含两个整数 ll 和 rr表示一个询问的区间范围。输出格式共 mm 行每行输出一个询问的结果。数据范围1≤l≤r≤n1≤l≤r≤n,1≤n,m≤1000001≤n,m≤100000,−1000≤数列中元素的值≤1000123456789101112131415161718#include iostreamusingnamespacestd;constintN 100010;intn,m;inta[N],S[N];intmain(){scanf(%d%d,n,m);for(inti 1;in;i)scanf(%d,a[i]);for(inti 1;in;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;}2.二维前缀和二维前缀和是在一个二维矩阵里求子矩阵的和练习题输入一个 nn 行 mm 列的整数矩阵再输入 qq 个询问每个询问包含四个整数 x1,y1,x2,y2x1,y1,x2,y2表示一个子矩阵的左上角坐标和右下角坐标。对于每个询问输出子矩阵中所有数的和。输入格式第一行包含三个整数 nmqnmq。接下来 nn 行每行包含 mm 个整数表示整数矩阵。接下来 qq 行每行包含四个整数 x1,y1,x2,y2x1,y1,x2,y2表示一组询问。输出格式共 qq 行每行输出一个询问的结果。数据范围1≤n,m≤10001≤n,m≤1000,1≤q≤2000001≤q≤200000,1≤x1≤x2≤n1≤x1≤x2≤n,1≤y1≤y2≤m1≤y1≤y2≤m,−1000≤矩阵内元素的值≤1000\12345678910111213141516171819202122232425#include iostreamusingnamespacestd;constintN 1010;intn,m,q;longa[N][N],s[N][N];intmain(){scanf(%d%d%d,n,m,q);for(inti 1;in;i){for(intj 1;jm;j){scanf(%d,a[i][j]);//求前缀和s[i][j] s[i-1][j]s[i][j-1]-s[i-1][j-1]a[i][j];}}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;}3.一维差分给定a[1],a[2],…,a[n]构造差分数组b[N],使得a[i] b[1]b[2]…b[i]b1 a1,b2 a2-a1,b3 a3-a2,直到bn an-an-1b是a的差分a是b的前缀和。有b数组就可以通过O(n)的时间复杂度得到a数组。推导过程现在在a数组[L,R]中全部加上C那就是alC,al1C,…,arC,通过暴力的方式O(n)可以求解那差分可以变成O(1)在[L,R]中如果我们在b数组blC,那么al也会加上Cal1也会加上C…an1也会加上C因为每一次都会加上一个bl。但是我们只要al到ar加上C那么ar后面不要加上C那么我们直接让br-c即可完成数组a在[L,R]范围里全部加上C。核心操作是将a[L~R]全部加上C等价于b[L] C,b[R1]-C把O(n)提高到O(1)假定a数组全是初始化为0那b数组也是全为0但是题目a数组并不是0我们可以看成进行n次插入操作第一次是在原数组a[1,1]加上a1,第二次是在原数组a[2,2]加上a2…以此类推即可所以并不需要去想如何构造差分题目输入一个长度为 nn 的整数序列。接下来输入 mm 个操作每个操作包含三个整数 l,r,cl,r,c表示将序列中 [l,r][l,r] 之间的每个数加上 cc。请你输出进行完所有操作后的序列。
前缀和差分是一对逆运算1.一维前缀和有一个长度为n的数组an:a1,a2…an;对于前缀和Si a1a2…ai如何求Si,S[i] s[i-1]a[i]前缀和可以快速求出原数组里面一段数的和。比如求一段区间[l,r],如果按照原来的做法需要循环一遍O(n),有前缀和的算法这个区间的数就是(Sr) - (sl-1)。同时为了方便计算令s[0] 0.比如计算[1,l],既s[l]-s[0] s[l].其实前缀和就是一个区间相减的操作统一处理。前缀和其实是非常简单的练习题输入一个长度为 nn 的整数序列。接下来再输入 mm 个询问每个询问输入一对 l,rl,r。对于每个询问输出原序列中从第 ll 个数到第 rr 个数的和。输入格式第一行包含两个整数 nn 和 mm。第二行包含 nn 个整数表示整数数列。接下来 mm 行每行包含两个整数 ll 和 rr表示一个询问的区间范围。输出格式共 mm 行每行输出一个询问的结果。数据范围1≤l≤r≤n1≤l≤r≤n,1≤n,m≤1000001≤n,m≤100000,−1000≤数列中元素的值≤1000123456789101112131415161718#include iostreamusingnamespacestd;constintN 100010;intn,m;inta[N],S[N];intmain(){scanf(%d%d,n,m);for(inti 1;in;i)scanf(%d,a[i]);for(inti 1;in;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;}2.二维前缀和二维前缀和是在一个二维矩阵里求子矩阵的和练习题输入一个 nn 行 mm 列的整数矩阵再输入 qq 个询问每个询问包含四个整数 x1,y1,x2,y2x1,y1,x2,y2表示一个子矩阵的左上角坐标和右下角坐标。对于每个询问输出子矩阵中所有数的和。输入格式第一行包含三个整数 nmqnmq。接下来 nn 行每行包含 mm 个整数表示整数矩阵。接下来 qq 行每行包含四个整数 x1,y1,x2,y2x1,y1,x2,y2表示一组询问。输出格式共 qq 行每行输出一个询问的结果。数据范围1≤n,m≤10001≤n,m≤1000,1≤q≤2000001≤q≤200000,1≤x1≤x2≤n1≤x1≤x2≤n,1≤y1≤y2≤m1≤y1≤y2≤m,−1000≤矩阵内元素的值≤1000\12345678910111213141516171819202122232425#include iostreamusingnamespacestd;constintN 1010;intn,m,q;longa[N][N],s[N][N];intmain(){scanf(%d%d%d,n,m,q);for(inti 1;in;i){for(intj 1;jm;j){scanf(%d,a[i][j]);//求前缀和s[i][j] s[i-1][j]s[i][j-1]-s[i-1][j-1]a[i][j];}}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;}3.一维差分给定a[1],a[2],…,a[n]构造差分数组b[N],使得a[i] b[1]b[2]…b[i]b1 a1,b2 a2-a1,b3 a3-a2,直到bn an-an-1b是a的差分a是b的前缀和。有b数组就可以通过O(n)的时间复杂度得到a数组。推导过程现在在a数组[L,R]中全部加上C那就是alC,al1C,…,arC,通过暴力的方式O(n)可以求解那差分可以变成O(1)在[L,R]中如果我们在b数组blC,那么al也会加上Cal1也会加上C…an1也会加上C因为每一次都会加上一个bl。但是我们只要al到ar加上C那么ar后面不要加上C那么我们直接让br-c即可完成数组a在[L,R]范围里全部加上C。核心操作是将a[L~R]全部加上C等价于b[L] C,b[R1]-C把O(n)提高到O(1)假定a数组全是初始化为0那b数组也是全为0但是题目a数组并不是0我们可以看成进行n次插入操作第一次是在原数组a[1,1]加上a1,第二次是在原数组a[2,2]加上a2…以此类推即可所以并不需要去想如何构造差分题目输入一个长度为 nn 的整数序列。接下来输入 mm 个操作每个操作包含三个整数 l,r,cl,r,c表示将序列中 [l,r][l,r] 之间的每个数加上 cc。请你输出进行完所有操作后的序列。
