[线段树]模板2

【模板】线段树2

题目描述

给定一个无序数列，有两种操作：

1.将一个区间内的所有点值都加上一个整数

2.求一个区间的和

输入

输入的第1行，共有两个数n和q，表示数列长度和操作次数

输入的第2行，共有n个数，表示该数列

接下来共有q行，每行有3～4个数第1个数为操作类型，具体如下

若是第1种操作，接下来三个数x,y,z表示将［x,y]内所有数加上z。

若是第2种操作，接下来两个数x，y表示闭区间的左右端点

输出

输出共有若干行，对于每一个询问输出一个整数结果

样例输入

样例输出

10
13
30

提示

1<=n,q<=200000

保证输入的所有数据在int范围内

代码：

 1 #include <cstdio>    
 2 #include <algorithm>    
 3 using namespace std;    
 4 #define lson l , m , rt*2    
 5 #define rson m + 1 , r , rt*2+1 
 6 #define root 1 , N , 1   
 7 const int maxn = 200001;    
 8 long long add[maxn<<2];    
 9 long long sum[maxn<<2];    
10 
11 void PushUp(int rt) {    
12     sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];    
13 }
14    
15 void PushDown(int rt, int m) {    
16     if (add[rt]) {    
17         add[rt << 1] += add[rt];    
18         add[rt << 1 | 1] += add[rt];    
19         sum[rt << 1] += add[rt] * (m - (m >> 1));    
20         sum[rt << 1 | 1] += add[rt] * (m >> 1);    
21         add[rt] = 0;    
22     }    
23 }    
24 
25 void Build(int l, int r, int rt) {    
26     add[rt] = 0;    
27     if (l == r) {    
28         scanf("%lld", &sum[rt]);    
29         return ;    
30     }    
31     int m = (l + r) >> 1;    
32     Build(lson);    
33     Build(rson);    
34     PushUp(rt);    
35 }    
36 
37 void Update(int L, int R, int c, int l, int r, int rt) {    
38     if (L <= l && r <= R) {    
39         add[rt] += c;    
40         sum[rt] += (long long)c * (r - l + 1);    
41         return ;    
42     }    
43     PushDown(rt, r - l + 1);    
44     int m = (l + r) >> 1;    
45     if (L <= m) {
46         Update(L, R, c, lson);    
47     }
48     if (m < R) {
49         Update(L, R, c, rson);    
50     }
51     PushUp(rt);
52 } 
53    
54 long long Query(int L, int R, int l, int r, int rt) {    
55     if (L <= l && r <= R) {    
56         return sum[rt];    
57     }    
58     PushDown(rt, r - l + 1);    
59     int m = (l + r) >> 1;    
60     long long re = 0;    
61     if (L <= m) {
62         re += Query(L, R, lson);    
63     }
64     if (m < R) {
65         re += Query(L, R, rson);    
66     }
67     return re;    
68 }    
69 
70 int main() {    
71     int N , Q;    
72     scanf("%d%d", &N, &Q);    
73     Build(root);    
74     while (Q --) {    
75         char op[2];    
76         int a , b , c;    
77         if (scanf("%s", op)!= 1) {
78             break;  
79         }
80         if (op[0] == '2') {    
81             scanf("%d%d", &a, &b);    
82             printf("%lld
", Query(a , b ,root));    
83         } 
84         else {    
85             scanf("%d%d%d", &a, &b, &c);    
86             Update(a, b, c, root);    
87         }    
88     }    
89     return 0;    
90 }