【HDOJ】1166 敌兵布阵 （线段树）

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

        给定一个数组a[]和一系列的操做，应答每一个询问。ios

        操做：Add i x：a[i]+=x  Sub i x：a[i]-=x  Query l r：询问Σ(a[l..r])数组

【Analysis】ui

        对于Sub i x操做，彻底能够用Add i -x来代替。spa

        标准的线段树，比较简单类型的。具体的能够去看wiki。code

【Code】get

// Task: 1166
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
using namespace std;
#define nil NULL
class SegmentTree
{
    public:
        int x;    // 节点值
        int l,r;  // 区间左右标记
        SegmentTree*left,*right;  // 左右子树
        SegmentTree (int L=0,int R=0)
        {
            l=L,r=R;
            x=0;
            left=right=nil;
        }
}*root;
SegmentTree*Build(int a[],int L,int R)
{
    if (L>R) return nil;
    else
    {
        SegmentTree*ret=new SegmentTree(L,R);
        if (L==R)
            ret->x=a[L];
        else
        {
            int K=(L+R)>>1;
            if ((ret->left=Build(a,L,K))!=nil) ret->x+=ret->left->x;
            if ((ret->right=Build(a,K+1,R))!=nil) ret->x+=ret->right->x;
        }
      //  cout << L << " " << R << " " << ret->x << endl;
        return ret;
    }
}
void Add(int i,int x)
{
    SegmentTree*p=root;
    while (p!=nil)
    {
        p->x+=x;
        int k=(p->l+p->r)>>1;
        if (i<=k) p=p->left;
        else p=p->right;
    }
}
int Query(int l,int r,SegmentTree*p=root)
{
    if (p==nil||l>r) return 0;
    else
    {
        int ret=0;
        if (p->l==l&&p->r==r) return p->x;   // 完美包含
        int k=(p->l+p->r)>>1;
        if (r<=k) return Query(l,r,p->left);  // 全都在左子树
        if (l>k) return Query(l,r,p->right);  // 全都在右子树
        if (l<=k) ret+=Query(l,k,p->left);    // 交叉包含左子树部分
        if (r>k) ret+=Query(k+1,r,p->right);  // 交叉包含右子树部分
    //    printf("%d(%d)-%d(%d) %d\n",l,p->l,r,p->r,ret);
        return ret;
    }
}
const int N = 50000;
int n;
int a[N+1];
char cmd[10];
int main()
{
    int T;
    scanf("%d",&T);
    for (int dex=1;dex<=T;dex++)
    {
        printf("Case %d:\n",dex);
        scanf("%d",&n);
        for (int i=1;i<=n;i++)
            scanf("%d",a+i);
        root=Build(a,1,n);
        scanf("%s",cmd);
        while (cmd[0]!='E')
        {
            int l,r;
            scanf("%d%d",&l,&r);
            switch(cmd[0])
            {
                case 'A':Add(l,r);break;
                case 'S':Add(l,-r);break;
                case 'Q':printf("%d\n",Query(l,r));break;
            }
            scanf("%s",cmd);
        }
    }
    return 0;
}