前缀和、差分

前言

对于一个普通的数组而言，求区间和效率----O(n)；区间修改效率----O(n)；单点修改效率----O(1)

为了更方便地进行区间操作，我们需要构造前后缀数组。

前缀和

前缀和指的是用使用一个数组表示另一个数组1-i下标的和。

例如：int arr[n]，Prefix[i] 表示 1-i 的arr[i]的和

前缀和数组：求区间和效率----O(1)；区间修改效率----O(n)；单点修改效率----O(n)

• 前缀和数组的思想也可以拓展到求 数组 1-i 下标的最大值/最小值
• 求后缀数组和求前缀数组是相同操作

例题1：最大数组和

1.最大数组和 - 蓝桥云课 (lanqiao.cn)

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAX = 1e6;

ll t,n,k;
ll a[MAX];
ll leftsum[MAX],rightsum[MAX];

int main(void){
	cin>>t;
	while(t--){
		cin>>n>>k;
		memset(leftsum,0,sizeof(leftsum));
		memset(rightsum,0,sizeof(rightsum));
		memset(a,0,sizeof(a));
		ll total = 0;
		for(int i = 1 ; i <= n ; i ++){
			cin>>a[i];
			total += a[i];
		}
		sort(a+1,a+n+1);
		for(int i = 1 ; i <= n ; i ++){
			if(i == 1){
				leftsum[i] = a[i];
			}
			else leftsum[i] = leftsum[i-1] + a[i];
		}
		for(int i = n ; i >= 1 ; i --){
			if(i == n){
				rightsum[i] = a[i];
			}
			else rightsum[i] = rightsum[i+1] + a[i];
		}
		ll ans = LONG_LONG_MIN;
		for(int i = 0 ; i <= k ; i ++){
			int j = k - i;
			ans = max(ans,total - leftsum[2*i] - rightsum[n+1-j]);
		}
		cout<<ans<<endl;
	}
	return 0;
}

例题2：大石头的搬运工

1.大石头的搬运工 - 蓝桥云课 (lanqiao.cn)

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAX = 1e6 + 10;

int n;
ll Left[MAX];
ll Right[MAX];

struct rock{
	int w;
	int p;
	bool operator<(const rock & rhs){
		if(w != rhs.w) return p < rhs.p;
		else return w < rhs.w;
	}
}r[MAX];

void make_prefix(void){
	ll s = 0;
	for(int i = 0 ; i < n ; i ++){
		if(i > 0) Left[i] = Left[i-1] + s*(r[i].p - r[i-1].p);
		s += r[i].w;
	}
	s = 0;
	for(int i = n-1 ; i >= 0 ; i --){
		if(i < n-1) Right[i] = Right[i+1] + s*(r[i+1].p - r[i].p);
		s += r[i].w;
	}
}

int main(void){
	cin>>n;
	for(int i = 0 ; i < n ; i ++){
		int x,y;cin>>x>>y;
		r[i].w = x;
		r[i].p = y;
	}
	sort(r,r+n);
	make_prefix();
	ll min_ = LONG_LONG_MAX;
	for(int i = 0 ; i < n ; i ++){
		min_ = min(min_,Left[i]+Right[i]);
	}
	cout<<min_;
	return 0;
}

例题3：四元组问题

----单调栈+前缀和

----单调栈可以用来求1-i的 最大 和 次大

1.四元组问题 - 蓝桥云课 (lanqiao.cn)

#include<bits/stdc++.h>
using namespace std;
const int MAX = 1e6;

int n;
int a[MAX],min_[MAX];
stack<int > st;

int main(void){
	cin>>n;
	for(int i = 0 ; i < n ; i ++){
		cin>>a[i];
	}
	min_[n-1] = a[n-1];
	for(int i = n ; i >= 0 ; i --){
		min_[i] = (min_[i+1],a[i]);
	}
	int A = -999;
	for(int i = 0 ; i < n-1 ; i ++){
		//判断是否符合最终条件
		if(A > a[i] && a[i] > min_[i+1]){ // A > C > D ,利用后缀最小值,求出三等于关系
			cout<<"YES"<<endl;
			return 0;
		}
		//对A和B值的更新
        //如果出现一个新的最大值，上次的最大值就会被弹出并保存，也就是次大
        //但这里a[i]不是B的值，我们并不记录B的值，因为后续比较A、C、D无需使用
		while(!st.empty() && st.top() < a[i]){ // B > A ,利用单调栈求出最大和次大
			A = max(st.top(),A);
			st.pop();
		}
		st.push(a[i]);
	}
	cout<<"NO"<<endl;
	return 0;
}

差分

差分数组就是用一个数组表示另一个数据的相邻差，以便进行区间修改操作。

差分数组的 前缀和 就是 原数组。

在需要恢复原数组时，需要求差分数组求前缀和。

前缀和数组：

1）求区间和效率----O(2*n)

2）区间修改效率----O(1)

3）单点修改效率----O(n)

例题1：肖恩的投球游戏

2.肖恩的投球游戏 - 蓝桥云课 (lanqiao.cn)

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAX = 1e5 + 10;

ll diff[MAX];
ll arr[MAX];
ll n,q;

int main(void){
	cin>>n>>q;
	for(int i = 1 ; i <= n ; i ++){ //从1开始，arr[0] == 0
		cin>>arr[i];
	}
	for(int i = 1 ; i <= n ; i ++){//生成差分数组
		diff[i] = arr[i] - arr[i-1];
	}
	while(q--){  //区间修改
		ll l,r,m;cin>>l>>r>>m;
		diff[l] += m;
		diff[r+1] -= m;
	}
	for(int i = 1 ; i <= n ; i ++){ //数组还原
		diff[i] += diff[i-1];
	}
	for(int i = 1 ; i <= n ; i ++){
		cout<<diff[i]<<" ";
	}
	return 0;
}

例题2：泡澡

1.泡澡 - 蓝桥云课 (lanqiao.cn)

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAX = 1e6;
const int N = 2*(1e5) + 10;
ll arr[MAX];
ll diff[MAX];
ll n,max_water,rside,lside;

int main(void){
	cin>>n>>max_water;
	memset(arr,0,sizeof(arr));
	while(n--){
		ll l,r,w;
		cin>>l>>r>>w;
        //注意：本题的区间是[l，r)
		diff[l] += w;
		diff[r] -= w; 
	}
	for(int i = 1 ; i <= N ; i ++){
		diff[i] += diff[i-1]; //恢复原数组
		if(diff[i] > max_water){
			cout<<"No";
			return 0;
		}
	}
	cout<<"Yes";
	return 0;
}

二维差分

主要用来进行二维数组的正方形区间修改操作，可优化时间复杂度为O(1)

二维差分数组的定义是：

diff[i][j] = arr[i][j] - arr[i-1][j] - arr[i][j-1] + arr[i-1][j-1];
//主对角线两点 - 副对角线两点

二维前缀和数组的定义是：

sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + sum[i][j];
//借此用差分数组恢复原数组
diff[i][j] = diff[i-1][j] + diff[i][j-1] - diff[i-1][j-1] + diff[i][j];

例题1：地毯

P3397 地毯 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAX = 1e3 + 10;

ll arr[MAX][MAX];
ll diff[MAX][MAX];
ll n,t;

int main(void){
	memset(arr,0,sizeof(arr));
	memset(diff,0,sizeof(diff));
	cin>>n>>t;
	while(t--){
		ll x1,x2,y1,y2;
		cin>>x1>>y1>>x2>>y2;
        //主对角线两点++
		diff[x1][y1] ++;
		diff[x2+1][y2+1] ++;
		//副对角线两点--
        diff[x2+1][y1] --;
		diff[x1][y2+1] --;
	}
	for(int i = 1 ; i <= n ; i ++){
		for(int j = 1 ; j <= n ; j ++){
            //数组还原公式
			arr[i][j] = arr[i-1][j] + arr[i][j-1] - arr[i-1][j-1] + diff[i][j];
		}
	}
	for(int i = 1 ; i <= n ; i ++){
		for(int j = 1 ; j <= n ; j ++){
			cout<<arr[i][j]<<" ";
		}
		cout<<"\n";
	}
	return 0;
}

例题2：肖恩的投球游戏（加强版）

竞赛中心 - 蓝桥云课 (lanqiao.cn)

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAX = 1e3 + 10;

ll diff[MAX][MAX];
ll arr[MAX][MAX];
ll n,m,t;

int main(void){
	cin>>n>>m>>t;
	for(int i = 1 ; i <= n ; i ++){
		for(int j = 1 ; j <= m ; j ++){
			cin>>arr[i][j];
		}
	} //输入原数组
	for(int i = 1 ; i <= n ; i ++){
		for(int j = 1 ; j <= m ; j ++){
			diff[i][j] = arr[i][j] - arr[i-1][j] - arr[i][j-1] + arr[i-1][j-1];
		}
	} //构造二维差分数组
	while(t--){ //区域增减操作
		ll x1,y1,x2,y2,v;
		cin>>x1>>y1>>x2>>y2>>v;
		diff[x1][y1] += v;
		diff[x2+1][y2+1] += v;
		diff[x1][y2+1] -= v;
		diff[x2+1][y1] -= v;
	}
	for(int i = 1 ; i <= n ; i ++){ //二维差分求前缀和，得到修改后的数组
		for(int j = 1 ; j <= m ; j ++){
			diff[i][j] = diff[i-1][j] + diff[i][j-1] - diff[i-1][j-1] + diff[i][j];
			cout<<diff[i][j]<<" ";
		}
		cout<<endl;
	}
	return 0;
}