hdu-1166

#include <cstdlib>
const int kMaxNum = 50000;
const int kMaxStrLen = 10;
int kN, kT;
int kSum[kMaxNum<<2];
///将儿子的信息更新到父亲节点上
void (int rt)
{
    kSum[rt] = kSum[rt<<1] + kSum[rt<<1|1];
}
/**
建线段树
*/
void BuildTree(int l, int r, int rt)
{
    if(l == r)
    {
        scanf("%d", &kSum[rt]);
        return ;
    }
    int mid = (l+r)>>1;
    BuildTree(l, mid, rt<<1);
    BuildTree(mid+1, r, rt<<1|1);
    PushUp(rt);
}
/**
更新操作
*/
void UpdateTree(int index, int val, int l, int r, int rt)
{
    if(l == r)
    {
        kSum[rt] += val;
        return;
    }
    int mid = (l+r)>>1;
    if(index <= mid)
        UpdateTree(index, val, l, mid, rt<<1);
    else
        UpdateTree(index, val, mid+1, r, rt<<1|1);
    PushUp(rt);
}
/**
询问
*/
int QueryTree(int left, int right, int l, int r, int rt)
{
    if(left <= l &&  r <= right)///说明在这个区间内
        return kSum[rt];
    int ret = 0;
    int mid = (l+r)>>1;
    if(left <= mid)///说明在 left-----mid这个区间
        ret += QueryTree(left, right, l, mid, rt<<1);
    if(right > mid)///说明在 mid------right这个区间
        ret += QueryTree(left, right, mid+1, r, rt<<1|1);
    return ret;
}
int main()
{
    scanf("%d", &kT);
    int cnt = 0;
    char op[kMaxStrLen];
    int l, r;
    while(cnt < kT)
    {
        printf("Case %d:n", ++cnt);
        scanf("%d", &kN);
        BuildTree(1, kN, 1);
        while(scanf("%s", op))
        {
            if(op[0] == 'E')
                break;
            scanf("%d%d",&l,&r);
            if(op[0] == 'A')
                UpdateTree(l, r, 1, kN, 1);
            else if(op[0] == 'S')
                UpdateTree(l, -r, 1, kN, 1);
            else
                printf("%dn", QueryTree(l, r, 1, kN, 1));
        }
    }
    return 0;
}