【算法笔记】前缀和，多维前缀和，一维差分

(1) 前缀和

a. 前缀和的作用：

快速的求一段元素的和。s[i]=s[i-1]+a[i];

如果是求[l,r]之间的数字的和，应该是s[r]-s[l-1];也就是可以用一次运算求出任意区间内的元素的和。

例题：ACwing 795

#include<iostream>
using namespace std;
int n;
int m;
const int N=100010;
int q[N];
int S[N];
int main(){
    scanf("%d%d",&n,&m);
    
    for(int i=1;i<n+1;++i){
        
        scanf("%d",&q[i]);
    }
    
    S[0]=0;
    
    for(int i=1;i<n+1;++i){
        
        S[i]=S[i-1]+q[i];
//        cout<<"此时的S"<<S[i]<<endl;
    }
    while(m--){
        
        int l,r;
        scanf("%d%d",&l,&r);
        cout<<S[r]-S[l-1]<<endl;
        
    }
    return 0;
}

（2） 多维前缀和

求和：设当前点位ij，要求的区域为（x1,y1)到（x2,y2)范围内的小方块的内容的和。求和公式为：S[x2] [y2] -S[x2] [y1-1] -S[x1-1] [y2] +S[x1-1] [y1-1]

如何更新S[i] [j] ?

S[i] [j] = S[i-1] [j] + S[i] [j-1] -S[i-1] [j-1] +a[i] [j]

#include<iostream>
using namespace std;
const int N=1010;
int q[N][N];
int s[N][N];
int main(){
	int m;
	int n;
	int p;
	scanf("%d%d%d",&m,&n,&p);
	for(int i=1;i<=m;++i){
		for(int j=1;j<=n;++j){
			scanf("%d",&q[i][j]);
		}
	}
	
	for(int i=1;i<=m;++i){
		for(int j=1;j<=n;++j){
			s[i][j]=s[i-1][j]+s[i][j-1]+q[i][j]-s[i-1][j-1];
		}
	}
	while(p--){
		int x1,y1,x2,y2;
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		cout<<s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]<<endl;
		
	}
	return 0;
} 

(3) 差分

构造 b1,b2…bn使得

a[i]=b1+b2+…+b[i]

则：b数组就是a数组的差分，a数组就是b数组的前缀和。所以我们能知道，差分和前缀和是逆运算的关系。

b[1]=a[1]

b[2]=a[2]-a[1]

b[3]=a[3]-a[2]

b[n]=a[n]-a[n-1]

a. 差分的作用

当我们需要在a数组中，某个区间范围内的所有数据全都加上c的时候。（比如区间是(l,r))原本需要o(n)的时间复杂度才能完成的事情。如果利用差分，只需要将b[l]+c,b[r+1]-c 就能做到最终的效果。实现了o(1)的数量级。

注意：在构造初始数组b的时候，我们假设a和b初始的时候都是全0，把a看作n次插入，对于a[i]而言，每次插入都相当于对a从（i,i）的区间内插入了a[i]这个值。这就构造出了原始的差分数组b，这一步非常巧妙！

例题：ACwing797

#include<iostream>
using namespace std;

const int N=100010;
int a[N];
int b[N];
void insert_(int l,int r,int c){
	b[l]+=c;
	b[r+1]-=c;
}
int main(){
	int m,n;
	scanf("%d%d",&m,&n);
	for(int i=1;i<=m;++i){
		scanf("%d",&a[i]);
		insert_(i,i,a[i]);
	}
	for(int i=0;i<n;++i){
		int l;
		int r;
		int c;
		scanf("%d%d%d",&l,&r,&c);
		insert_(l,r,c);
	}
	
	for(int i=1;i<=m;++i)b[i]+=b[i-1];
	for(int i=1;i<=m;++i)cout<<b[i]<<" ";
	return 0;
}

最后

以上就是机灵小伙最近收集整理的关于【算法笔记】前缀和，多维前缀和，一维差分的全部内容，更多相关【算法笔记】前缀和内容请搜索靠谱客的其他文章。