hdu1166-敵兵布陣(線段樹）

// File Name: hdu1166.cpp   
// Author: bo_jwolf   
// Created Time: 2013年08月16日 星期五 11時27分03秒   
  
#include<vector>   
#include<list>   
#include<map>   
#include<set>   
#include<deque>   
#include<stack>   
#include<bitset>   
#include<algorithm>   
#include<functional>   
#include<numeric>   
#include<utility>   
#include<sstream>   
#include<iostream>   
#include<iomanip>   
#include<cstdio>   
#include<cmath>   
#include<cstdlib>   
#include<cstring>   
#include<ctime>   
  
using namespace std;  
  
#define lson l , mid , rt << 1    
#define rson mid + 1 , r , rt << 1 | 1    
  
const int maxn = 55555 ;  
//int sum[ maxn << 2 ] ;   
  
struct node  
{  
    int sum ;  
}tree[ maxn << 2 ] ;  
  
void PushUp( int rt )  
{  
    tree[ rt ].sum  = tree[ rt << 1 ].sum + tree[ (rt << 1 | 1 ) ].sum ;  
}  
void build( int l , int r , int rt )  
{  
    if( l == r )  
    {  
        scanf( "%d" , &tree[ rt ].sum );  
        return ;  
    }  
    int mid = ( l + r ) >> 1 ;  
    build( lson ) ;  
    build( rson ) ;  
    PushUp( rt ) ;  
}  
  
void update( int p , int add , int l , int r , int rt )  
{  
    if( l == r )  
    {  
        tree[ rt ].sum  += add ;  
        return ;  
    }  
    int mid = ( l + r ) >> 1 ;  
    if( p <= mid )  
        update( p , add , lson ) ;  
    else  
        update( p , add , rson ) ;  
    PushUp( rt ) ;  
}  
  
int query( int L , int R , int l , int r , int rt )  
{  
    if( L <= l && r <=R )  
    {  
        return tree[ rt ].sum ;  
    }  
    int mid = ( l + r ) >> 1 ;  
    int ret = 0 ;   
    if( L <= mid )  
            ret += query( L , R , lson ) ;  
    if( R > mid )  
            ret += query( L , R , rson ) ;  
    return ret ;  
}  
  
int main()  
{  
    int T , n ;   
    scanf( "%d" , &T ) ;  
    for( int cas = 1 ; cas <= T ; ++cas )  
    {  
        printf( "Case %d:\n" , cas ) ;  
        scanf( "%d" , &n ) ;  
        build( 1 , n , 1 ) ;  
        char op[ 10 ] ;  
        while( scanf( "%s" , op ) )  
        {  
            if( op[ 0 ] == 'E' )   
                break ;  
            int a , b ;  
            scanf( "%d%d" , &a , &b ) ;  
            if( op[ 0 ] == 'Q' )  
                printf( "%d\n" , query( a , b , 1 , n , 1 ) ) ;  
            else if( op[ 0 ] == 'S' )  
                update( a , -b , 1 , n , 1 ) ;  
            else  
                update( a , b , 1 , n , 1 ) ;  
        }  
    }  
return 0;  
}