Segment Tree

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;
#define siz 1000005
int a[siz],t[siz];
int n,m,sqrtN;
char as[siz];
void reset(){
    for(int i=0;i<=m;i++) t[i]=0;
}
void build(int v, int tl, int tr){
    if(tl==tr) t[v]=a[tl];
    else{
        int tm=(tl+tr)/2;
        build(2*v,tl,tm);
        build(2*v+1,tm+1,tr);
        t[v]=t[v*2]+t[v*2+1];
    }
}

int sum(int v, int tl, int tr, int l, int r){
    if(l>r) return 0;
    if(l==tl&&r==tr) return t[v];
    int tm=(tl+tr)/2;
    return sum(2*v,tl,tm,l,min(r,tm))+sum(2*v+1,tm+1,tr,max(l,tm+1),r);
}

void updateAdd(int v, int tl, int tr, int pos, int new_val){
    if(tl==tr) t[v]+=new_val ;
    else{
        int tm=(tl+tr)/2;
        if(pos<=tm) updateAdd(2*v,tl,tm,pos,new_val);
        else updateAdd(2*v+1,tm+1,tr,pos,new_val);
        t[v]=t[2*v]+t[2*v+1];
    }
}
void updateSub(int v, int tl, int tr, int pos, int new_val){
    if(tl==tr) t[v]-=new_val ;
    else{
        int tm=(tl+tr)/2;
        if(pos<=tm) updateSub(2*v,tl,tm,pos,new_val);
        else updateSub(2*v+1,tm+1,tr,pos,new_val);
        t[v]=t[2*v]+t[2*v+1];
    }
}
int main()
{
    int x,y,k=1;
    //freopen("input.txt","r",stdin);
    scanf("%d",&n);
    for(int t=0;t<n;t++){
        scanf("%d",&m);
        sqrtN=(int)sqrt((double)m);
        reset();
        for(int i=1;i<=m;i++) scanf("%d",&a[i]);
        build(1,1,m);
        printf("Case %d:\n",k++);
        while(scanf("%s",&as)==1){
            if(strcmp(as,"End")==0) break;
            else if(strcmp(as,"Query")==0){
                scanf("%d%d",&x,&y);
                printf("%d\n",sum(1,1,m,x,y));
            }
            else if(strcmp(as,"Add")==0){
                scanf("%d%d",&x,&y);
                updateAdd(1,1,m,x,y);
            }
            else if(strcmp(as,"Sub")==0){
                scanf("%d%d",&x,&y);
                updateSub(1,1,m,x,y);
            }
        }
    }
    return 0;
}