HDU.1166 敌兵布阵 (线段树 单点更新 区间查询)

题意分析

加深理解，重写一遍

代码总览

#include <bits/stdc++.h>

#define nmax 100000

using namespace std;

struct Tree{

    int l,r,val;

    int lazy;

    int mid(){

        return (l+r)>>1;

    }

};

Tree tree[nmax<<2];

int num[nmax<<2];

void PushUp(int rt)

{

    tree[rt].val = tree[rt<<1].val + tree[rt<<1|1].val;

}

void Build(int l, int r, int rt)

{

    tree[rt].l = l; tree[rt].r = r;

    tree[rt].val = tree[rt].lazy = 0;

    if(l == r){

        tree[rt].val = num[l];

        return;

    }

    Build(l,tree[rt].mid(),rt<<1);

    Build(tree[rt].mid()+1,r,rt<<1|1);

    PushUp(rt);

}

void UpdatePoint(int val, int pos, int rt)

{

    if(tree[rt].l == tree[rt].r){

        tree[rt].val+=val;

        return;

    }

    if(pos<= tree[rt].mid()) UpdatePoint(val,pos,rt<<1);

    else UpdatePoint(val,pos,rt<<1|1);

    PushUp(rt);

}

int Query(int l,int r,int rt)

{

    if(l>tree[rt].r || r<tree[rt].l) return 0;

    if(l <= tree[rt].l && tree[rt].r <= r) return tree[rt].val;

    return Query(l,r,rt<<1) + Query(l,r,rt<<1|1);

}

int T,N,a,b;

char op[10];

int main()

{

    //freopen("in.txt","r",stdin);

    scanf("%d",&T);

    for(int i = 1;i<=T;++i){

        printf("Case %d:\n",i);

        scanf("%d",&N);

        for(int j = 1;j<=N;++j) scanf("%d",&num[j]);

        Build(1,N,1);

        while(scanf(" %s",op) && op[0] != 'E'){

            scanf("%d %d",&a,&b);

            if(op[0] == 'Q'){

                printf("%d\n",Query(a,b,1));

            }else if(op[0] == 'A'){

                UpdatePoint(b,a,1);

            }else{

                UpdatePoint(-b,a,1);

            }

        }

    }

    return 0;

}