線段樹是這樣的一棵
完全二叉樹，它的每個節點維護著兩個變量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 閱讀(1289)
評論(0) 編輯 收藏 引用 所屬分類:
算法基礎