线段树是这样的一棵
完全二叉树，它的每个节点维护着两个变量start和end，另外还有一些根据特定应用需要维护的值，我们设为x，则它代表着区间[start, end之间的某个特征为x，比如求最值问题，如果有这样一类问题，比如我们需要给定若干区间[a
i, b
i]，需要查询这些区间中的最大值（或者最小值），那么线段树就是最佳选择，因为它每次的查询都只需要耗费O(log(b
i - a
i))时间，效率非常高。线段树一般采用标准的二叉树结构实现，维护着left和right指针，以及start和end两个区间边界，还有一些和需求有关的域。
下面举几个例子，toj的2250题，excellent，题意就是有若干个队伍，然后进行三次比赛，如果对某支队伍i，不存在另外一只队伍j在三次比赛中的排名都比i的排名高，则认为队伍i是excellent的。输入是三次比赛的所有排名情况，输出是excellent队伍的个数。暴力方法不讲了，由于队伍数量比较多，所以会超时。下面介绍线段树方法，首先我们知道第一次比赛取得第一名的队伍a肯定是excellent的，对于第二名队伍b，我们需要知道队伍a是否在第二次排名和第三次排名中的名词都比b高，如果不是，那么b也是excellent，同理，对于第一次比赛中取得第i名的队伍f[i]，我们需要知道是否有一个队伍f[j] j < i，在第二次比赛和第三次比赛中的名次都比f[i]队伍高。那么如何才能加速查询呢？我们可以这样使用线段树做：以在第二次比赛中的名次为区间，以第三次比赛的最小名次为特征值。并且初始情况下线段树为空，每当发现一个excellent队伍则把它插入到线段树中，因为仔细想一下不难发现不是excellent的队伍必定会存在一个已经在线段树中的队伍，它的第三次排名比该队伍小。因此不是excellent的队伍不需要插入到线段树中。上面的思想非常巧妙，代码实现倒是比较简单，如下：
1 #include <cstdio>
2
3 #define MAX 0x7fffffff
4
5 //first[i]代表第一次比赛第i名的队伍编号
6 int first[100005];
7 //second_and_third[i].second
8 //second_and_third[i].third
9 //上面分别代表第i号队伍在第二次、第三次比赛中取得的名次
10 struct st {
11 int second;
12 int third;
13 }second_and_third[100005];
14
15 struct segment_tree {
16 int min_third;
17 int start;
18 int end;
19 segment_tree *left;
20 segment_tree *right;
21 };
22
23 segment_tree *build(int start, int end) {
24 segment_tree *p = new segment_tree;
25 p->start = start;
26 p->end = end;
27 p->min_third = MAX;
28 if (start == end) {
29 p->left = NULL;
30 p->right = NULL;
31 return p;
32 }
33 p->left = build(start, (start + end) / 2);
34 p->right = build((start + end) / 2 + 1, end);
35 return p;
36 }
37
38 void insert(int second_rank, int third_rank, segment_tree *p) {
39 if (!p || second_rank < p->start || second_rank > p->end) {
40 return;
41 }
42 if (p->min_third > third_rank) {
43 p->min_third = third_rank;
44 }
45 insert(second_rank, third_rank, p->left);
46 insert(second_rank, third_rank, p->right);
47 }
48
49 int check(int start, int end, segment_tree *p) {
50 if (!p || start > p->end || end < p->start) {
51 return MAX;
52 }
53 if (start <= p->start && end >= p->end) {
54 return p->min_third;
55 }
56 int left = check(start, end, p->left);
57 int right = check(start, end, p->right);
58 return left < right ? left : right;
59 }
60
61 void destroy(segment_tree *p) {
62 if (!p) {
63 return;
64 }
65 destroy(p->left);
66 destroy(p->right);
67 delete p;
68 }
69
70 int main() {
71 int n;
72 while (scanf("%d", &n), n) {
73 int i, tmp;
74 for (i = 1; i <= n; ++i) {
75 scanf("%d", &first[i]);
76 }
77 for (i = 1; i <= n; ++i) {
78 scanf("%d", &tmp);
79 second_and_third[tmp].second = i;
80 }
81 for (i = 1; i <= n; ++i) {
82 scanf("%d", &tmp);
83 second_and_third[tmp].third = i;
84 }
85 segment_tree *root = build(1, n);
86 int count = 0;
87 for (i = 1; i <= n; ++i) {
88 int second = second_and_third[first[i]].second;
89 int third = second_and_third[first[i]].third;
90 int min_third = check(1, second, root);
91 if (min_third >= third) {
92 count++;
93 insert(second, third, root);
94 }
95 }
96 printf("%d\n", count);
97 delete root;
98 }
99 return 0;
100 }
下面看另外一个例题：
此题摘自poj2352(stars)，题意：在平面坐标中，有一些stars，每个stars都有整数坐标，且坐标范围为[0, 32000]，stars总数量<=15000。每个星星都属于一个level，如果满足{x <=xi && y <= yi}的stars的数量为k个（每个点仅能有一个星星，即星星不能重叠），则我们说(xi, yi)这个star的level为k，现在要输出每个level拥有星星的数量。该题一个比较特殊的地方是输入数据已经是按照纵坐标递增排序了，若纵坐标相等，则按照很坐标递增排序，所以不需要我们手动排序。现在分析题目：
由于输入的递增特性，首先我们可以知道，对每个星星i，满足{x <=xi && y <= yi}条件的(x, y)的星星必然是在星星i之前输入的，不会是i输入之后输入的星星，因为在y输入之后的星星y坐标肯定比星星i的y坐标大，或者y坐标相等而x坐标大，这样都不满足条件。该题中的y坐标实际上没有用处，
因此这题就变成从第i个输入a中找出从第1~i - 1的输入中比a小的数有多少个的问题了。这种问题用线段树来解时间复杂度非常完美，但是由于线段树的空间复杂度一直被人诟病，所以这样做的空间复杂度会有些高。我们的线段树的每个节点都保存着常规域left和right指针，以及该节点所表示的区间的start和end，最后的特征值我们保存[start, end]区间中的节点数。这样，当第i个节点a来到时，我们需要向线段树中插入，插入函数返回值即当前已经输入的星星中x坐标小于a的个数。这里是代码的核心，如果a < start那么我们可以直接返回0了；否则如果a > end，则我们可以直接返回当前节点的[start, end]中所有的节点个数了，因为在[start, end]的区间中的所有节点的x坐标必定都小于a，因为a > end（这不废话嘛……）；否则若a == start && a == end，则说明当前节点已经为叶子节点了，那么直接返回当前节点的星星数量，然后再将a插入到该节点，即当前节点的星星数量加1；最后的情况肯定就是a在区间[start, end]之间了，这时候递归向左子树和右子树插入即可，返回值相加即是[start, end]中小于a的星星的数量。说的比较罗嗦，看代码吧：
1 #include <cstdio>
2 #include <cstdlib>
3
4 #define MAX 15005
5
6 int stars_x[MAX];
7 int levels[MAX];
8
9 struct segment_tree {
10 int start;
11 int end;
12 int node_num;
13 segment_tree *left;
14 segment_tree *right;
15 };
16
17 segment_tree *create_segment_tree(int start, int end) {
18 segment_tree *p = (segment_tree *)malloc(sizeof(segment_tree));
19 p->start = start;
20 p->end = end;
21 p->node_num = 0;
22 if (start == end) {
23 p->left = p->right = NULL;
24 } else {
25 p->left = create_segment_tree(start, (end + start) / 2);
26 p->right = create_segment_tree((end + start) / 2 + 1, end);
27 }
28 return p;
29 }
30
31 int insert_into_segment_tree(int x, segment_tree *t) {
32 if (!t || x < t->start) {
33 return 0;
34 }
35 if (x > t->end) {
36 return t->node_num;
37 }
38 if (x == t->start && x == t->end) {
39 return t->node_num++;
40 }
41 t->node_num++;
42 int left_num = insert_into_segment_tree(x, t->left);
43 int right_num = insert_into_segment_tree(x, t->right);
44 return left_num + right_num;
45 }
46 void release(segment_tree *p) {
47 if (!p) {
48 return;
49 }
50 release(p->left);
51 release(p->right);
52 free(p);
53 }
54
55 int main() {
56 int n;
57 scanf("%d", &n);
58 int i, max_x = -1, tmpy;
59 for (i = 0; i < n; ++i) {
60 scanf("%d%d", &stars_x[i], &tmpy);
61 if (max_x < stars_x[i]) {
62 max_x = stars_x[i];
63 }
64 levels[i] = 0;
65 }
66
67 segment_tree *root = create_segment_tree(0, max_x + 2);
68
69 for (i = 0; i < n; ++i) {
70 int num = insert_into_segment_tree(stars_x[i], root);
71 levels[num]++;
72 }
73
74 for (i = 0; i < n; ++i) {
75 printf("%d\n", levels[i]);
76 }
77
78 release(root);
79 return 0;
80 }
注意如果直接拿这个代码提交会TLE，主要时间其实耗费在了建线段树上了， 因为我们采用的是用malloc从堆中分配，没开辟一个节点就调用一次malloc函数，非常耗费时间，我第一次提交就TLE了，不过可以不需要把其改成用数组表示线段树的形式，可以直接不管内存释放，直接把release(root)语句删除，然后把release()函数删除，这样提交的代码恰好1000ms，太惊险了。如果用数组表示线段树的话相信时间会快很多，这就是oj的特点。另外需要说明的是把malloc替换成new的话会超过1000ms，超时，说明还是用malloc效率高一些。
posted on 2012-09-13 14:31
myjfm 阅读(1248)
评论(0) 编辑 收藏 引用 所属分类:
算法基础