Binary Indexed Tree (BIT)

#include <iostream>

#include <cstdio>

#include <cmath>

using namespace std;

#define siz 1000005

int tree[siz],a[siz];

int MaxVal,n,m;

void reset(){

    for(int i=0;i<=m;i++) tree[i]=0;

}

int read(int idx){

    int sum=0;

    while(idx>0){

        sum+=tree[idx];

        idx-=(idx & -idx);

    }

    return sum;

}



void update(int idx ,int val){

 while (idx <= MaxVal){

  tree[idx] += val;

  idx += (idx & -idx);

 }

}



void updateSub(int idx ,int val){

 while (idx <= MaxVal){

  tree[idx] -= val;

  idx += (idx & -idx);

 }

}



int main()

{

    int x,y,q,k=1,z;

    //freopen("input.txt","r",stdin);

    scanf("%d",&n);

    for(int t=0;t<n;t++){

        scanf("%d%d",&m,&q);

        reset();

        MaxVal=m;

        for(int i=1;i<=m;i++){

            scanf("%d",&a[i]);

            update(i,a[i]);

        }



        printf("Case %d:\n",k++);

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

            scanf("%d",&z);

            if(z==1){

                scanf("%d",&x);

                x+=1;

                updateSub(x,a[x]);

                printf("%d\n",a[x]);

                a[x]=0;

            }

            else if(z==2){

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

                x+=1;

                a[x]+=y;

                update(x,y);

            }

            else if(z==3){

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

                x+=1;

                y+=1;

                if(x==1) printf("%d\n",read(y));

                else printf("%d\n",read(y)-read(x-1));

            }

        }

    }

    return 0;

}