L - 敌兵布阵 (线段树模板题)

思路:板子题。

AC代码:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAX=50050;
int t,N;
int tr[MAX<<4];
void re(int x)
{
    tr[x]=tr[x*2]+tr[x*2+1];
}
void build(int st,int ed,int node)
{
    if(st==ed)
    {
        scanf("%d",&tr[node]);
        return;
    }
    int mid=(st+ed)>>1;
    build(st,mid,node<<1);
    build(mid+1,ed,(node<<1)+1);
    re(node);
}
void update(int st,int ed,int node,int id,int val)
{
    if(st==ed)
    {
        tr[node]+=val;
        return;
    }
    int mid=(st+ed)>>1;
    if(id<=mid)
    {
        update(st,mid,node<<1,id,val);
    }
    else
    {
        update(mid+1,ed,node<<1|1,id,val);
    }
    re(node);
}
int query(int st,int ed,int node,int l,int r)
{
    if(r<st||l>ed) return 0;
    else if(st>=l&&ed<=r) return tr[node];
    int mid=(st+ed)>>1;
    int l_sum=query(st,mid,node<<1,l,r);
	int r_sum=query(mid+1,ed,node<<1|1,l,r);
	return  l_sum+r_sum;
}
int main()
{
    scanf("%d",&t);
    for(int k=1;k<=t;k++)
    {
        scanf("%d",&N);
        printf("Case %d:\n",k);
        build(1,N,1);
        char op[10];
        while(scanf("%s",op))
        {
            if(op[0]=='E')
            {
                break;
            }
            int i,j;
            scanf("%d %d",&i,&j);
            if(op[0]=='A')
            {
                update(1,N,1,i,j);
            }
            if(op[0]=='S')
            {
                update(1,N,1,i,-j);
            }
            if(op[0]=='Q')
            {
                cout<<query(1,N,1,i,j)<<endl;
            }
        }
    }
    return 0;
}