HDU 1166 敌兵布阵(线段树，区间求和)

链接：

http://acm.hdu.edu.cn/showproblem.php?pid=1166

分析与总结：

我的第一道线段树，留做纪念。。

学习过程中，主要是遇到了一个问题：

在输入初始化线段树时，有的是直接在build函数里面输入，有的是在外面先全部输入到一个数组里面，然后才build，代码如下：

1.

int build(int cur, int left, int right){
    t[cur].left  = left;
    t[cur].right = right;
    if(left == right){
        // a数组为已经全部输入完毕了
        return t[cur].val=a[left];
    }
    int m = (left+right)>>1;
    return t[cur].val = build(lson(cur),left,m)+build(rson(cur),m+1,right);
}

2.

int build(int cur, int left, int right){
    t[cur].left  = left;
    t[cur].right = right;
    if(left == right){
        scanf("%d",&t[cur].val); //直接在这里输入
        return t[cur].val;
    }
    int m = (left+right)>>1;
    build(lson(cur),left,m);
    build(rson(cur),m+1,right);
    push_up(cur);
}

然后我是综合了上面两种方式:

int build(int cur, int left, int right){
    t[cur].left  = left;
    t[cur].right = right;
    if(left == right){
        scanf("%d",&t[cur].val);
        return t[cur].val;
    }
    int m = (left+right)>>1;
    return t[cur].val = build(lson(cur),left,m)+build(rson(cur),m+1,right);
}

结果一直WA.....

最后发现不能直接return t[cur].val = build(lson(cur),left,m)+build(rson(cur),m+1,right);

只能像第2中方式一样。。。不知道为什么。。求解。。

代码：

1. 线段树

#include<iostream>
#include<cstring>
#include<cstdio>
#define lson(x) ((x)<<1)
#define rson(x) (lson(x)|1)
using namespace std;

typedef int Type; 
const int MAX_NODE = 55555<<2; //开节点数的4倍大小

struct node{
    int left, right; 
    Type val;
    int mid(){return (left+right)>>1;}
    bool buttom(){return left==right;}
};

class SegTree{
public:
    void build(int cur,int left,int right){
        t[cur].left  = left;
        t[cur].right = right;
        if(left==right) {
            scanf("%d", &t[cur].val);
            return;
        }
        int m = (left+right)>>1;
        build(lson(cur),left,m);
        build(rson(cur),m+1,right);
        push_up(cur);
    }
    void update(int cur, int p, Type add){
        t[cur].val += add;
        if(t[cur].buttom())
            return ;
        int m=t[cur].mid();
        if(p <= m) 
            update(lson(cur),p,add);
        else
            update(rson(cur),p,add);
    }
    int query(int cur,int left,int right){
        if(t[cur].left==left && t[cur].right==right)
            return t[cur].val;
        int m = t[cur].mid();
        if(right <= m)
            return query(lson(cur),left,right);
        else if(left > m)
            return query(rson(cur),left,right);
        else
            return query(lson(cur),left,m)+query(rson(cur),m+1,right);
    }
private:
    void push_up(int cur){
        t[cur].val = t[lson(cur)].val+t[rson(cur)].val; 
    }
    node t[MAX_NODE];
};

SegTree st;

int main(){
    int T,cas=1,n, x, y;
    char cmd[8];
    scanf("%d", &T);
    while(T--){
        printf("Case %d:\n",cas++);
        scanf("%d",&n);
        st.build(1,1,n);
        while(scanf("%s",cmd)){
            if(cmd[0]=='E')break;
            scanf("%d%d",&x,&y);
            if(cmd[0]=='A')
                st.update(1,x,y);
            else if(cmd[0]=='S')
                st.update(1,x,-y);
            else 
                printf("%d\n",st.query(1,x,y));
        }
    }
    return 0;
}

2. 树状数组

#include<iostream>
#include<cstdio>
#include<cstring>
#define mid ((left+right)>>1)
#define lson rt<<1,left,mid
#define rson rt<<1|1,mid+1,right
using namespace std;

const int MAXN = 50005;
int c[MAXN], n;

int lowbit(int x){return x&(-x);}
int sum(int x){
    int ret = 0;
    while(x > 0){
        ret += c[x];
        x -= lowbit(x);
    }
    return ret;
}
void add(int x, int add){
    while(x <= n){
        c[x] += add;
        x += lowbit(x);
    }
}

int main(){
    int T, x, y,cas=1;
    char cmd[8];
    scanf("%d",&T);
    while(T--){
        printf("Case %d:\n", cas++);
        memset(c, 0, sizeof(c));
        scanf("%d",&n);
        for(int i=1; i<=n; ++i){
            scanf("%d",&x);
            add(i,x);
        }
        while(scanf("%s",cmd)){
            if(cmd[0] == 'E') break;
            scanf("%d %d",&x,&y);
            if(cmd[0] == 'Q'){
                printf("%d\n", sum(y)-sum(x-1));
            }
            else if(cmd[0] == 'A')
                add(x,y);
            else
                add(x,-y);
        }
    }
    return 0;
}

—— 生命的意义，在于赋予它意义士。

原创http://blog.csdn.net/shuangde800，By D_Double (转载请标明)