DSL_2_B Range Sum Query (RSQ)

問題
Range Sum Query | データ構造ライブラリ | Aizu Online Judge

前回のRMQとほぼ同じ感じで解けそうだったので、すぐに取り掛かってみました。

kujira16.hateblo.jp

#include<stdio.h>
#include<math.h>
#define MAX 100000


int min(int a,int b){
 if(a < b)return a;
 return b;
}


int main(){
 int n,q,i,com,j,sum;
 int x,y;
 int A[MAX];
 int B[MAX];
 int b,L,R;

 scanf("%d %d",&n,&q);
 b=floor(sqrt(n));

 for(i=0;i<n;i++){
   A[i]=0;
   B[i]=0;
 }


 for(i=0;i<q;i++){

   scanf("%d %d %d",&com,&x,&y);

   if(com==0){/*add*/
     A[x]+=y;
     B[x/b]+=y;
   }

   else if(com==1){/*getsum*/
     if(x==y)printf("%d\n",A[x]);

     else{
       L=x/b; R=y/b; sum=0;
       if(L==R){
         for(j=x;j<=y;j++)sum+=A[j];
         printf("%d\n",sum);
       }else{
         for(j=x;j<(L+1)*b;j++)sum+=A[j];
         for(j=L+1;j<R;j++)sum+=B[j];
         for(j=R*b;j<=y;j++)sum+=A[j];
         printf("%d\n",sum);
       }
     }

   }

 }


return 0;
}

本当にあっさりできました。RMQではBの配列にバケットの最小値を入れていましたが、今回はBにバケットの合計を入れることで素早く計算できる（らしいです）。