什么是线段树
线段树，是一种树形结构，它的各个节点都保存的是一条线段。线段树主要是解决动态查询的问题，使用二叉树的结构后，它的操作基本的复杂度为O(logn).
线段树的每个节点表示一个区间，其左右子树表示该节点的左半区间和右半区间。比如说，一个节点为[a, b],中间的值为c=(a+b)/2,左子节点表示的区间为[a,c],右子节点表示的区间为[c+1, b]
线段树要解决的问题
问题描述：在一个数组arr[0…n-1]中，查找某个区间[a,b]上的最小值，其中数组的大小固定，但是数组中的元素可以更新。
如果使用遍历数组的方法，时间复杂度为O(n),空间复杂度为O(1).当数据量很大时，不可取。如果用一个二维数组来提前计算好区间[i,j]的最小值，那么预处理时间复杂度为O(n^2),空间复杂度也为O(n^2)。
我们可以用线段树解决这个问题：预处理时间为O(n),查询和更新操作为O(log(n)),需要的额外空间为O(n).为此我们构建一个二叉树：
- 叶子节点是数组中的元素
- 非叶子节点表示其所有子节点的最小值
比如对于一个数组[2,5,1,4,9,3]构造的二叉树为：
由于线段树的父节点区间是平均分割到左右子树，因此线段树是完全二叉树，对于包含n个叶子节点的完全二叉树，它一定有n-1个非叶节点，总共2n-1个节点，因此存储线段是需要的空间复杂度是O(n)。
操作
创建线段树
线段树可以直接使用数组存储。节点的结构为：
1
2
3
4
struct SegTreeNode
{
int val;
}定义包含n个节点的线段树 SegTreeNode segTree[n]，segTree[0]表示根节点。那么对于节点segTree[i]，它的左孩子是segTree[2*i+1],右孩子是segTree[2*i+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
const int MAXNUM = 1000;
struct SegTreeNode
{
int val;
}segTree[MAXNUM];//定义线段树
/*
功能：构建线段树
root：当前线段树的根节点下标
arr: 用来构造线段树的数组
istart：数组的起始位置
iend：数组的结束位置
*/
void build(int root, int arr[], int istart, int iend)
{
if(istart == iend)//叶子节点
segTree[root].val = arr[istart];
else
{
int mid = (istart + iend) / 2;
build(root*2+1, arr, istart, mid);//递归构造左子树
build(root*2+2, arr, mid+1, iend);//递归构造右子树
//根据左右子树根节点的值，更新当前根节点的值
segTree[root].val = min(segTree[root*2+1].val, segTree[root*2+2].val);
}
}查询线段树
已经构建好了线段树，那么怎样在它上面超找某个区间的最小值呢？查询的思想是选出一些区间，使他们相连后恰好涵盖整个查询区间，因此线段树适合解决“相邻的区间的信息可以被合并成两个区间的并区间的信息”的问题。代码如下，具体见代码解释
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/*
功能：线段树的区间查询
root：当前线段树的根节点下标
[nstart, nend]: 当前节点所表示的区间
[qstart, qend]: 此次查询的区间
*/
int query(int root, int nstart, int nend, int qstart, int qend)
{
//查询区间和当前节点区间没有交集
if(qstart > nend || qend < nstart)
return INFINITE;
//当前节点区间包含在查询区间内
if(qstart <= nstart && qend >= nend)
return segTree[root].val;
//分别从左右子树查询，返回两者查询结果的较小值
int mid = (nstart + nend) / 2;
return min(query(root*2+1, nstart, mid, qstart, qend),
query(root*2+2, mid + 1, nend, qstart, qend));
}举例说明（对照上面的二叉树）：
1、当我们要查询区间[0,2]的最小值时，从根节点开始，要分别查询左右子树，查询左子树时节点区间[0,2]包含在查询区间[0,2]内，返回当前节点的值1，查询右子树时，节点区间[3,5]和查询区间[0,2]没有交集，返回正无穷INFINITE，查询结果取两子树查询结果的较小值1，因此结果是1.
2、查询区间[0,3]时，从根节点开始，查询左子树的节点区间[0,2]包含在区间[0,3]内，返回当前节点的值1；查询右子树时，继续递归查询右子树的左右子树，查询到非叶节点4时，又要继续递归查询：叶子节点4的节点区间[3,3]包含在查询区间[0,3]内，返回4，叶子节点9的节点区间[4,4]和[0,3]没有交集，返回INFINITE,因此非叶节点4返回的是min(4, INFINITE) = 4，叶子节点3的节点区间[5,5]和[0,3]没有交集，返回INFINITE,因此非叶节点3返回min(4, INFINITE) = 4, 因此根节点返回 min(1,4) = 1。
单节点更新
单节点更新是指只更新线段树的某个叶子节点的值，但是更新叶子节点会对其父节点的值产生影响，因此更新子节点后，要回溯更新其父节点的值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*
功能：更新线段树中某个叶子节点的值
root：当前线段树的根节点下标
[nstart, nend]: 当前节点所表示的区间
index: 待更新节点在原始数组arr中的下标
addVal: 更新的值（原来的值加上addVal）
*/
void updateOne(int root, int nstart, int nend, int index, int addVal)
{
if(nstart == nend)
{
if(index == nstart)//找到了相应的节点，更新之
segTree[root].val += addVal;
return;
}
int mid = (nstart + nend) / 2;
if(index <= mid)//在左子树中更新
updateOne(root*2+1, nstart, mid, index, addVal);
else updateOne(root*2+2, mid+1, nend, index, addVal);//在右子树中更新
//根据左右子树的值回溯更新当前节点的值
segTree[root].val = min(segTree[root*2+1].val, segTree[root*2+2].val);
}比如我们要更新叶子节点4（addVal = 6）,更新后值变为10，那么其父节点的值从4变为9，非叶结点3的值更新后不变，根节点更新后也不变。
区间更新
区间更新是指更新某个区间内的叶子节点的值，因为涉及到的叶子节点不止一个，而叶子节点会影响其相应的非叶父节点，那么回溯需要更新的非叶子节点也会有很多，如果一次性更新完，操作的时间复杂度肯定不是O(lgn)，例如当我们要更新区间[0,3]内的叶子节点时，需要更新出了叶子节点3,9外的所有其他节点。为此引入了线段树中的延迟标记概念，这也是线段树的精华所在。
延迟标记：每个节点新增加一个标记，记录这个节点是否进行了某种修改(这种修改操作会影响其子节点)，对于任意区间的修改，我们先按照区间查询的方式将其划分成线段树中的节点，然后修改这些节点的信息，并给这些节点标记上代表这种修改操作的标记。在修改和查询的时候，如果我们到了一个节点p，并且决定考虑其子节点，那么我们就要看节点p是否被标记，如果有，就要按照标记修改其子节点的信息，并且给子节点都标上相同的标记，同时消掉节点p的标记。
因此需要在线段树结构中加入延迟标记域，本文例子中我们加入标记与addMark，表示节点的子孙节点在原来的值的基础上加上addMark的值，同时还需要修改创建函数build 和 查询函数 query，其中区间更新的函数为update，代码如下：
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
const int INFINITE = INT_MAX;
const int MAXNUM = 1000;
struct SegTreeNode
{
int val;
int addMark;//延迟标记
}segTree[MAXNUM];//定义线段树
/*
功能：构建线段树
root：当前线段树的根节点下标
arr: 用来构造线段树的数组
istart：数组的起始位置
iend：数组的结束位置
*/
void build(int root, int arr[], int istart, int iend)
{
segTree[root].addMark = 0;//----设置标延迟记域
if(istart == iend)//叶子节点
segTree[root].val = arr[istart];
else
{
int mid = (istart + iend) / 2;
build(root*2+1, arr, istart, mid);//递归构造左子树
build(root*2+2, arr, mid+1, iend);//递归构造右子树
//根据左右子树根节点的值，更新当前根节点的值
segTree[root].val = min(segTree[root*2+1].val, segTree[root*2+2].val);
}
}
/*
功能：当前节点的标志域向孩子节点传递
root: 当前线段树的根节点下标
*/
void pushDown(int root)
{
if(segTree[root].addMark != 0)
{
//设置左右孩子节点的标志域，因为孩子节点可能被多次延迟标记又没有向下传递
//所以是 “+=”
segTree[root*2+1].addMark += segTree[root].addMark;
segTree[root*2+2].addMark += segTree[root].addMark;
//根据标志域设置孩子节点的值。因为我们是求区间最小值，因此当区间内每个元
//素加上一个值时，区间的最小值也加上这个值
segTree[root*2+1].val += segTree[root].addMark;
segTree[root*2+2].val += segTree[root].addMark;
//传递后，当前节点标记域清空
segTree[root].addMark = 0;
}
}
/*
功能：线段树的区间查询
root：当前线段树的根节点下标
[nstart, nend]: 当前节点所表示的区间
[qstart, qend]: 此次查询的区间
*/
int query(int root, int nstart, int nend, int qstart, int qend)
{
//查询区间和当前节点区间没有交集
if(qstart > nend || qend < nstart)
return INFINITE;
//当前节点区间包含在查询区间内
if(qstart <= nstart && qend >= nend)
return segTree[root].val;
//分别从左右子树查询，返回两者查询结果的较小值
pushDown(root); //----延迟标志域向下传递
int mid = (nstart + nend) / 2;
return min(query(root*2+1, nstart, mid, qstart, qend),
query(root*2+2, mid + 1, nend, qstart, qend));
}
/*
功能：更新线段树中某个区间内叶子节点的值
root：当前线段树的根节点下标
[nstart, nend]: 当前节点所表示的区间
[ustart, uend]: 待更新的区间
addVal: 更新的值（原来的值加上addVal）
*/
void update(int root, int nstart, int nend, int ustart, int uend, int addVal)
{
//更新区间和当前节点区间没有交集
if(ustart > nend || uend < nstart)
return ;
//当前节点区间包含在更新区间内
if(ustart <= nstart && uend >= nend)
{
segTree[root].addMark += addVal;
segTree[root].val += addVal;
return ;
}
pushDown(root); //延迟标记向下传递
//更新左右孩子节点
int mid = (nstart + nend) / 2;
update(root*2+1, nstart, mid, ustart, uend, addVal);
update(root*2+2, mid+1, nend, ustart, uend, addVal);
//根据左右子树的值回溯更新当前节点的值
segTree[root].val = min(segTree[root*2+1].val, segTree[root*2+2].val);
}区间更新举例说明：当我们要对区间[0,2]的叶子节点增加2，利用区间查询的方法从根节点开始找到了非叶子节点[0-2]，把它的值设置为1+2 = 3，并且把它的延迟标记设置为2，更新完毕；当我们要查询区间[0,1]内的最小值时，查找到区间[0,2]时，发现它的标记不为0，并且还要向下搜索，因此要把标记向下传递，把节点[0-1]的值设置为2+2 = 4，标记设置为2，节点[2-2]的值设置为1+2 = 3，标记设置为2（其实叶子节点的标志是不起作用的，这里是为了操作的一致性），然后返回查询结果：[0-1]节点的值4；当我们再次更新区间[0,1]（增加3）时，查询到节点[0-1],发现它的标记值为2，因此把它的标记值设置为2+3 = 5，节点的值设置为4+3 = 7；
其实当区间更新的区间左右值相等时（[i,i]），就相当于单节点更新，单节点更新只是区间更新的特例。
例题poj3468
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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
/*
poj 3468-线段树
http://poj.org/problem?id=3468
You have N integers, A1, A2, ... , AN. You need to deal with two kinds of operations.
One type of operation is to add some given number to each number in a given interval.
The other is to ask for the sum of numbers in a given interval.
题目大意：对于给定的一组数，有两种操作：求某个区间的和以及更新某个区间的值
解题思路：用线段树。
*/
#include <cstdio>
#include <algorithm>
using namespace std;
//#pragma warning(disable:4996)
#define ll long long
inline int L(int r)
{
return r << 1;
}
inline int R(int r)
{
return (r << 1) + 1;
}
inline int MID(int l, int r)
{
return (l + r) >> 1;
}
const int max_n = 1e5 + 10;
ll sum;
//树的节点结构：线段的起点left和重点right
//[left, right]的和以及更新值add
struct node
{
int left;
int right;
ll val;
ll add;
}tree[max_n<<2];//interval tree
ll arr[max_n << 2];//init array
//建一棵树
void Built(int l, int r, int root)
{
tree[root].left = l;
tree[root].right = r;
tree[root].add = 0;
if (l == r)
{
tree[root].val = arr[l];
return;
}
else
{
//递归构建左右子树
int mid = MID(l, r);
Built(l, mid, L(root));
Built(mid + 1, r, R(root));
//更新root
tree[root].val = tree[L(root)].val + tree[R(root)].val;
}
}
void Update(int root)
{
//更新子树
if (tree[root].add)
{
tree[L(root)].add += tree[root].add;//
tree[R(root)].add += tree[root].add;//
tree[L(root)].val += (tree[L(root)].right - tree[L(root)].left + 1)*tree[root].add;
tree[R(root)].val += (tree[R(root)].right - tree[R(root)].left + 1)*tree[root].add;
tree[root].add = 0;
}
}
//加上v
void Add(int l, int r, ll v, int root)
{
if (l <= tree[root].left && r >= tree[root].right)
{
tree[root].add += v;
tree[root].val += v*(tree[root].right - tree[root].left + 1);
return;
}
else
{
//分别在左右子树上增加
Update(root);
if (tree[root].left == tree[root].right)
return;
int mid = MID(tree[root].left, tree[root].right);
if (l > mid)
Add(l, r, v, R(root));
else if (r <= mid)
Add(l, r, v, L(root));
else
{
Add(l, mid, v, L(root));
Add(mid + 1, r, v, R(root));
}
tree[root].val = tree[L(root)].val + tree[R(root)].val;
}
}
void Solve(int l, int r, int root)
{
if (l <= tree[root].left && r >= tree[root].right)
{
sum += tree[root].val;
return;
}
else {
Update(root);
if (tree[root].left == tree[root].right)
return;
int mid = MID(tree[root].left, tree[root].right);
if (l > mid)
Solve(l, r, R(root));
else if (r <= mid)
Solve(l, r, L(root));
else
{
Solve(l, mid, L(root));
Solve(mid + 1, r, R(root));
}
}
}
int main()
{
//freopen("poj3468.txt", "r", stdin);
int m, n;
while (scanf("%d %d", &m, &n) != EOF)
{
for (int i = 1; i <= m; ++i)
scanf("%lld", arr + i);
//建树
Built(1, m, 1);
char c[2];
while (n--)
{
scanf("%s", c);
if ('C' == c[0])
{
int l, f;
ll v;
scanf("%d %d %lld", &l, &f, &v);
Add(l, f, v, 1);
}
else
{
int l, f;
scanf("%d %d", &l, &f);
sum = 0;
Solve(l, f, 1);
printf("%lldn", sum);
}
}
}
}参考
[1]http://www.cnblogs.com/TenosDoIt/p/3453089.html
[2]http://www.cppblog.com/cxiaojia/archive/2011/11/22/poj3468.html
最后
以上就是碧蓝钥匙最近收集整理的关于poj3468-线段树详解的全部内容，更多相关poj3468-线段树详解内容请搜索靠谱客的其他文章。
发表评论 取消回复