线段树模板

Posted on | In | | Visitors:
Words count in article: 857

线段树模板

最近时间太紧了鸭，算法细节就不写了吧，就留个模板吧 : (

线段树就是一棵树，树上的每个节点对应一个线段（也就是一个区间），同一层的节点所代表的区间相互不会重叠，并且加起来是一个连续的区间，叶子节点是区间的单位长度，不可再分~

1. 例题

题目链接：洛谷 P3372 【模板】线段树 1

题目描述

如题，已知一个数列，你需要进行下面两种操作：

  1. 将某区间每一个数加上 k。
  2. 求出某区间每一个数的和。

输入格式

第一行包含两个整数 n, m，分别表示该数列数字的个数和操作的总个数。

第二行包含 n 个用空格分隔的整数，其中第 i 个数字表示数列第 i 项的初始值。

接下来 m 行每行包含 3 或 4 个整数，表示一个操作，具体如下：

  1. 1 x y k：将区间 [x, y] 内每个数加上 k。
  2. 2 x y：输出区间 [x, y] 内每个数的和。

输出格式

输出包含若干行整数，即为所有操作 2 的结果。

具体样例参考洛谷原题哟~

2. 解题模板

上模板~

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
92
#include<iostream>
#include<algorithm>
using namespace std;
#define N 100
typedef long long int LL;
struct node {	// 每个树节点记录此时的和与待加数
	LL sum;
	LL add;
};
LL arr[N] = { 0 };
node tree[4 * N];
int n;
void buildTree(int l, int r, int root) {	// 常规的建树过程
	if (l == r) {	// 递归到叶子节点
		tree[root].sum = arr[l];
		tree[root].add = 0;
	}
	else {
		int mid = (l + r) / 2;
		buildTree(l, mid, 2 * root);
		buildTree(mid + 1, r, 2 * root + 1);
		// 建好子树后，求解此时的树根节点
		tree[root].sum = tree[2 * root].sum + tree[2 * root + 1].sum;
		tree[root].add = 0;
	}
}
// 为区间加数
void treeAdd(int k, int ll, int rr, int l, int r, int root) {
	if (ll <= l && rr >= r) {
		// 节点区间完全在待加区间中
		tree[root].add += k;
	}
	else {
		int mid = (l + r) / 2;
		// 向下更新时，需要消灭掉根节点的add
		tree[root].sum += (r - l + 1) * tree[root].add;
		tree[2 * root].add += tree[root].add;
		tree[2 * root + 1].add += tree[root].add;
		tree[root].add = 0;
		// 向下更新
		if (ll <= mid) {
			// 记得给根节点的sum加上
			tree[root].sum += (min(rr, mid) - max(ll, l) + 1) * k;
			treeAdd(k, ll, rr, l, mid, 2 * root);
		}
		if(rr > mid) {
			tree[root].sum += (min(rr, r) - max(ll, mid + 1) + 1) * k;
			treeAdd(k, ll, rr, mid + 1, r, 2 * root + 1);
		}
	}
}
// 查找区间和，这个过程和更新过程非常类似
LL treeSearch(int ll, int rr, int l, int r, int root) {
	if (ll <= l && rr >= r) {
		return tree[root].sum + (r - l + 1) * tree[root].add;
	}
	else {
		int mid = (l + r) / 2;
		LL temp = 0;
		tree[root].sum += (r - l + 1) * tree[root].add;
		tree[2 * root].add += tree[root].add;
		tree[2 * root + 1].add += tree[root].add;
		tree[root].add = 0;
		if (ll <= mid) {
			temp += treeSearch(ll, rr, l, mid, 2 * root);
		}
		if (rr > mid) {
			temp += treeSearch(ll, rr, mid + 1, r, 2 * root + 1);
		}
		return temp;
	}
}
int main() {
	int m, op, x, y, k;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
	buildTree(1, n, 1);
	for (int i = 0; i < m; i++) {
		cin >> op;
		if (op == 1) {
			cin >> x >> y >> k;
			treeAdd(k, x, y, 1, n, 1);
		}
		else {
			cin >> x >> y;
			cout << treeSearch(x, y, 1, n, 1)<<endl;
		}
	}
	return 0;
}