本文主要是介绍差分、前缀和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
P8218 【深进1.例1】求区间和 （前缀和）
#include <bits/stdc++.h>
using namespace std;
int n, m, a[100010], sum[100010], ans, l, r;
int main()
{scanf("%d", &n);for(int i=1; i<=n; ++i){scanf("%d", &a[i]);sum[i]=sum[i-1]+a[i];}scanf("%d", &m);while(m--){scanf("%d %d", &l, &r);ans=sum[r]-sum[l-1];printf("%d\n", ans);}return 0;
}P6568 [NOI Online #3 提高组] 水壶
#include <bits/stdc++.h>
using namespace std;
const int N=1000010;
int n, k, a[N], sum[N], ans;
int main()
{scanf("%d %d", &n, &k);for(int i=1; i<=n; ++i){scanf("%d", &a[i]);sum[i]=sum[i-1]+a[i];}for(int i=1; i+k<=n; ++i){ans=max(ans, sum[i+k]-sum[i-1]);}printf("%d", ans);return 0;
}P1865 A % B Problem（判断质数+区间查询+前缀和）
#include <bits/stdc++.h>
using namespace std;
int l, r, n, m, sum[1000010];
bool check(int x)
{if(x<2){return false;}for(int i=2; i<=sqrt(x); ++i){if(x%i==0){return false;}}return true;
}
int main()
{scanf("%d %d", &n, &m);for(int i=2; i<=m; ++i){if(check(i)){sum[i]=sum[i-1]+1;}else{sum[i]=sum[i-1];}}while(n--){scanf("%d %d", &l, &r);if(l<1 || l>m || r<1 || r>m){printf("Crossing the line\n");}else if(l>r){printf("0\n");}else{printf("%d\n", sum[r]-sum[l-1]);}}return 0;
}P5638 【CSGRound2】光骓者的荣耀
//前缀和
#include <bits/stdc++.h>
using namespace std;
int n, k;
long long a[1000006], sum[1000006], ans, mx;
int main()
{scanf("%d %d", &n, &k);for(int i=1; i<n; ++i){scanf("%lld", &a[i]);//前缀和, sum[i]表示从1号城市到i+1号城市走高速公路花的时间 //也就是第1条路到第i条路的总时间, 总共有n-1条路 sum[i]=sum[i-1]+a[i];}//不能传送 if(k==0){ans=sum[n-1]; }else if(k>=n-1){ //能直接传送到终点 ans=0;}else{//能传送连续的k条路, 相当于计算连续k条路的最大和mx, //然后用总的时间sum[n-1]减去求得的最大和mx就是答案 //第i条路~第i+k-1条路直接传送了 for(int i=1; i+k-1<n; ++i){
// ans=min(ans, sum[n-1]-(sum[i+k-1]-sum[i-1]));mx=max(mx, sum[i+k-1]-sum[i-1]);} ans=sum[n-1]-mx;}printf("%lld", ans);return 0;
}P3406 海底高铁
#include <bits/stdc++.h>
using namespace std;
int n, m, p[100006], a[100006], b[100006], c[100006];
long long ans, cnt[100006]; //cnt[i]表示第i条铁路走的次数
int main()
{scanf("%d %d", &n, &m);for(int i=1; i<=m; ++i){scanf("%d", &p[i]);}for(int i=1; i<n; ++i){//第i段铁路 可以理解为第i座城市——第i+1座城市之间的铁路 //a[i]表示第i段铁路原始票价//b[i]表示第i段铁路的折扣票价//c[i]表示第i段铁路IC卡的工本费 scanf("%d %d %d", &a[i], &b[i], &c[i]);}//差分//cnt[i]表示第i条铁路走的次数 for(int i=1; i<m; ++i){//p[i]和p[j]表示两座城市的编号 int from=min(p[i], p[i+1]);int to=max(p[i], p[i+1]);//从第from座城市出发到第to座城市, 会经过(第form)~(第to-1)条铁路, 所以前面+1, 后面-1 cnt[from]+=1; cnt[to]-=1;}for(int i=1; i<n; ++i){//前缀和, 求出经过第i条铁路的次数 cnt[i]+=cnt[i-1]; //cnt[0]是0 //总共n-1段铁路, 每一段是买卡还是买票, 取决于：//买卡的钱c[i]+坐的次数*折扣后的票价b[i] 和 坐的次数*原价a[i]的大小关系 if(c[i]+cnt[i]*b[i]<cnt[i]*a[i]){ //买卡便宜 ans+=c[i]+cnt[i]*b[i];}else{ //直接买票便宜 ans+=cnt[i]*a[i];}} printf("%lld", ans);return 0;
}P2367 语文成绩
#include <bits/stdc++.h>
using namespace std;
int n, p, x, y, z, mn=510000000, a[5000008], d[5000008]; //学生分数和增加的分数
int main()
{scanf("%d %d", &n, &p);for(int i=1; i<=n; ++i){scanf("%d", &a[i]);}for(int i=1; i<=p; ++i){scanf("%d %d %d", &x, &y, &z);//区间修改//标记区间两端 d[x]+=z;d[y+1]-=z; }//前缀和 for(int i=1; i<=n; ++i){d[i]=d[i-1]+d[i]; //对差分数组求前缀和 a[i]=a[i]+d[i]; //统一修改 mn=min(mn, a[i]); //比较最值 }printf("%d", mn);return 0;
}P1719 最大加权矩形（二维前缀和）
#include <bits/stdc++.h>
using namespace std;
//d[i][j]是二维前缀和数组, 表示从第一行第一列到第i行第j列形成的矩阵数字之和
int n, a[128][128], d[128][128], mx, cur;
int main()
{scanf("%d", &n);for(int i=1; i<=n; ++i){for(int j=1; j<=n; ++j){scanf("%d", &a[i][j]);}}//计算二维前缀和数组 for(int i=1; i<=n; ++i){ //子矩阵的右下角所在的行 for(int j=1; j<=n; ++j){ //子矩阵的右下角所在的列 d[i][j]=d[i][j-1]+d[i-1][j]-d[i-1][j-1]+a[i][j];}}for(int i=1; i<=n; ++i){ //子矩阵的左上角所在的行 for(int j=1; j<=n; ++j){ //子矩阵的左上角所在的列 //注意k从i开始 for(int k=i; k<=n; ++k){ //子矩阵的右下角所在的行//注意l从j开始for(int l=j; l<=n; ++l){ //子矩阵的右下角所在的列 //计算子矩阵的和cur=d[k][l]-d[k][j-1]-d[i-1][l]+d[i-1][j-1];mx=max(mx, cur);}}}}printf("%d", mx);return 0;
}P2004 领地选择（二维前缀和）
//最大子矩阵简化版
#include <bits/stdc++.h>
using namespace std;
int n, m, c, x, y, ans, a[1006][1006], sum[1006][1006];
int main()
{scanf("%d %d %d", &n, &m, &c);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){sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+a[i][j];}}//设一个擂主 x=1;y=1;ans=sum[c][c];//通过差分求从(i,j)到(i+c-1, j+c-1)的最大矩阵和 for(int i=1; i+c-1<=n; ++i){for(int j=1; j+c-1<=m; ++j){int ii=i+c-1; //右下角横坐标 int jj=j+c-1; //右下角纵坐标 if(sum[ii][jj]-sum[i-1][jj]-sum[ii][j-1]+sum[i-1][j-1] > ans){x=i;y=j;ans=sum[ii][jj]-sum[i-1][jj]-sum[ii][j-1]+sum[i-1][j-1]; }}}printf("%d %d", x, y);return 0;
}P3397 地毯（二维差分前缀和）
//二维差分
#include <bits/stdc++.h>
using namespace std;
int n, m, sum, leftx, lefty, rightx, righty, ans[1002][1002], d[1002][1002];
int main()
{scanf("%d %d", &n, &m); while(m--){scanf("%d %d %d %d", &leftx, &lefty, &rightx, &righty);for(int i=leftx; i<=rightx; ++i){d[i][lefty]+=1;d[i][righty+1]-=1;} }for(int i=1; i<=n+1; ++i){for(int j=1; j<=n+1; ++j){sum+=d[i][j];ans[i][j]=sum;}}for(int i=1; i<=n; ++i){for(int j=1; j<=n; ++j){printf("%d ", ans[i][j]);}printf("\n");}return 0;
}P2822 [NOIP2016 提高组] 组合数问题（组合数+二维前缀和）
#include <bits/stdc++.h>
using namespace std;
long long a[2001][2001];
int n, m, t, k, ans[2001][2001];
int main()
{scanf("%d %d", &t, &k);for(int i=0; i<=2000; ++i){a[i][0]=1;a[i][i]=1;}//杨辉三角计算组合数 for(int i=1; i<=2000; ++i){for(int j=1; j<=i; ++j){a[i][j]=(a[i-1][j-1]+a[i-1][j])%k;}}for(int i=1; i<=2000; ++i){for(int j=1; j<=i; ++j){//前缀和, 上加左、减左上、加自己 ans[i][j]=ans[i-1][j]+ans[i][j-1]-ans[i-1][j-1];if(a[i][j]==0){ans[i][j]++;}}//计算ans[i+1][i+1]时, 会用到ans[i][i+1], 由于前面没计算 ans[i][i+1]=ans[i][i];}while(t--){scanf("%d %d", &n, &m);if(m>n){printf("%d\n", ans[n][n]); }else{printf("%d\n", ans[n][m]); }}return 0;
}P2280 [HNOI2003]激光炸弹
处理边界的一种方法
#include <bits/stdc++.h>
using namespace std;
int n, m, x, y, v, asd[5010][5010], cur, ans;
int main()
{scanf("%d %d", &n, &m);for(int i=1; i<=n; ++i){scanf("%d %d %d", &x, &y, &v);asd[x+1][y+1]=v;}for(int i=1; i<=5001; ++i){for(int j=1; j<=5001; ++j){asd[i][j]=asd[i][j-1]+asd[i-1][j]-asd[i-1][j-1]+asd[i][j];}}for(int i=1; i+m-1<=5001; ++i){for(int j=1; j+m-1<=5001; ++j){int xx=i+m-1;int yy=j+m-1;cur=asd[xx][yy]-asd[xx][j-1]-asd[i-1][yy]+asd[i-1][j-1];ans=max(ans, cur);}}printf("%d", ans);return 0;
}处理边界的另一种方法
#include <bits/stdc++.h>
using namespace std;
int n, m, x, y, v, cur, ans, asd[5010][5010];
int main()
{scanf("%d %d", &n, &m);for(int i=1; i<=n; ++i){scanf("%d %d %d", &x, &y, &v);asd[x+1][y+1]=v;}for(int i=1; i<=5001; ++i){for(int j=1; j<=5001; ++j){asd[i][j]=asd[i][j-1]+asd[i-1][j]-asd[i-1][j-1]+asd[i][j];}}for(int i=m; i<=5001; ++i){for(int j=m; j<=5001; ++j){int starti=i-m+1;int startj=j-m+1;cur=asd[i][j]-asd[i][startj-1]-asd[starti-1][j]+asd[starti-1][startj-1];ans=max(ans, cur);}}printf("%d", ans);return 0;
}P3131 [USACO16JAN]Subsequences Summing to Sevens S
（前缀和思维题）
#include <bits/stdc++.h>
using namespace std;
const int N=50010;
int n, a[N], sum[N], l[7], r[7], ans;
int main()
{scanf("%d", &n);for(int i=1; i<=n; ++i){scanf("%d", &a[i]);sum[i]=(sum[i-1]+a[i])%7;if(!l[sum[i]]){ //第一次出现这个余数, l[sum[i]]=i; //记录第一次出现的下标 }r[sum[i]]=i; //记录最后一次出现的下标 }for(int i=1; i<=6; ++i){ans=max(ans, r[i]-l[i]); //如果没答案, 则ans为0 }ans=max(ans, r[0]);printf("%d", ans);return 0;
}这篇关于差分、前缀和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
