萌新刚学OI,线段树求调
查看原帖
萌新刚学OI,线段树求调
682028
_awa_keyai楼主2022/8/24 20:04
#include<bits/stdc++.h>

using namespace std;

const int maxn=5e5+10;
int n,m;
struct TREE{
	int l,r,num;
}tree[maxn*4];
int input[maxn];

inline void init(int i,int l,int r){
	tree[i].l=l;tree[i].r=r;
	tree[i].num=0;
	if(tree[i].l==tree[i].r){
		return;
	}
 
	int mid=(l+r)/2;
	init(i*2,l,mid);
	init(i*2+1,mid+1,r);
}

inline void revise_line(int i,int l,int r,int k){
	if(tree[i].l>=l && tree[i].r<=r){
		tree[i].num+=k;
		return;
	}
	if(tree[i*2].r>=l) revise_line(i*2,l,r,k);
	if(tree[i*2+1].l<=r) revise_line(i*2+1,l,r,k); 
//	tree[i].num=tree[i*2].num+tree[i*2+1].num;
}

inline int search_dot(int i,int dis){
//	ans+=tree[i].num; 
	if(tree[i].l==tree[i].r){
		return tree[i].num;
//		return;
	}
	
	int s=0;
	if(dis<=tree[i*2].r) s+=search_dot(i*2,dis);
	if(dis>=tree[i*2+1].l) s+=search_dot(i*2+1,dis);
	return s;
}

int main(){
	
	cin>>n>>m;
	
	for(int i=1;i<=n;i++){
		cin>>input[i];
	}
	
	init(1,1,n);
	for(int i=1;i<=m;i++){
		int t,a,b,c;
		cin>>t;
		if(t==1){
			cin>>a>>b>>c;
			//区间修改 
			revise_line(1,a,b,c); 
		} else {
			//单点查询
			cin>>a; 
			cout<<search_dot(1,a)+input[a]<<endl;
		}
	}
	
	return 0;
}
2022/8/24 20:04
加载中...