poj3468(线段树区间更新&区间求和模板)

题意: 输入 n, m表初始有 n 个数, 接下来 m 行输入, Q x y 表示询问区间 [x, y]的和；

C x y z 表示区间 [x, y] 内所有数加上 z ；

思路: 线段树区间更新&区间求和模板；

代码:

 1 #include <iostream>
 2 #include <stdio.h>
 3 #define ll long long
 4 #define lson l, mid, rt << 1
 5 #define rson mid + 1, r, rt << 1 | 1
 6 using namespace std;
 7 
 8 const int MAXN = 1e5 + 10;
 9 ll sum[MAXN << 2];
10 ll add[MAXN << 2];
11 
12 void push_up(int rt){//向上更新
13     sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
14 }
15 
16 void push_down(int rt, int m){
17     if(add[rt]){//若有标记,则将标记向下移动一层
18         add[rt << 1] += add[rt];
19         add[rt << 1 | 1] += add[rt];
20         sum[rt << 1] += (m - (m >> 1)) * add[rt];
21         sum[rt << 1 | 1] += (m >> 1) * add[rt];
22         add[rt] = 0;//取消本层标记
23     }
24 }
25 
26 void build(int l, int r, int rt){//建树
27     add[rt] = 0;
28     if(l == r){
29         scanf("%lld", &sum[rt]);
30         return;
31     }
32     int mid = (l + r) >> 1;
33     build(lson);
34     build(rson);
35     push_up(rt);//向上更新
36 }
37 
38 void update(int L, int R, ll key, int l, int r, int rt){//区间更新
39     if(L <= l && R >= r){
40         sum[rt] += (r - l + 1) * key;
41         add[rt] += key;
42         return;
43     }
44     push_down(rt, r - l + 1);//向下更新
45     int mid = (l + r) >> 1;
46     if(L <= mid) update(L, R, key, lson);
47     if(R > mid) update(L, R, key, rson);
48     push_up(rt);//向上更新
49 }
50 
51 ll query(int L, int R, int l, int r, int rt){//区间求和
52     if(L <= l && R >= r) return sum[rt];
53     push_down(rt, r - l + 1);//向下更新
54     int mid = (l + r) >> 1;
55     ll ans = 0;
56     if(L <= mid) ans += query(L, R, lson);
57     if(R > mid) ans += query(L, R, rson);
58     return ans;
59 }
60 
61 int main(void){
62     int n, m;
63     scanf("%d%d", &n, &m);
64     build(1, n, 1);
65     while(m--){
66         char str[3];
67         int x, y;
68         ll z;
69         scanf("%s", str);
70         if(str[0] == 'C'){
71             scanf("%d%d%lld", &x, &y, &z);
72             update(x, y, z, 1, n, 1);
73         }else{
74             scanf("%d%d", &x, &y);
75             printf("%lld
", query(x, y, 1, n, 1));
76         }
77     }
78 }

View Code