用线段树来接树状数组类的问题

大致解决的问题就是区间查询以及单点的修改

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+10;
int a[N],tag[N<<2];
struct{
	struct{
		int l,r,sum;
	}tr[N<<2];
	
	void push_up(int i){
		tr[i].sum = tr[i<<1].sum+tr[i<<1|1].sum;
	}
	void build(int i,int l,int r){
		tr[i].l= l;
		tr[i].r= r;
		if(l==r){
			tr[i].sum = a[l];
			return;
		}
		int mid=(l+r)>>1;
		build(i<<1,l,mid);
		build(i<<1|1,mid+1,r);
		push_up(i);
	}
	void add(int i,int l,int r,int k){
	    tag[i]+=k;
	    tr[i].sum+=(r-l+1)*k;
	}
	void push_down(int i,int l,int r){
		if(tag[i]){
			int mid=(l+r)>>1;
			add(i<<1,l,mid,tag[i]);
			add(i<<1|1,mid+1,r,tag[i]);
			tag[i]=0;
		}
	}
	void updata(int i,int l,int r,int L,int R,int k){
		if(L>=l&&R<=r){
			add(i,L,R,k);
			return;
		}
		push_down(i,L,R);
		int mid=(L+R)>>1;
		if(l<=mid){
			updata(i<<1,l,r,L,mid,k);
		}
		if(r>mid){
			updata(i<<1|1,l,r,mid+1,R,k);
		}
		push_up(i);
	}
	int query(int i,int l,int r,int L,int R){
		if(l<=L&&r>=R){
			return tr[i].sum;
		}
		push_down(i,L,R);
		int ans=0;
		int mid=(L+R)>>1;
	    if(l<=mid)ans+=query(i<<1,l,r,L,mid);
	    if(r>=mid+1)ans+=query(i<<1|1,l,r,mid+1,R);
	    return ans;
	}
}ST;
signed main(){
	int n,q;
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	ST.build(1,1,n);
	for(int i=1;i<=q;i++){
		int x;
		cin>>x;
		if(x==1){
			int y,z,k;
			cin>>y>>z>>k;
			ST.updata(1,y,z,1,n,k);
		}else{
			int y;
			cin>>y;
			int ans=ST.query(1,y,y,1,n);
			cout<<ans<<"\n";
		}
	}
	return 0;
}