線段樹是這樣的一棵
完全二叉樹，它的每個(gè)節(jié)點(diǎn)維護(hù)著兩個(gè)變量start和end，另外還有一些根據(jù)特定應(yīng)用需要維護(hù)的值，我們設(shè)為x，則它代表著區(qū)間[start, end之間的某個(gè)特征為x，比如求最值問題，如果有這樣一類問題，比如我們需要給定若干區(qū)間[a
i, b
i]，需要查詢這些區(qū)間中的最大值（或者最小值），那么線段樹就是最佳選擇，因?yàn)樗看蔚牟樵兌贾恍枰馁M(fèi)O(log(b
i - a
i))時(shí)間，效率非常高。線段樹一般采用標(biāo)準(zhǔn)的二叉樹結(jié)構(gòu)實(shí)現(xiàn)，維護(hù)著left和right指針，以及start和end兩個(gè)區(qū)間邊界，還有一些和需求有關(guān)的域。
下面舉幾個(gè)例子，toj的2250題，excellent，題意就是有若干個(gè)隊(duì)伍，然后進(jìn)行三次比賽，如果對(duì)某支隊(duì)伍i，不存在另外一只隊(duì)伍j在三次比賽中的排名都比i的排名高，則認(rèn)為隊(duì)伍i是excellent的。輸入是三次比賽的所有排名情況，輸出是excellent隊(duì)伍的個(gè)數(shù)。暴力方法不講了，由于隊(duì)伍數(shù)量比較多，所以會(huì)超時(shí)。下面介紹線段樹方法，首先我們知道第一次比賽取得第一名的隊(duì)伍a肯定是excellent的，對(duì)于第二名隊(duì)伍b，我們需要知道隊(duì)伍a是否在第二次排名和第三次排名中的名詞都比b高，如果不是，那么b也是excellent，同理，對(duì)于第一次比賽中取得第i名的隊(duì)伍f[i]，我們需要知道是否有一個(gè)隊(duì)伍f[j] j < i，在第二次比賽和第三次比賽中的名次都比f[i]隊(duì)伍高。那么如何才能加速查詢呢？我們可以這樣使用線段樹做：以在第二次比賽中的名次為區(qū)間，以第三次比賽的最小名次為特征值。并且初始情況下線段樹為空，每當(dāng)發(fā)現(xiàn)一個(gè)excellent隊(duì)伍則把它插入到線段樹中，因?yàn)樽屑?xì)想一下不難發(fā)現(xiàn)不是excellent的隊(duì)伍必定會(huì)存在一個(gè)已經(jīng)在線段樹中的隊(duì)伍，它的第三次排名比該隊(duì)伍小。因此不是excellent的隊(duì)伍不需要插入到線段樹中。上面的思想非常巧妙，代碼實(shí)現(xiàn)倒是比較簡單，如下：
1 #include <cstdio>
2
3 #define MAX 0x7fffffff
4
5 //first[i]代表第一次比賽第i名的隊(duì)伍編號(hào)
6 int first[100005];
7 //second_and_third[i].second
8 //second_and_third[i].third
9 //上面分別代表第i號(hào)隊(duì)伍在第二次、第三次比賽中取得的名次
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 }
下面看另外一個(gè)例題：
此題摘自poj2352(stars)，題意：在平面坐標(biāo)中，有一些stars，每個(gè)stars都有整數(shù)坐標(biāo)，且坐標(biāo)范圍為[0, 32000]，stars總數(shù)量<=15000。每個(gè)星星都屬于一個(gè)level，如果滿足{x <=xi && y <= yi}的stars的數(shù)量為k個(gè)（每個(gè)點(diǎn)僅能有一個(gè)星星，即星星不能重疊），則我們說(xi, yi)這個(gè)star的level為k，現(xiàn)在要輸出每個(gè)level擁有星星的數(shù)量。該題一個(gè)比較特殊的地方是輸入數(shù)據(jù)已經(jīng)是按照縱坐標(biāo)遞增排序了，若縱坐標(biāo)相等，則按照很坐標(biāo)遞增排序，所以不需要我們手動(dòng)排序。現(xiàn)在分析題目：
由于輸入的遞增特性，首先我們可以知道，對(duì)每個(gè)星星i，滿足{x <=xi && y <= yi}條件的(x, y)的星星必然是在星星i之前輸入的，不會(huì)是i輸入之后輸入的星星，因?yàn)樵趛輸入之后的星星y坐標(biāo)肯定比星星i的y坐標(biāo)大，或者y坐標(biāo)相等而x坐標(biāo)大，這樣都不滿足條件。該題中的y坐標(biāo)實(shí)際上沒有用處，
因此這題就變成從第i個(gè)輸入a中找出從第1~i - 1的輸入中比a小的數(shù)有多少個(gè)的問題了。這種問題用線段樹來解時(shí)間復(fù)雜度非常完美，但是由于線段樹的空間復(fù)雜度一直被人詬病，所以這樣做的空間復(fù)雜度會(huì)有些高。我們的線段樹的每個(gè)節(jié)點(diǎn)都保存著常規(guī)域left和right指針，以及該節(jié)點(diǎn)所表示的區(qū)間的start和end，最后的特征值我們保存[start, end]區(qū)間中的節(jié)點(diǎn)數(shù)。這樣，當(dāng)?shù)趇個(gè)節(jié)點(diǎn)a來到時(shí)，我們需要向線段樹中插入，插入函數(shù)返回值即當(dāng)前已經(jīng)輸入的星星中x坐標(biāo)小于a的個(gè)數(shù)。這里是代碼的核心，如果a < start那么我們可以直接返回0了；否則如果a > end，則我們可以直接返回當(dāng)前節(jié)點(diǎn)的[start, end]中所有的節(jié)點(diǎn)個(gè)數(shù)了，因?yàn)樵赱start, end]的區(qū)間中的所有節(jié)點(diǎn)的x坐標(biāo)必定都小于a，因?yàn)閍 > end（這不廢話嘛……）；否則若a == start && a == end，則說明當(dāng)前節(jié)點(diǎn)已經(jīng)為葉子節(jié)點(diǎn)了，那么直接返回當(dāng)前節(jié)點(diǎn)的星星數(shù)量，然后再將a插入到該節(jié)點(diǎn)，即當(dāng)前節(jié)點(diǎn)的星星數(shù)量加1；最后的情況肯定就是a在區(qū)間[start, end]之間了，這時(shí)候遞歸向左子樹和右子樹插入即可，返回值相加即是[start, end]中小于a的星星的數(shù)量。說的比較羅嗦，看代碼吧：
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 }
注意如果直接拿這個(gè)代碼提交會(huì)TLE，主要時(shí)間其實(shí)耗費(fèi)在了建線段樹上了， 因?yàn)槲覀儾捎玫氖怯胢alloc從堆中分配，沒開辟一個(gè)節(jié)點(diǎn)就調(diào)用一次malloc函數(shù)，非常耗費(fèi)時(shí)間，我第一次提交就TLE了，不過可以不需要把其改成用數(shù)組表示線段樹的形式，可以直接不管內(nèi)存釋放，直接把release(root)語句刪除，然后把release()函數(shù)刪除，這樣提交的代碼恰好1000ms，太驚險(xiǎn)了。如果用數(shù)組表示線段樹的話相信時(shí)間會(huì)快很多，這就是oj的特點(diǎn)。另外需要說明的是把malloc替換成new的話會(huì)超過1000ms，超時(shí)，說明還是用malloc效率高一些。
posted on 2012-09-13 14:31
myjfm 閱讀(1289)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
算法基礎(chǔ)