poj 3468 线段树成段增减区间求和

题意：Q是询问区间和，C是在区间内每个节点加上一个值

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

4
55
9
15

  1 # include <iostream>
  2 # include <cstdio>
  3 # include <cstring>
  4 # include <algorithm>
  5 # include <cmath>
  6 # include <queue>
  7 # define LL long long
  8 using namespace std ;
  9 
 10 
 11 const int maxn = 100010;
 12 
 13 LL sum[maxn<<2] ; //结点开4倍
 14 LL add[maxn<<2] ; //延迟标记
 15 
 16 void PushUP(int rt) //更新到父节点
 17 {
 18     sum[rt] = sum[rt * 2] + sum[rt * 2 + 1] ; //rt 为当前结点
 19 }
 20 
 21 void PushDown(int rt , int m )  //向下更新
 22 {
 23     if (add[rt])
 24     {
 25         add[rt * 2] += add[rt] ;
 26         add[rt * 2 + 1] += add[rt] ;
 27         sum[rt * 2] += (m - m / 2) * add[rt] ;
 28         sum[rt * 2 + 1] += (m / 2) * add[rt] ;
 29         add[rt] = 0 ;
 30     }
 31 }
 32 
 33 void build(int l , int r , int rt) //构建线段树
 34 {
 35     add[rt] = 0 ;
 36     if (l == r)
 37     {
 38         cin>>sum[rt];
 39         return ;
 40     }
 41     int m = (l + r) / 2 ;
 42     build(l , m , rt * 2) ;
 43     build(m + 1 , r , rt * 2 +1) ;
 44     PushUP(rt) ;
 45 }
 46 
 47 void updata(int L , int R , int c , int l , int r , int rt)  //成段增减
 48 {
 49     if (L <= l && r <= R)
 50         {
 51             add[rt] += c ;
 52             sum[rt] += (r - l + 1) * c ;
 53             return  ;
 54         }
 55     PushDown(rt , r - l + 1) ;
 56     int m = (l + r) / 2 ;
 57 
 58     if (L <= m)
 59        updata(L , R , c , l , m , rt * 2) ;
 60     if (R > m)
 61        updata(L , R , c , m + 1 , r , rt * 2 + 1) ;
 62     PushUP(rt) ;
 63 }
 64 
 65 LL query(int L , int R , int l , int r , int rt)  //区间求和
 66 {
 67     if (L <= l && r <= R)
 68         return sum[rt] ;
 69     PushDown(rt , r - l + 1) ;
 70     int m = (l + r) / 2 ;
 71     LL ret = 0 ;
 72     if (L <= m)
 73        ret += query(L , R , l , m , rt * 2) ;
 74     if (R > m)
 75        ret += query(L , R , m + 1 , r , rt * 2 + 1) ;
 76     return ret ;
 77 }
 78 
 79 int main ()
 80 {
 81     //freopen("in.txt","r",stdin) ;
 82     int n , m ;
 83     scanf("%d %d" , &n , &m) ;
 84 
 85         build(1 , n , 1) ;
 86         while(m--)
 87         {
 88             char op[10] ;
 89             int a , b , c ;
 90             scanf("%s" , op) ;
 91             if(op[0] == 'Q')
 92             {
 93                 scanf("%d %d" , &a , &b) ;
 94                 cout<<query(a , b , 1 , n , 1)<<endl ;
 95             }
 96             else
 97             {
 98               scanf("%d %d %d" , &a , &b , &c) ;
 99               updata(a , b , c , 1 , n , 1) ;
100             }
101         }
102 
103 
104 
105     return 0 ;
106 }

View Code

poj 3468 线段树 成段增减 区间求和

poj 3468 线段树成段增减区间求和