HDU 1166(単点更新の線分ツリー)

大牛NotOnlySuccessのブログとshiqiを見た614の線分樹をまとめた後、人間として生まれ変わり、線分樹を完成させることを決意する.第一歩は、セグメントツリーのコードと構造部分の総括と関連として、ふわふわしたコードスタイルです.code:

#include
#include
#include
using namespace std;

#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
const int maxn = 55010;

int tree[maxn<<2];

void pushUp(int rt)
{
    tree[rt]=tree[rt<<1]+tree[rt<<1|1];
}

void build(int l,int r,int rt)
{
    if(l==r)
    {
        scanf("%d",&tree[rt]);
        return ;
    }
    int m=(l+r)>>1;
    build(lson);
    build(rson);
    pushUp(rt);
}

void update(int p, int add, int l,int r, int rt)// 
{
    if(l==r)
    {
        tree[rt]+=add;
        return ;
    }
    int m=(l+r)>>1;
    if(p<=m)
    {
        update(p,add,lson);
    }
    else{
        update(p,add,rson);
    }
    pushUp(rt);
}

int query(int L,int R,int l,int r,int rt)
{
    if(r<=R&&l>=L)
    {
        return tree[rt];
    }
    int sum=0;
    int m=(l+r)>>1;
    if(L<=m)
    {
        sum+=query(L,R,lson);
    }
    if(R>m)
    {
        sum+=query(L,R,rson);
    }
    return sum;
}

int main()
{
    int t;
    int n;
    int x,y;
    scanf("%d",&t);
    for(int _case=1;_case<=t;_case++)
    {
        printf("Case %d:
",_case);
        scanf("%d",&n);
        build(1,n,1);
        string conmond;
        while(cin>>conmond)
        {
            if(conmond=="End")
                break;
            scanf("%d%d",&x,&y);
            if(conmond=="Add")
                update(x,y,1,n,1);
            if(conmond=="Sub")
                update(x,-y,1,n,1);
            if(conmond=="Query")
                printf("%d
",query(x,y,1,n,1));
        }
    }
    return 0;
}