Robin Hood

#include<bits/stdc++.h>
using namespace std;
#define LL long long
void build(LL int ar[],LL int seg[],LL int node,LL int b,LL int e){
    if(b==e){
        seg[node]=ar[b];
        return;
    }
    LL int Left=node*2+1;
    LL int Right=node*2+2;
    LL int mid=(b+e)/2;
    build(ar,seg,Left,b,mid);
    build(ar,seg,Right,mid+1,e);
    seg[node]=seg[Left]+seg[Right];
}
LL int query(LL int seg[],LL int node,LL int b,LL int e,LL int i,LL int j){
    if(i>e||j<b) return 0;
    if(b>=i&&e<=j) return seg[node];
    LL int Left=node*2+1;
    LL int Right=node*2+2;
    LL int mid=(b+e)/2;
    return query(seg,Left,b,mid,i,j)+query(seg,Right,mid+1,e,i,j);
}
void update(LL int seg[],LL int node,LL int b,LL int e,LL int i,LL int newvalue){
    if(i>e||i<b)return;
    if(b>=i&&e<=i){
        seg[node]=newvalue;
        return;
    }
    LL int Left=node*2+1;
    LL int Right=node*2+2;
    LL int mid=(b+e)/2;
    update(seg,Left,b,mid,i,newvalue);
    update(seg,Right,mid+1,e,i,newvalue);
    seg[node]=seg[Left]+seg[Right];
}
LL int a[1<<20];
LL int seg[1<<19];
int  main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int  t;
    scanf("%d",&t);
    for(int i=1;i<=t;i++){
        printf("Case %d:\n",i);
        LL int  n,q;
        scanf("%lld%lld",&n,&q);
        for(int j=0;j<n;j++){
            scanf("%lld",&a[j]);
        }
        build(a,seg,0,0,n-1);
        for(int j=0;j<q;j++){
            LL int t1,ii,jj;
            scanf("%lld",&t1);
            if(t1==1){
                scanf("%lld",&ii);
                printf("%lld\n",a[ii]);
                update(seg,0,0,n-1,ii,0);
                a[ii]=0;
            }
            else if(t1==2){
                scanf("%lld%lld",&ii,&jj);
                update(seg,0,0,n-1,ii,jj+a[ii]);
                a[ii]+=jj;
            }
            else{
                scanf("%lld%lld",&ii,&jj);
                printf("%lld\n",query(seg,0,0,n-1,ii,jj));
            }
        }
    }
}