[ACM 데이터 구조] 선분 트 리 템 플 릿

#include<iostream>

#include<cmath>

using namespace std;

#define maxn 200005

class Node{

public:

    int l,r;

    int add;//   

    int sum;

}node[maxn];

int getRight(int n){//    2^x>=n   x[ 0   ,       ]

    return ceil(log10(n*1.0)/log10(2.0));

}

void build(int l,int r,int num){//    [1,2^getRight(n)],num=1  

    if(l==r){

        node[num].l=node[num].r=l;node[num].add=0;node[num].sum=0;

        return;

    }

    node[num].l=l;node[num].r=r;node[num].add=0;node[num].sum=0;

    build(l,(l+r)/2,num*2);

    build((l+r)/2+1,r,num*2+1);

}

void add(int o,int l,int r,int v){// o      [     o=1  ]   [l,r]   v

    if(l<=node[o].l && r>=node[o].r){//   [    ]

        node[o].add+=v;

    }else{

        int M=node[o].l+(node[o].r-node[o].l)/2;

        if(r<=M)add(o*2,l,r,v);

        else if(l>M)add(o*2+1,l,r,v);

        else{

            add(o*2,l,M,v);

            add(o*2+1,M+1,r,v);

        }

    }

    //    o

    if(node[o].l!=node[o].r){//             

        node[o].sum=node[2*o].sum+node[2*o+1].sum;

    }else node[o].sum=0;

    node[o].sum+=node[o].add*(node[o].r-node[o].l+1);

}



//  addadd           addadd [             add  ，         add ]

//        0

int sum=0;

void ask(int o,int l,int r,int addadd){// o      [     o=1  ]   [l,r]  

    if(l<=node[o].l && r>=node[o].r){//   [    ]

        sum+=(node[o].sum+addadd*(node[o].r-node[o].l+1));

    }else{

        int M=node[o].l+(node[o].r-node[o].l)/2;

        if(r<=M)ask(o*2,l,r,node[o].add+addadd);

        else if(l>M)ask(o*2+1,l,r,node[o].add+addadd);

        else{

            ask(o*2,l,M,node[o].add+addadd);

            ask(o*2+1,M+1,r,node[o].add+addadd);

        }

    }

}

int main(){

    int T;

    cin>>T;

    int kases=1;

    int i,j;

    int a;

    for(;kases<=T;kases++){

        int N;

        cin>>N;

        build(1,1<<getRight(N),1);

        for(i=1;i<=N;i++){

            cin>>a;

            add(1,i,i,a);

        }

        char str[10];

        cout<<"Case "<<kases<<":
";

        bool ok=1;

        while(ok){

            cin>>str;

            switch(str[0]){

            case 'Q':

                cin>>i>>j;

                sum=0;

                ask(1,i,j,0);

                cout<<sum<<'
';

                break;

            case 'A':

                cin>>i>>j;

                add(1,i,i,j);

                break;

            case 'S':

                cin>>i>>j;

                add(1,i,i,-j);

                break;

            case 'E':

                ok=0;

                break;

            default:break;

            }

        }

    }return 0;

}