线段树

 1 #include<iostream>
 2 #include<string>
 3 #define ll long long
 4 const int N = 1e5 + 5;
 5 
 6 using namespace std;
 7 
 8 ll tree[N<<2]; // 线段树,可以是对应的结构体
 9 ll lz[N<<2]; // 延迟标记，也可以是结构体
10 
11 //lz标记下传
12 void push_down(int id, int l, int r) {
13     if (lz[id]) {
14         int mid = (l + r) / 2;
15         lz[id * 2] += lz[id];
16         lz[id * 2 + 1] += lz[id];
17         tree[id * 2] += 1LL * (mid - l + 1) * lz[id];
18         tree[id * 2 + 1] += 1LL * (r - mid) * lz[id];
19         lz[id] = 0;
20     }
21 }
22 
23 //左右树信息合并
24 void push_up(int id) {
25     tree[id] = tree[id * 2] + tree[id * 2 + 1];
26 }
27 // 创建线段树
28 void build(int id, int l, int r) {
29     if (l == r) {
30         cin >> tree[id];//初始化可根据自己的要求来改写；
31         return;
32     }
33     int mid = (l + r) / 2;
34     build(id * 2, l, mid);
35     build(id * 2 + 1, mid + 1, r);
36     push_up(id);
37 }
38 
39 // 区间更新，lr为更新范围，LR为线段树范围，add为更新值
40 
41 void update(int id, int L, int R, int l, int r, int add) {
42     if (l <= L && r >= R) {
43         lz[id] += 1LL * add;
44         tree[id] += 1LL * (R - L + 1) * add; // 更新方式
45         return;
46     }
47     push_down(id, L, R);
48     int mid = (L + R) / 2;
49     if (mid >= l) update(id * 2, L, mid, l, r, add);
50     if (mid < r) update(id * 2 + 1, mid + 1, R, l, r, add);
51     push_up(id);
52 }
53 // 区间查找
54 ll query(int id, int L, int R, int l, int r) {
55     if (l <= L && r >= R) return tree[id];
56     push_down(id, L, R);
57     int mid = (L + R) / 2;
58     ll sum = 0;
59     if (mid >= l) sum += query(id * 2, L, mid, l, r);
60     if (mid < r) sum += query(id * 2 + 1, mid + 1, R, l, r);
61     return sum;
62 }
63 
64 int main() {
65     int n, m;
66     cin >> n >> m;
67     build(1, 1, n);
68     while (m--) {
69         int ty;
70         cin >> ty;
71         if (ty == 1) {
72             int l, r,d;
73             cin >> l >> r >> d;
74             update(1, 1, n, l, r, d);
75         }
76         else {
77             int l, r;
78             cin >> l >>r;
79             cout << query(1, 1, n, l, r) << endl;
80         }
81     }
82     return 0;
83 }