好久沒寫過算法了，添一個吧，寫一個線段樹的入門知識，比較大眾化。

上次在湖大，其中的一道題數據很強，我試了好多種優化都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

 1void 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