学步园

线段树简单题

#include<stdio.h>
#define N 50005
int a[N],n,c,cnt;
struct op
{
    int left,right,cont;
}p[N*3];
void insert(int l,int r,int i)
{
    p[i].left=l;p[i].right=r;
    if(l==r)
    {
        p[i].cont=a[l];return;
    }
    int mind=(l+r)/2;
    insert(l,mind,i*2);
    insert(mind+1,r,i*2+1);
        p[i].cont=p[i*2].cont+p[i*2+1].cont;
}
void xiugai(int l,int r,int i)
{
    if(l==r)
    {
        p[i].cont+=cnt;
        return ;
    }
    int mind=(l+r)/2;
    if(c>mind)
    {
        xiugai(mind+1,r,i*2+1);
    }
    else 
    {
        xiugai(l,mind,i*2);
    }
    p[i].cont=p[i*2].cont+p[i*2+1].cont;
}
int chaxun(int start,int end,int i)
{
    int sum=0;
    if(p[i].left==start&&p[i].right==end)
    {
        return p[i].cont;
    }
    int mind=(p[i].left+p[i].right)/2;
    if(start>mind)
        sum+=chaxun(start,end,i*2+1);
    else if(end<=mind)
         sum+=chaxun(start,end,i*2);
    else
    {
        sum+=chaxun(start,mind,i*2);
        sum+=chaxun(mind+1,end,i*2+1);
    }
    return sum;
}
int main()
{
    int i,j,t,o=1;
    char str[20];
    scanf("%d",&t);
        while(o<=t)
        {
            scanf("%d",&n);
            for(i=1;i<=n;i++)
                scanf("%d",&a[i]);
            insert(1,n,1);
            printf("Case %d:\n",o);
            while(scanf("%s",str),str[0]!='E')
            {
                scanf("%d%d",&c,&cnt);
                if(str[0]=='A')
                {
                    xiugai(1,n,1);
                }
                else if(str[0]=='S')
                {
                    cnt=-cnt;
                    xiugai(1,n,1);
                }
                else if(str[0]=='Q')
                {
                        printf("%d\n",chaxun(c,cnt,1));
                }
            }
            o++;
        }
        return 0;
}