好久沒寫過算法了，添一個吧，寫一個線段樹的入門知識，比較大眾化。
上次在湖大，其中的一道題數據很強，我試了好多種優化都TLE，相信只能用線段樹才能過。回來之后暗暗又學了一次線段樹，想想好像是第三次學了，像網絡流一樣每學一次都有新的體會。
把問題簡化一下：
在自然數，且所有的數不大于30000的范圍內討論一個問題：現在已知n條線段，把端點依次輸入告訴你，然后有m個詢問，每個詢問輸入一個點，要求這個點在多少條線段上出現過；
最基本的解法當然就是讀一個點，就把所有線段比一下，看看在不在線段中；
每次詢問都要把n條線段查一次，那么m次詢問，就要運算m*n次，復雜度就是O(m*n)
這道題m和n都是30000，那么計算量達到了10^9；而計算機1秒的計算量大約是10^8的數量級，所以這種方法無論怎么優化都是超時
-----
因為n條線段是固定的，所以某種程度上說每次都把n條線段查一遍有大量的重復和浪費；
線段樹就是可以解決這類問題的數據結構
舉例說明：已知線段[2,5] [4,6] [0,7]；求點2,4,7分別出現了多少次
在[0,7]區間上建立一棵滿二叉樹：（為了和已知線段區別，用【】表示線段樹中的線段）
【0,7】
/ \
【0,3】 【4,7】
/ \ / \
【0,1】 【2,3】 【4,5】 【6,7】
/ \ / \ / \ / \
【0,0】 【1,1】【2,2】 【3,3】 【4,4】 【5,5】 【6,6】 【7,7】
每個節點用結構體：
struct line
{
int left,right;//左端點、右端點
int n;//記錄這條線段出現了多少次，默認為0
}a[16];
和堆類似，滿二叉樹的性質決定a[i]的左兒子是a[2*i]、右兒子是a[2*i+1];
然后對于已知的線段依次進行插入操作：
從樹根開始調用遞歸函數insert
1
void insert(int s,int t,int step)//要插入的線段的左端點和右端點、以及當前線段樹中的某條線段
2
3
{
4
5 if (s==a[step].left && t==a[step].right)
6
7
{
8
9 a[step].n++;//插入的線段匹配則此條線段的記錄+1
10
11 return;//插入結束返回
12
13
}
14
15 if (a[step].left==a[step].right) return;//當前線段樹的線段沒有兒子，插入結束返回
16
17 int mid=(a[step].left+a[step].right)/2;
18
19 if (mid>=t) insert(s,t,step*2);//如果中點在t的右邊，則應該插入到左兒子
20
21 else if (mid<s) insert(s,t,step*2+1);//如果中點在s的左邊，則應該插入到右兒子
22
23 else//否則，中點一定在s和t之間，把待插線段分成兩半分別插到左右兒子里面
24
25 {
26
27 insert(s,mid,step*2);
28
29 insert(mid+1,t,step*2+1);
30
31 }
32
33
}
34
35
三條已知線段插入過程：
[2,5]
--[2,5]與【0,7】比較，分成兩部分：[2,3]插到左兒子【0,3】，[4,5]插到右兒子【4,7】
--[2,3]與【0,3】比較，插到右兒子【2,3】；[4,5]和【4,7】比較，插到左兒子【4,5】
--[2,3]與【2,3】匹配，【2,3】記錄+1；[4,5]與【4,5】匹配，【4,5】記錄+1
[4,6]
--[4,6]與【0,7】比較，插到右兒子【4,7】
--[4,6]與【4,7】比較，分成兩部分，[4,5]插到左兒子【4,5】；[6,6]插到右兒子【6,7】
--[4,5]與【4,5】匹配，【4,5】記錄+1；[6,6]與【6,7】比較，插到左兒子【6,6】
--[6,6]與【6,6】匹配，【6,6】記錄+1
[0,7]
--[0,7]與【0,7】匹配，【0,7】記錄+1
插入過程結束，線段樹上的記錄如下（紅色數字為每條線段的記錄n）：
【0,7】
1
/ \
【0,3】 【4,7】
0 0
/ \ / \
【0,1】 【2,3】 【4,5】 【6,7】
0 1 2 0
/ \ / \ / \ / \
【0,0】 【1,1】 【2,2】 【3,3】 【4,4】 【5,5】 【6,6】 【7,7】
0 0 0 0 0 0 1 0
詢問操作和插入操作類似，也是遞歸過程，略
2——依次把【0,7】 【0,3】 【2,3】 【2,2】的記錄n加起來，結果為2
4——依次把【0,7】 【4,7】 【4,5】 【4,4】的記錄n加起來，結果為3
7——依次把【0,7】 【4,7】 【6,7】 【7,7】的記錄n加起來，結果為1
不管是插入操作還是查詢操作，每次操作的執行次數僅為樹的深度——logN
建樹有n次插入操作，n*logN，一次查詢要logN，m次就是m*logN；總共復雜度O(n+m)*logN，這道題N不超過30000，logN約等于14，所以計算量在10^5～10^6之間，比普通方法快了1000倍；
這道題是線段樹最基本的操作，只用到了插入和查找；刪除操作和插入類似，擴展功能的還有測度、連續段數等等，在N數據范圍很大的時候，依然可以用離散化的方法建樹。
湖大的那道題目繞了個小彎子，alpc12有詳細的題目和解題報告，有興趣的話可以看看http://m.shnenglu.com/sicheng/archive/2008/01/09/40791.html
線段樹的經典題目就是poj1177的picturehttp://acm.pku.edu.cn/JudgeOnline/problem?id=1177
posted on 2009-04-14 00:26
wyiu 閱讀(211)
評論(0) 編輯 收藏 引用 所屬分類:
算法