POJ 3468 A Simple Problem with Integers (线段树成段更新)

题意就是给你一组数据，成段累加，成段查询。

很久之前做的，复习了一下成段更新，就是在单点更新基础上多了一个懒惰标记变量。updata的时候刚好在(l==T[p].l && r==T[p].r)的时候不更新下去，暂时用一个懒惰变量存了起来(所以才懒惰)，不然继续更新下去复杂度会很高。在query的时候更新到下一层(看代码，多打打就有体会了)。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 const int MAXN = 1e5 + 5;
 6 typedef long long LL;
 7 struct segtree {
 8     int l , r;
 9     LL add , sum;
10 }T[MAXN << 2];
11 
12 void init(int p , int l , int r) {
13     T[p].add = 0 , T[p].l = l , T[p].r = r;
14     int mid = (l + r) >> 1;
15     if(l == r) {
16         scanf("%lld" , &T[p].sum);
17         return ;
18     }
19     init(p << 1 , l , mid);
20     init((p << 1)|1 , mid + 1 , r);
21     T[p].sum = T[p << 1].sum + T[(p << 1)|1].sum;
22 }
23 
24 void updata(int p , int l , int r , int val) {
25     int mid = (T[p].l + T[p].r) >> 1;
26     if(T[p].l == l && T[p].r == r) {
27         T[p].add += val;
28         return ;
29     }
30     T[p].sum += val * (r - l + 1);
31     if(r <= mid) {
32         updata(p << 1 , l , r , val);
33     }
34     else if(l > mid) {
35         updata((p << 1)|1 , l , r , val);
36     }
37     else {
38         updata(p << 1 , l , mid , val);
39         updata((p << 1)|1 , mid + 1 , r , val);
40     }
41 }
42 
43 LL query(int p , int l , int r) {
44     int mid = (T[p].l + T[p].r) >> 1;
45     if(l == T[p].l && T[p].r == r) {
46         return T[p].sum + T[p].add * (r - l + 1);
47     }
48     if(T[p].add) {
49         T[p].sum += T[p].add * (T[p].r - T[p].l + 1);
50         T[p << 1].add += T[p].add;
51         T[(p << 1)|1].add += T[p].add;
52         T[p].add = 0;
53     }
54     if(r <= mid) {
55         return query(p << 1 , l , r);
56     }
57     else if(l > mid) {
58         return query((p << 1)|1 , l , r);
59     }
60     else {
61         return query(p << 1 , l , mid) + query((p << 1)|1 , mid + 1 , r);
62     }
63 }
64 
65 int main()
66 {
67     char str[5];
68     int n , m , x , y , z;
69     while(~scanf("%d %d" , &n , &m)) {
70         init(1 , 1 , n);
71         while(m--) {
72             scanf("%s" , str);
73             if(str[0] == 'Q') {
74                 scanf("%d %d" , &x , &y);
75                 printf("%lld
" , query(1 , x , y));
76             }
77             else {
78                 scanf("%d %d %d" , &x , &y , &z);
79                 updata(1 , x , y , (LL)z);
80             }
81         }
82     }
83 }