AOJ Range Query - Range Sum Query

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B
会津大学オンラインジャッジ問ＤＳＬ２Ｂ
データの変更と集計クエリに高速に答える問題。

もちろん、クエリごとに線形で集計していたら答えは出ない。
セグメント木で分割して集計したものをさらに集計するというひと手間が必要。

実は細部は直感で書いてるので理論面ではちょっと曖昧な部分があります。
色々なテストデータを用意して全部うまくいったからこれでいけるだろという感じで合格しました。


#include<stdio.h>
#include<map>
#include<algorithm>

const int LIMIT=262144;
const int FIRST=LIMIT/2;
int A[LIMIT];

void set(int p){
      if(p==0)return ;
      A[p]=0;
      set(p/2);
}


void dellAndSet(int p){
      if(p==0)return ;
      int a=0,b=0;
      if(p*2<LIMIT){
            a=A[p*2];
      }
      if(p*2+1<LIMIT){
            b=A[p*2+1];
      }
      A[p]=a+b;
      dellAndSet(p/2);
}

int sum(int x,int y,int p,int L,int R){
      if(x>y)return 0;
      int M=(L+R)/2;
      if(L==x){
            M=R;
            while(y<M){
                  p*=2;
                  M = (L+M)/2;
            }
            int a=A[p];
            int b;
            b=sum(M+1,y,1,0,FIRST-1);
            //printf("(%d %d %d)<%d %d %d %d %d>",a,b,p,L,M,R,x,y);
            return a+b;
      }
           
     
      if(M<x){
            return sum(x,y,p*2+1,M+1,R);
      }else if(x<=M){
            return sum(x,y,p*2,L,M);
      }

      return -10000;//おかしな処理の検出
}
int main(){
      int n,q,com,x,y;
      scanf("%d %d",&n,&q);
      for(int i=0;i<FIRST;i++){
            set(FIRST+i);
      }
     
      for(int i=0;i<q;i++){
            scanf("%d %d %d",&com,&x,&y);
            if(com==0){
                  A[x+FIRST]+=y;
                  dellAndSet((x+FIRST)/2);
            }else{
                  printf("%d\n",sum(x,y,1,0,FIRST-1));
            }
      }
}