线段树学习笔记

四月 01, 2018 5008

快速查找和修改区间

注：本文包含洛谷 P3372 【模板】线段树 1 题解

线段树模板

前言

  • 什么是线段树？

线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。

  • 线段树的主要用途及好处？

线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN）。

  • 线段树的应用？

最简单的应用就是记录线段是否被覆盖，随时查询当前被覆盖线段的总长度。

代码

基础函数

我们选择一个 O(1) 的取儿子函数：

1
2
3
4
5
6
7
8
9
10
inline int leftChild(int p) {
	return p << 1;
}
// 左子树 

inline int rightChild(int p) {
	return p << 1 | 1;
}
// 右子树

线段树的维护：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void pushUp(int p) {
	t[p] = t[leftChild(p)] + t[rightChild(p)];
}
// 向上维护区间

void pushUpMin(int p) {
	t[p] = std::min(t[leftChild(p)], t[rightChild(p)]);
} 
// 向t[p]下放Min标签

void pushUpMax(int p) {
	t[p] = std::max(t[leftChild(p)], t[rightChild(p)]);
} 
// 向t[p]下放Max标签

递归建树：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef long long int lli;

void buildTree(lli p, lli l, lli r) {
	if (l == r) {
		ans[p] = a[l];
		return;
	}
	// 如果左右区间相同，则必是叶子节点
	lli mid = (l + r) >> 1;
	buildTree(leftChild(p), l, mid);
	buildTree(rightChild(p), mid + 1, r);
	// 递归
	pushUp(p); 
} 
// 递归 + 二分建树

区间修改函数

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

inline void Record(lli p, lli l, lli r, lli k) {
	tag[p] = tag[p] + k;
	ans[p] = ans[p] + k * (r - l + 1);
	// 因为是区间统一改变，所以ans要加元素个数 
}
// 记录当前节点所代表的区间

inline void pushDown(lli p, lli l, lli r) {
	lli mid = (l + r) >> 1;
	Record(leftChild(p), l, mid, tag[p]);
	Record(rightChild(p), mid + 1, r, tag[p]);
	tag[p] = 0;
	// 每次更新两个儿子节点，不断向下传递 
} 

inline void update(lli nl, lli nr, lli l, lli r, lli p, lli k) {
	// 将要修改从 nl 到 nr 的区间
	// l,r 为当前节点所储存的区间 
	// p 为当前节点的编号
	if (nl <= l && r <= nr) {
		ans[p] += k * (r - l + 1);
		tag[p] += k;
		return;
	} 
	pushDown(p, l, r);	
	lli mid = (l + r) >> 1;
	if (nl <= mid) update(nl, nr, l, mid, leftChild(p), k)
	if (nr > mid) update(nl, nr,mid + 1, r, rightChild(p), k);
	pushUp(p);
}
// 更新区间

查询区间函数

1
2
3
4
5
6
7
8
9
10
inline lli query(lli qx, lli qy, lli l, lli r, lli p) {
	lli res = 0;
	if (qx <= l && r <= qy) return ans[p];
	lli mid = (l + r) >> 1;
	pushDown(p, l, r);
	if (qx <= mid) res += query(qx, qy, l, mid, leftChild(p));
	if (mid + 1 <= qy) res += query(qx, qy, mid + 1, r, rightChild(p));
	return res; 
}
// 查询区间

依然采用二分的形式…

洛谷 P3372 题解

题目描述

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

1.将某区间每一个数加上x

2.求出某区间每一个数的和

输入格式

第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。

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

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

操作1： 格式：1 x y k 含义：将区间[x,y]内每个数加上k

操作2： 格式：2 x y 含义：输出区间[x,y]内每个数的和

输出格式

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

输入样例

1
2
3
4
5
6
7
5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4

输出样例

1
2
3
11
8
20

解题思路

就是把上面的函数都复制下来就行了= =

没什么多解释的

注释见上面代码

代码实现

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
93
94
95
96
97
98
99
100
101
102
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
// using namespace std;

typedef long long int ll;
typedef unsigned long long int ull;

const int MAXN = 1000000 + 1;

ull n, m, a[MAXN], ans[MAXN << 2], tag[MAXN << 2];

inline ll ls(ll x) {
	return x << 1; 
}

inline ll rs(ll x) {
	return x << 1 | 1;
}

void scan(){
	scanf("%lld %lld", &n, &m);
	for (ll i = 1;i <= n;i++) {
		scanf("%lld", &a[i]);
	}
}

inline void pushUp(ll p) {
	ans[p] = ans[ls(p)] + ans[rs(p)];
} 

inline void build(ll p, ll l, ll r) {
	tag[p] = 0;
	if (l == r) {
		ans[p] = a[l];
		return; 
	}
	ll mid = (l + r) >> 1;
	build(ls(p), l, mid);
	build(rs(p), mid + 1, r);
	pushUp(p);
}

inline void rec(ll p, ll l, ll r, ll k) {
	tag[p] = tag[p] + k;
	ans[p] = ans[p] + k * (r - l + 1);
}

inline void pushDown(ll p,ll l, ll r) {
	ll mid = (l + r) >> 1;
	rec(ls(p), l, mid, tag[p]);
	rec(rs(p), mid + 1, r, tag[p]);
	tag[p] = 0;
}

inline void update(ll nl, ll nr, ll l, ll r, ll p, ll k) {
	if (nl <= l && r <= nr) {
		ans[p] += k * (r - l + 1);
		tag[p] += k;
		return;
	}
	pushDown(p, l, r);
	ll mid = (l + r) >> 1;
	if (nl <= mid) update(nl, nr, l, mid, ls(p), k);
	if (nr > mid) update(nl, nr, mid + 1, r, rs(p), k);
	pushUp(p);
}

ll query(ll qx, ll qy, ll l, ll r, ll p) {
	ll res = 0;
	if (qx <= l && r <= qy) return ans[p];
	ll mid = (l + r) >> 1;
	pushDown(p, l, r);
	if (qx <= mid) res += query(qx, qy, l, mid, ls(p));
	if (qy > mid) res += query(qx, qy, mid + 1, r, rs(p));
	return res;
}

int main() {
	// ios::sync_with_stdio(false);
	ll a1, b, c, d, e, f;
	scan();
	build(1, 1, n);
	while (m--) {
		scanf("%lld", &a1);
		switch(a1) {
			case 1:{
				scanf("%lld %lld %lld", &b, &c, &d);
				update(b, c, 1, n, 1, d);
				break;
			}
			case 2:{
				scanf("%lld %lld", &e, &f);
				printf("%lld\n", query(e, f, 1, n, 1));	
				break;
			}
		}
	}
	return 0;
}
// 注意一下，stdio 和 iostream 混用会出现很多奇怪的bug！