POJ A Simple Problem with Integers 线段树的成段更新

A Simple Problem with Integers

Description

You have N integers, A₁, A₂, ... , A_N. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.

Input

The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000. The second line contains N numbers, the initial values of A₁, A₂, ... , A_N. -1000000000 ≤ A_i ≤ 1000000000. Each of the next Q lines represents an operation. "C a b c" means adding c to each of A_a, A_a₊₁, ... , A_b. -10000 ≤ c ≤ 10000. "Q a b" means querying the sum of A_a, A_a₊₁, ... , A_b.

Output

You need to answer all Q commands in order. One answer in a line.

Sample Input

10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

Sample Output

Hint

The sums may exceed the range of 32-bit integers.

/* 如果两个人的天堂 象是温馨的墙 囚禁你的梦想 幸福是否象是一扇铁窗 候鸟失去了南方*/

#include<cstdio>
#include<iostream>
#define M 100010
struct node{ int s , e  ; long long  add ,  sum  ; }qe[M*4] ;//数据太大 需要 long long 
using namespace std ;
long long  Max , sum ;
void creat( int s , int e , int step ){ // 建树 
	qe[step].s = s ; 
	qe[step].e = e ;
	qe[step].sum = 0 ;
	qe[step].add = 0 ;
	if( s == e ) return ;
	int mid = ( s + e ) >> 1 ;
	creat( s , mid , step << 1 ) ;
	creat( mid + 1 ,e , step << 1 |1 ) ;
}
long long  ma( long long  a , long long  b ){
	if( a > b ) return a ;
	return b ;
}
void pushdown(int step , int s , int e )  
{    
	long long f = qe[step].add ;
    if( f )  
    {   int mid = ( s + e ) >> 1 ;
        qe[step<<1].add += f;  
        qe[step<<1|1].add += f ;  
        qe[step<<1].sum += f * ( qe[step<<1].e - qe[step<<1].s + 1 ) ; 
        qe[step<<1|1].sum += f * ( qe[step<<1|1].e - qe[step<<1|1].s + 1 ) ; 
        qe[step].add = 0 ;  // 已经更新 子树 所以需要置为 0 避免下次重复更新子节点
    }  
}  
void insert( long long  i , long long  mun , long long  step ){ // 把线段树初始化 
	if( qe[step].s == qe[step].e  ){
		qe[step].sum = mun ;
		return ;
	}
	
	int mid = ( qe[step].s + qe[step].e ) >> 1 ;
	if( mid >= i )
		insert( i , mun , step << 1 ) ;

	else insert( i ,mun , step << 1 | 1 ) ;
	qe[step].sum = qe[step<<1].sum + qe[step<<1|1].sum ;
	return ;
}
void up( int s , int e , int add , int step ){

	if( qe[step].s == s && qe[step].e == e ){
		qe[step].add += add ;
		qe[step].sum += ( add * ( e - s + 1 ) ) ;
		return ;
	}
	pushdown( step ,s , e  ) ; // 如果 当前的 线段 qe[].add 不为 0 就一起向下更新 

	int mid = ( qe[step].s + qe[step].e ) >> 1 ;
	if( mid >= e ) up( s , e , add , step << 1 ) ;
	else if( s > mid ) up( s , e , add , step << 1| 1 ) ;
	else {
		up( s , mid , add , step << 1 ) ;
		up( mid + 1 , e , add , step <<1|1 ) ;
	}
	qe[step].sum = qe[step<<1].sum + qe[step<<1|1].sum ;//更新当前的 线段
	return ;
}
long long  find( int s , int e ,int step ){
	if( s == qe[step].s && e == qe[step].e ){	
		return qe[step].sum ; 
	}
	 pushdown( step ,s , e ) ;// 查找的时候也要更新 
	 int mid = ( qe[step]. s + qe[step].e ) >> 1 ;
	 if( mid >= e ) return find( s , e , step << 1 ) ;
	 else if( mid < s ) return find( s , e ,  step << 1 | 1 ) ;
	 else {
		return  find( s , mid , step << 1 ) + find( mid + 1 , e , step << 1 | 1 ) ;
	 }
}
int main()
{
	int i , n , m , k , u , v ;
	char o ;
	//freopen( "in.txt" , "r" , stdin)
	while( scanf( "%d%d" , &n , &m ) != EOF ){
		  creat( 1 , n , 1 ) ;
		for( i = 1 ; i <= n ;i++ ) {
			scanf( "%d" , &u ) ;
			insert( i , u , 1 ) ;
		}
		while( m-- ){
			scanf( " %c" , &o ) ;
			if( o == 'C' ){
			scanf( "%d%d%d" , &u , &v ,&k ) ;
			 up( u , v , k , 1 ) ;
			}
			else{  
				Max = 0 ; sum = 0 ;
				 scanf( "%d%d" , &u , &v ) ;
				 printf( "%lld\n" , find( u , v , 1 ) ) ;
			}
		}
	}
}

代码：