學習數據挖掘 1 : 線段樹

來自專欄學習數據挖掘6 人贊了文章

問題引入：售票系統問題

假設在一個火車線路上有五個車站，它們分別在A、B、C、D、E五座城市(因此區間數 )。售票部門出售所能的車票，即起始站和終點站是任意的。由於城市之間距離較長，售票部分希望每位乘客都有座位，設總座位數是 。在處理新的訂單請求時，機智的程序員怎麼最快地判斷是否還有餘座呢？

拍腦袋給出的演算法

開一個 維的數組，分別存儲A-B, B-C, C-D, D-E段的乘客數，每當新訂單出現時，就更新相應的區間，只要 個數都小於乘客數 (等價地， 個數中最大數小於乘客數 ), 就安排乘客上這趟車，否則告訴乘客余票不足。

每新添加一個訂單，需要重新找 個數中的最大數，因此計算複雜度是 。這是最好的演算法嗎？

問題的分析

• 售票系統是一個在線的系統，會有源源不斷的新數據(新訂單)湧入，因此保留歷史的中間變數可能會加速演算法。
• 車站具有順序性。其次，一個顧客的乘坐區間只能是連續的，即他不可能在A站上火車，B站下火車，又在D站上同一趟火車，最後在E站下了車。

線段樹長神馬樣子？

仍然從售票系統例子出發。一開始售票數為0時，線段樹長這樣（圖1）：

基本特點容易看出：這是一個二叉樹，在每個節點處，一個區間被分成了左、右兩個區間。在每個節點和葉子處，都有一個伴隨數字，這個數字代表這個區間的乘車人數(這麼說不嚴謹，具體怎麼更新，請大家耐著性子再往後看2333)。

首先打北邊來了個小饒同學，他的乘車區間是B-C, B-C就是葉節點，線段樹更新為（圖2）：

然後打南邊來了個小鳴同學，他的乘車區間是B-D, 注意B-D=B-C+C-D, 而B-C和C-D是葉節點，線段樹更新為（圖3）：

一直到現在都十分正常，和拍腦袋給出的演算法一樣。

這時急匆匆來了個小迪同學，他的乘車區間是A-D, A-D=A-C+C-D, C-D是葉節點這個沒問題，但A-C是一個中間節點，現在有兩種看法：

• 繼續往下拆，A-C=A-B+B-C， 更新A-B 和B-C區間
• 保持整體， 更新A-C區間，線段樹的哲♂學要求我們選擇這種更新策略，如圖4所示。

最後來了個小承同學，他買了張全程票，即A-E, 注意到A-E恰好就是根，於是不必往下拆了，更新A-E即可，如圖5所示。按照拍腦袋給出的演算法，等價的結果應該如圖5 所示。

是騾子是馬，拉出來溜溜了。我們需要知道區間的最多人數，從葉節點出發，我們可以算出所有區間人數的最大值（因為有 ）。如下圖所示：

兩種辦法求出的最大值都是4，可以說明線段樹和拍腦袋方法的等價性。好了，線段樹學習結束了。exm？？？那線段樹優勢在哪呢？

為什麼線段樹？

更新(添加新訂單)

• 對於拍腦袋的辦法，需要 的運算量
• 對於線段樹，只需要 的運算量，嚴格的上界是
• 簡單地理解，當一個區間恰好等於一個節點（而不必是葉節點），更新即可完成

查詢(計算所有區間的最多乘客數)

• 對於拍腦袋的辦法，採用打擂法求最大值，需要 的運算量
• 對於線段樹，利用了樹的結構，還是需要 的計算量，而且在中間節點處要記得加上相應的數(專業名稱：lazy tag等等)。

所以線段樹的優勢，主要還是體現在在線(online)的問題上。

一般的線段樹

博客：這裡有嚴格定義和相應的實現代碼