hdu 1166

题目地址：敌兵布阵

按照胡浩版的线段树代码写的

#include <cstdio>#include <cstring>#include <cstdlib>#include <algorithm>#include <iostream>using namespace std;#define lson l, mid, rt<<1 //直接定义子节点，因为每次都要用到，所以直接定义一个很方便#define rson mid+1, r, rt<<1|1const int MAXN = 51000;int sum[MAXN<<2];void PushUP(int rt)//向上更新父节点的值{    sum[rt] = sum[rt<<1] + sum[rt<<1|1];}void build(int l, int r, int rt)//建立二叉树，rt即为sum数组下标{    if(l == r){//已经到达最底端的叶子节点，即单点，直接输入该值        scanf("%d", &sum[rt]);        return;    }    int mid = (l+r)>>1;    build(lson);//向左子节点继续建立二叉树    build(rson);//向右子节点继续建立二叉树    PushUP(rt);//全部建立完后向上更新父节点的值}void update(int x,int p, int l, int r, int rt)//单点修改{    if(l == r){//说明已经到了最低端的叶子节点，已经是单点了，可以直接修改该值        sum[rt] += p;        return;    }    int mid = (l+r)>>1;    if(mid>=x)//如果要修改的值在这个区间左边，就进入左子节点继续寻找        update(x, p, lson);    else if(mid<x)//如果要修改的值在这个区间右边，就进去右子节点继续寻找        update(x, p, rson);    PushUP(rt);//修改完后，仍然要向上更新父节点的值}int query(int ll, int rr, int l, int r, int rt)//区间查询{    if(ll<=l&&r<=rr){//如果要查询的区间完全覆盖了该子节点，直接返回该子节点的值        return sum[rt];    }    int mid = (l+r)>>1;    int ans = 0;    if(mid>=ll) ans+=query(ll,rr,lson);//如果在该子节点左边还有一部分要查询的区间，就去左子树继续查询    if(mid<rr) ans+=query(ll,rr,rson);//如果在该子节点右边还有一部分要查询的区间，就去右子树继续查询    return ans;}int main(){    int t;    scanf("%d", &t);    int num = 0;    int n;    int a,b;    char s[10];    int ans;    while(t--){        num++;        memset(sum,0,sizeof(sum));        scanf("%d", &n);        build(1,n,1);//建立        PRintf("Case %d:/n", num);        while(scanf("%s", s)){            if(s[0] == 'E')break;            else if(!strcmp(s,"Add")){//修改                scanf("%d %d", &a, &b);                update(a,b,1,n,1);            }else if(!strcmp(s,"Sub")){//修改                scanf("%d %d", &a, &b);                update(a,-b,1,n,1);            }else if(!strcmp(s,"Query")){//查询                scanf("%d %d", &a, &b);                ans = query(a,b,1,n,1);                printf("%d/n", ans);            }        }    }    return 0;}