hdu 1166 敌兵布阵 线段树

#include<cstdio>
#include<cstring>
using namespace std;
int sum;
int s1[100000],s2[1000000];
int build(int l,int r,int p)
{
   if (l==r) return s2[p]=s1[l];
   int m=(l+r)/2;
   int a=build(l,m,2*p);
   int b=build(m+1,r,2*p+1);
   return s2[p]=a+b;
}
void un(int l,int r,int p,int pos,int c)
{
    if (l<=pos&&r>=pos) s2[p]+=c;
    if (l==r) return ;
    int m=(l+r)/2;
    if (pos<=m) un(l,m,2*p,pos,c);
    else un(m+1,r,2*p+1,pos,c);
    return ;
}
void find(int l,int r,int p,int ll,int rr)
{
    if (ll<=l&&rr>=r) {sum+=s2[p];return ;}
    if (ll>r||rr<l) return ;
    int m=(l+r)/2;
    find(l,m,2*p,ll,rr);
    find(m+1,r,2*p+1,ll,rr);
    return ;
}
int main()
{
    int n,i,k,c,a,b;
    char s[10];
    scanf("%d",&c);
    for (k=1;k<=c;k++)
    {
        //if (k!=1) printf("\n");
        printf("Case %d:\n",k);
        scanf("%d",&n);
        for (i=1;i<=n;i++) scanf("%d",&s1[i]);
        build(1,n,1);
        while (~scanf("%s",&s))
        {
            if (s[0]==‘E‘) break;
            scanf("%d%d",&a,&b);
            if (s[0]==‘A‘) un(1,n,1,a,b);
            if (s[0]==‘S‘) un(1,n,1,a,-b);
            if (s[0]==‘Q‘)
            {
                sum=0;
                find(1,n,1,a,b);
                printf("%d\n",sum);
            }
        }
    }
    return 0;
}