线段树详解与实现

1 #include
2 #include
3 #include
4 #include
5 #include
6 using namespace std;
7
8 const int MAXN = 200005;
9
10 int n, m, op, a, b;
11 long long val;
12 int arr[MAXN];
13
14 struct SegmentTree {
15 int left, right;
16 long long sum;
17 int lazy;
18 } tree[4 * MAXN];
19
20 void pushUp(int node) {
21 tree[node].sum = tree[node * 2].sum + tree[node * 2 + 1].sum;
22 }
23
24 void pushDown(int node) {
25 if (tree[node].lazy) {
26 tree[node * 2].lazy += tree[node].lazy;
27 tree[node * 2 + 1].lazy += tree[node].lazy;
28 tree[node * 2].sum += (tree[node * 2].right - tree[node * 2].left + 1) * tree[node].lazy;
29 tree[node * 2 + 1].sum += (tree[node * 2 + 1].right - tree[node * 2 + 1].left + 1) * tree[node].lazy;
30 tree[node].lazy = 0;
31 }
32 }
33
34 void build(int node, int start, int end) {
35 tree[node].left = start;
36 tree[node].right = end;
37 tree[node].lazy = 0;
38 if (start == end) {
39 tree[node].sum = arr[start];
40 return;
41 }
42 int mid = (start + end) / 2;
43 build(node * 2, start, mid);
44 build(node * 2 + 1, mid + 1, end);
45 pushUp(node);
46 }
47
48 void update(int node, int start, int end, long long value) {
49 if (tree[node].left >= start && tree[node].right <= end) {
50 tree[node].lazy += value;
51 tree[node].sum += (tree[node].right - tree[node].left + 1) * value;
52 return;
53 }
54 pushDown(node);
55 int mid = (tree[node].left + tree[node].right) / 2;
56 if (start <= mid) update(node * 2, start, end, value);
57 if (end > mid) update(node * 2 + 1, start, end, value);
58 pushUp(node);
59 }
60
61 long long query(int node, int start, int end) {
62 if (tree[node].left >= start && tree[node].right <= end) return tree[node].sum;
63 pushDown(node);
64 int mid = (tree[node].left + tree[node].right) / 2;
65 long long result = 0;
66 if (start <= mid) result += query(node * 2, start, end);
67 if (end > mid) result += query(node * 2 + 1, start, end);
68 return result;
69 }
70
71 int main() {
72 cin >> n;
73 for (int i = 1; i <= n; i++) cin >> arr[i];
74 build(1, 1, n);
75 cin >> m;
76 for (int i = 1; i <= m; i++) {
77 cin >> op;
78 if (op == 1) {
79 cin >> a >> b >> val;
80 update(1, a, b, val);
81 } else if (op == 2) {
82 cin >> a >> b;
83 cout <84 }
85 }
86 return 0;
87 }