1112 - Curious Robin Hood

#include<bits/stdc++.h>
using namespace std;
long long arry[100010],segment[400050];
 
void build(long long at, long long L, long long R)
{
    if(L==R)
    {
        segment[at] = arry[L];
        return;
    }
    long long mid = (L+R)/2;
    build(at*2,L,mid);
    build(at*2+1,mid+1,R);
    segment[at] = segment[at*2] + segment[at*2+1];
}
 
void update(long long at, long long L, long long R, long long pos, long long u)
{
    if(L==R)
    {
        segment[at] += u;
        return;
    }
    long long mid = (L+R)/2;
    if(pos <= mid)
        update(at*2,L,mid,pos,u);
    else
        update(at*2+1,mid+1,R,pos,u);
    segment[at] = segment[at*2]+segment[at*2+1];
}
 
long long query(long long at,long long L, long long R, long long l, long long r)
{
    if(r<L || l>R)
        return 0;
    if(L==R)
        return segment[at];
    if(l <= L && r >= R)
        return segment[at];
    long long mid = (L+R)/2;
    long long x = query(at*2, L, mid, l, r);
    long long y = query(at*2+1, mid+1, R, l, r);
    return x + y;
}
 
int main()
{
    //freopen("T - Curious Robin Hood.txt","r",stdin);
    long long T,n,q,a,b,i,c=1;
    scanf("%lld", &T);
    while(T--)
    {
        scanf("%lld %lld", &n, &q);
        for(i=1; i<=n; i++)
            scanf("%lld", &arry[i]);
 
        build(1,1,n);
        printf("Case %lld:\n",c++);
        for(i=1; i<=q; i++)
        {
            scanf("%lld",&a);
            if(a==1)
            {
                scanf("%lld",&b);
                update(1,1,n,b+1,-arry[b+1]);
                printf("%lld\n",arry[b+1]);
                arry[b+1] = 0;
            }
            else if(a==2)
            {
                scanf("%lld %lld",&a,&b);
                update(1,1,n,a+1,b);
                arry[a+1] += b;
            }
            else
            {
                scanf("%lld %lld", &a, &b);
                printf("%lld\n",query(1,1,n,a+1,b+1));
            }
        }
    }
    return 0;
}