hdu1166-敌兵布阵(线段树） - c++编程基础

// File Name: hdu1166.cpp   
// Author: bo_jwolf   
// Created Time: 2013年08月16日 星期五 11时27分03秒   
  
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
  
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;  
}