「模版」线段树

发表于 | 分类于

附上线段树模版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <cstdio>
#include <iostream>
#define DEBUG(x) std::cerr << #x << "=" << x << std::endl
const int N_MAX = 100007;
template <class T>
struct SegT{
	struct Node {
		int l, r;
		T sum, tag;
	}node[4 * N_MAX];
	int lc(int x) {
		return x << 1;
	}
	int rc(int x) {
		return x << 1 | 1;
	}
	void build(int l, int r, int x = 1) {
		node[x].l = l; node[x].r = r;
		if(l == r) return;
		int mid = (l + r) >> 1;
		build(l, mid, lc(x));
		build(mid + 1, r, rc(x));
	}
	void update(int x, T d) {
		node[x].tag += d;
		node[x].sum += (node[x].r - node[x].l + 1) * d;
	}
	void push_down(int x) {
		if(node[x].tag) {
			update(lc(x), node[x].tag);
			update(rc(x), node[x].tag);
			node[x].tag = 0;
		}
	}
	void push_up(int x) {
		node[x].sum = node[lc(x)].sum + node[rc(x)].sum;
	}
	void add(int l, int r, T d, int x = 1) {
		if(l > node[x].r || r < node[x].l) return;
		if(l <= node[x].l && r >= node[x].r) return update(x, d);
		push_down(x);
		add(l, r, d, lc(x));
		add(l, r, d, rc(x));
		push_up(x);
	}
	T query(int l, int r, int x = 1) {
		if(node[x].l > r || node[x].r < l) return 0;
		if(l <= node[x].l && r >= node[x].r) return node[x].sum;
		return push_down(x), query(l, r, lc(x)) + query(l, r, rc(x));
	}
};
SegT<long long>s;
int main(int argc, char *argv[]) {
	int n, m;
	scanf("%d", &n);
	s.build(1, n);
	for(int i = 1; i <= n; i++) {
		int x;
		scanf("%d", &x);
		s.add(i, i, x);
	}
	scanf("%d", &m);
	while(m --) {
		int op;
		scanf("%d", &op); 
		if(op == 1){
			int l, r, d;
			scanf("%d%d%d", &l, &r, &d);
			s.add(l, r, d);
		}
		if( op == 2) {
			int l, r;
			scanf("%d%d", &l, &r);
			printf("%lld\n", s.query(l, r));
		}
	}
	return 0;
}