LOJ 1112 seg

#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;

#define Max 2000009
#define read()             freopen("input.txt", "r", stdin)
#define write()            freopen("output.txt", "w", stdout)

int tree[Max],arr[Max];

void fastIO()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

void BuildTree(int node,int L,int R)
{
    if(L==R){
        tree[node] = arr[L];
        return;
    }
    int mid = (L+R)/2;
    int Left = 2*node;
    int Right = Left+1;
    BuildTree(Left,L,mid);
    BuildTree(Right,mid+1,R);
    tree[node] = tree[Left] + tree[Right];
}

void UpdateTree(int node,int L,int R,int index,int val)
{
    if(L==index && R==index){
        tree[node]=tree[node]+val;
        return;
    }
    if(L>index || R<index) return;
    int mid = (L+R)/2;
    int Left = 2*node;
    int Right = Left+1;
    UpdateTree(Left,L,mid,index,val);
    UpdateTree(Right,mid+1,R,index,val);
    tree[node] = tree[Left] + tree[Right];
}

void UpdateZero(int node,int L,int R,int index)
{
    if(L==index && R==index){
        printf("%d\n",tree[node]);
        tree[node]=0;
        return;
    }
    if(L>index || R<index) return;
    int mid = (L+R)/2;
    int Left = 2*node;
    int Right = Left+1;
    UpdateZero(Left,L,mid,index);
    UpdateZero(Right,mid+1,R,index);
    tree[node] = tree[Left] + tree[Right];
}

int RangeSum(int node,int L,int R,int x,int y)
{
    if(L>=x && R<=y){
        return tree[node];
    }
    if(L>y || R<x) return 0;
    int mid = (L+R)/2;
    int Left = 2*node;
    int Right = Left+1;
    int sum1 = RangeSum(Left,L,mid,x,y);
    int sum2 = RangeSum(Right,mid+1,R,x,y);
    return sum1+sum2;
}

int main()
{
    //read();
    //write();
    //fastIO();
    int t;
    scanf("%d",&t);
    for(int i=1;i<=t;i++){
        int n,q;
        scanf("%d %d",&n,&q);
        for(int j=1;j<=n;j++){
            scanf("%d",&arr[j]);
        }
        BuildTree(1,1,n);
        printf("Case %d:\n",i);
        while(q--){
            int x,l,r;
            scanf("%d",&x);
            if(x==1){
                scanf("%d",&l);
                UpdateZero(1,1,n,l+1);
            }
            else{
                scanf("%d %d",&l,&r);
                if(x==2){
                    UpdateTree(1,1,n,l+1,r);
                }
                else{
                    printf("%d\n",RangeSum(1,1,n,l+1,r+1));
                }
            }
        }
    }
    return 0;
}