树状数组用线段树来写-526互联

#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;
}