线段树

qwq ， ylx 问我要一份线段树的版，可我线段树一直是10分钟，从不写版，qwq ，还是放一份版在这。

题目见： http://acm.hdu.edu.cn/showproblem.php?pid=1166

只是单点查询+区间修改（zkw版本），唯一注意的就是数组不能开小了（我先就是数组开小了，一直错）

 1 #include <iostream>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <cstdio>
 5 const int inf = 1<<30 , maxn = 1 << 16  ;
 6 int t , n , M , tree[maxn<<1] ;
 7 char ch[15] ;
 8 using namespace std ;
 9 
10 void build( int num )
11 {
12     for( M = 1 ; M <= num + 1 ; M <<= 1 ) ;
13     for( int i = M + 1 ; i <= M + num ; ++i )
14         scanf( "%d" , tree+i ) ;
15     for( int i = M - 1 ; i > 0 ; --i )
16         tree[i] = tree[i<<1] + tree[i<<1|1] ;
17 }
18 
19 
20 
21 
22 void update( int num , int add )
23 {
24     for( tree[num+=M] += add , num>>=1 ; num; num>>=1 )
25         tree[num] = tree[num<<1] + tree[num<<1|1] ;
26 }
27 
28 
29 int quer( int l , int r  )
30 {
31     int ans = 0 ;
32     for( l = l + M - 1 , r = r + M + 1 ; l^r^1 ; l >>= 1 , r >>= 1  )
33     {
34         if( ~l&1 ) ans += tree[l^1] ; 
35         if( r & 1 ) ans += tree[r^1] ;
36     }
37     return ans ;
38 }
39 
40 int main( )
41 {
42     scanf( "%d" , &t ) ;
43     int a , b , i = 0 ;
44     while( t-- )
45     {
46         scanf( "%d" , &n ) ;
47         memset( tree, 0, sizeof(tree) );  
48         build( n ) ;
49         printf("Case %d:
" , ++i ); 
50         while( 1 )
51         {
52             
53             scanf( "%s" , ch ) ;
54             if( ch[0] == 'E' ) break ;
55             scanf( "%d%d" , &a , &b ) ;
56             if( ch[0] == 'Q' )
57             {
58                 printf( "%d
" , quer( a , b ) ) ;
59             }
60             else
61             {
62                 if( ch[0] == 'S' ) b = -b ;
63                 update( a , b ) ;
64             }
65         }
66     }
67     return 0 ;
68 }

题目见：http://poj.org/problem?id=3468

这是区间修改+区间查询普通版

  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdlib>
  4 #include <cstdio>
  5 const int inf = 1<<30 , maxn = 100000 + 11 ;
  6 using namespace std;
  7 int n , q , cnt ;
  8 struct id
  9 {
 10      long long  sum , lazy ;
 11 }tree[maxn<<2] ;
 12 
 13 long long int read(  ) {
 14     char ch = getchar(  ) ; long long int ret = 0 , k = 1 ;
 15     while( ch < '0' || ch > '9' ) { if( ch == '-' ) k = -1 ; ch = getchar(  ) ; }
 16     while( ch >= '0' && ch <= '9' ) ret = ret * 10 + ch - '0' , ch = getchar(  ) ;
 17     return ret * k ;
 18 }
 19 
 20 
 21 
 22 void set_lazy( int num , int l , int r )
 23 {
 24     int m = r - l + 1 ; 
 25     if( tree[num].lazy )
 26     {
 27         tree[num<<1].lazy += tree[num].lazy ;
 28         tree[(num<<1)+1].lazy += tree[num].lazy ;
 29         tree[num<<1].sum += tree[num].lazy * ( m - (m>>1) ) ;
 30         tree[(num<<1)+1].sum += tree[num].lazy * ( m>>1 ) ;
 31         tree[num].lazy = 0ll ;
 32     }
 33     
 34 }
 35 
 36 void update( int l , int r , int num , int L , int R , int add )
 37 { 
 38     if( l == L && r == R )
 39     {
 40         tree[num].sum += 1ll*add * ( R - L + 1 ) ;
 41         tree[num].lazy += add ; 
 42         return ;
 43     }
 44     if( l == r ) return ;
 45     set_lazy( num , l , r ) ; 
 46     int mid = l + ( ( r - l ) >> 1 );
 47     if( R <= mid ) update( l , mid , num<<1 , L , R , add ) ;
 48     else if( L > mid ) update( mid+1 , r , (num<<1)+1 , L , R , add ) ;
 49     else 
 50     {
 51         update( l , mid , num<<1 , L , mid , add ) ;
 52         update( mid+1 , r , (num<<1)+1 , mid+1 , R , add ) ;    
 53     }
 54     tree[num].sum = tree[num<<1].sum + tree[(num<<1)+1].sum ;
 55 }
 56 
 57 
 58 long long int quer( int l , int r , int num , int L , int R )
 59 { 
 60     if( l == L && R == r ) return tree[num].sum ;
 61     set_lazy( num , l , r ) ; 
 62     int mid = l + ( ( r - l ) >> 1 ) ;
 63     if( R <= mid ) return quer( l , mid , num<<1 , L , R ) ;
 64     else if( L > mid ) return quer( mid + 1 , r , (num<<1)+1 , L , R ) ;
 65     else return quer( l  , mid  , num<<1 , L , mid ) + quer( mid+1 , r , (num<<1)+1 , mid+1 , R ) ;
 66 }
 67 
 68 
 69 void build( int num , int l , int r )
 70 {
 71     tree[num].lazy = 0ll ;
 72     if( l == r )
 73     {
 74         tree[num].sum = read( ) ;
 75         return ;
 76     }
 77     int mid = l + ( ( r - l ) >> 1 ) ;
 78     
 79     build( num<<1 , l , mid ) ;
 80     build( (num<<1)+1 , mid+1 , r ) ;
 81     tree[num].sum = tree[num<<1].sum + tree[(num<<1)+1].sum ; 
 82 }
 83 
 84 int main( )
 85 {
 86     n = read( ) , q = read( ) ; 
 87     build( 1 , 1 , n  ) ;
 88     for( int  x = 1 ; x <= q ; ++x )
 89     {
 90         char a ; int b , c , d ;
 91         scanf( "%s" , &a ) ;
 92         b = read( ) , c = read( ) ;
 93         if( a == 'C' ) 
 94         {
 95             d = read( ) ;
 96             update( 1 , n , 1 , b , c , d ) ;
 97         }
 98         if( a == 'Q' )
 99         {
100             printf( "%lld
" , quer( 1 , n , 1 , b , c ) ) ;
101         }
102     }
103 }