前缀和

一维前缀和

前缀和数组

d[i]=d[i-1]+a[i];

前缀和公式

sum=a[r]-a[l-1];

模版

#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
int n,m,a[100005],x,y,d[100005];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        d[i]=d[i-1]+a[i];
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        printf("%d\n",d[y]-d[x-1]);
    }
    return 0;
}

二维前缀和

区间和公式

sum[xb][yb]-sum[xa-1][yb]-sum[xb][ya-1]+sum[xa-1][ya-1];

前缀和公式

sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];

模版

#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
int n,m,k,a[1005][1005],sum[1005][1005],xa,ya,xb,yb;
int main(){
	scanf("%d%d%d",&n,&m,&k);
	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-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
		}
	}
	for(int i=1;i<=k;i++){
		scanf("%d%d%d%d",&xa,&ya,&xb,&yb);
		printf("%d\n",sum[xb][yb]-sum[xa-1][yb]-sum[xb][ya-1]+sum[xa-1][ya-1]);
	}
    return 0;
}

差分

一维差分

数组

d[i]=a[i]-a[i-1];

公式

a[l]+=x;
a[r+1]-=x;

模版

#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
int n,m,a[100005],l,r,x,sum[100005];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		sum[i]=a[i]-a[i-1];
	}
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&l,&r,&x);
		sum[l]+=x;
		sum[r+1]-=x;
	}
	for(int i=1;i<=n;i++){
		sum[i]+=sum[i-1];
		printf("%d ",sum[i]);
	}
    return 0;
}

二维差分

公式

sum[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1];//求差分 
sum[xa][ya]+=c;
sum[xa][yb+1]-=c;
sum[xb+1][ya]-=c;
sum[xb+1][yb+1]+=c;
//对于每次操作 

模版

#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
int n,m,q,xa,ya,xb,yb,c,a[1005][1005],sum[1005][1005],ans[1005][1005];
int main(){
	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]);
			sum[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1];
		}
	}
	for(int i=1;i<=q;i++){
		scanf("%d%d%d%d%d",&xa,&ya,&xb,&yb,&c);
		sum[xa][ya]+=c;
		sum[xa][yb+1]-=c;
		sum[xb+1][ya]-=c;
		sum[xb+1][yb+1]+=c;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			ans[i][j]=ans[i-1][j]+ans[i][j-1]-ans[i-1][j-1]+sum[i][j];
			printf("%d ",ans[i][j]);
		}
		printf("\n");
	}
    return 0;
}