HDU 1166 敌兵布阵

线段树第一题，看了很长时间都不会啊，入手了一个最简单的单点更新线段树的题，交了好几发才过。

题目大意：

给出n个数，然后有不大于40000条询问，可以更新某一个数的值，求某一段数的总和。

最水的线段树题目，就不再写思路了。

下面是代码：

#include <stdio.h>
const int Maxn=50005;
int node[Maxn<<2];
void pushup(int tr)
{
    node[tr]=node[tr<<1]+node[tr<<1|1];
}
void Build_tr(int l,int r,int tr)
{
    if(l==r)
    {
        scanf("%d",&node[tr]);
        return;
    }
    int mid=(l+r)>>1;
    Build_tr(l,mid,tr<<1);
    Build_tr(mid+1,r,tr<<1|1);
    pushup(tr);
}
int query(int L,int R,int l,int r,int tr)
{
    if(L<=l&&r<=R)return node[tr];
    int mid=(l+r)/2;
    int ans =0;
    if(L<=mid)ans+=query(L,R,l,mid,tr<<1);
    if(R>mid)ans+=query(L,R,mid+1,r,tr<<1|1);
    return ans;
}
void update(int num,int add,int l,int r,int tr)
{
    if(l==r)
    {
        node[tr]+=add;
        return ;
    }
    int mid=(l+r)>>1;
    if(num<=mid)update(num,add,l,mid,tr<<1);
    else update(num,add,mid+1,r,tr<<1|1);
    pushup(tr);
}
int main()
{
    int t,case1=1;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        Build_tr(1,n,1);
        char s[10];
        scanf("%s",s);
        printf("Case %d:\n",case1++);
        while(s[0]!=‘E‘)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            if(s[0]==‘Q‘)printf("%d\n",query(a,b,1,n,1));
            else if(s[0]==‘A‘)update(a,b,1,n,1);
            else if(s[0]==‘S‘)update(a,-b,1,n,1);
            scanf("%s",s);
        }
    }
    return 0;
}

HDU 1166 敌兵布阵

原文：http://blog.csdn.net/lin375691011/article/details/19347431