线段树求助
查看原帖
线段树求助
521890
上帝之鹰楼主2022/3/13 20:32
#include<iostream>
using namespace std;
int m,n,x,y,k;
int a[100005],num[400005],addv[400005];
void pushdown(int o,int L,int R){
	int mid=(L+R)/2;
	addv[o*2]+=addv[o];
	num[o*2]+=addv[o]*(L-mid+1);
	addv[o*2+1]+=addv[o];
	num[o*2+1]+=addv[o]*(mid-R+2);
	addv[o]=0;
}
void build(int o,int L,int R){
	addv[o]=0;
	if(L==R){
		num[o]=a[L];
		return;
	}
	int mid=(L+R)/2;
	build(o*2,L,mid);
	build(o*2+1,mid+1,R);
	num[o]=num[o*2]+num[o*2+1];
}
void update(int o,int L,int R){
	if(L>=x&&R<=y){
		addv[o]+=k;
		num[o]+=(R-L+1)*k;
		return;
	}
	int mid=(L+R)/2;
	pushdown(o,L,R);
	if(x<=L)
		update(o*2,L,mid);
	if(R<y)
		update(o*2+1,mid+1,R);
	num[o]=num[o*2]+num[o*2+1];
}
int query(int o,int L,int R){
	if(x<=L&&R<=y){
		return num[o];
	}
	int mid=(L+R)/2;
	pushdown(o,L,R);
	if(x<=mid){
		return query(o*2,L,mid);
	}
	if(y>mid){
		return query(o*2+1,mid+1,R);
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;++i){
		cin>>a[i];
	}
	build(1,1,n);
	int eq;
	for(int i=0;i<m;++i){
		cin>>eq;
		if(eq==1){
			cin>>x>>y>>k;
			update(1,1,n);
		}
		else{
			cin>>x;
			y=x;
			cout<<query(1,1,n)<<endl;
		}
	}
	return 0;
}
2022/3/13 20:32
加载中...