1.前缀和
一维数组
#include<iostream> using namespace std; const int N=1e5+10; int main() { int n,m,a[N],sum[N]={0}; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); sum[i]=sum[i-1]+a[i]; } while(m--) { int l,r; scanf("%d%d",&l,&r); printf("%d\n",sum[r]-sum[l-1]); } }
二维数组
#include<iostream> using namespace std; const int N=1010; int main() { int n,m,q,a[N][N],sum[N][N]={0}; 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++) { sum[i][j]=sum[i][j-1]+sum[i-1][j]+a[i][j]-sum[i-1][j-1]; } } while(q--) { int x1,y1,x2,y2; cin>>x1>>y1>>x2>>y2; cout<<sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1]<<endl; } }
2.差分
(前缀和的逆运算)
一维数组
数组a[ ]:a[0],a[1],a[2],a[3],a[4]; 构造数组b[ ]:b[0],b[1],b[2],b[3],b[4];
a是b的前缀和数组,a[i]=b[0]+b[1]+...+b[i];
所以b[0]=a[0]; b[1]=a[1]-a[0]; b[2]=a[2]-a[1];
输入一个长度为 n 的整数序列。
接下来输入 m 个操作,每个操作包含三个整数 l,r,c 表示将序列中 [l,r] 之间的每个数加上 c。
请你输出进行完所有操作后的序列。
#include<iostream> using namespace std; const int N=1e5+10; int main() { int n,m,a[N],b[N]={0},c[N]={0}; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); b[i]=a[i]-a[i-1]; } while(m--) { int l,r,c; scanf("%d%d%d",&l,&r,&c); b[l]+=c;b[r+1]-=c; } for(int i=1;i<=n;i++) { c[i]=b[i]+c[i-1]; printf("%d ",c[i]); } }
二维数组
#include<iostream> using namespace std; const int N=1010; int main() { int n,m,q,a[N][N],b[N][N]={0}; 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++) { b[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]; } } int x1,y1,x2,y2,c; while(q--) { cin>>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; } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+b[i][j]; cout<<a[i][j]<<" "; }cout<<endl; } }