1、概述

線段樹，也叫區(qū)間樹，是一個完全二叉樹，它在各個節(jié)點保存一條線段（即“子數(shù)組”），因而常用于解決數(shù)列維護問題，它基本能保證每個操作的復(fù)雜度為O(lgN)。

2、線段樹基本操作

線段樹的基本操作主要包括構(gòu)造線段樹，區(qū)間查詢和區(qū)間修改。

（1）    線段樹構(gòu)造

首先介紹構(gòu)造線段樹的方法：讓根節(jié)點表示區(qū)間[0,N-1]，即所有N個數(shù)所組成的一個區(qū)間，然后，把區(qū)間分成兩半，分別由左右子樹表示。不難證明，這樣的線段樹的節(jié)點數(shù)只有2N-1個，是O(N)級別的，如圖：

顯然，構(gòu)造線段樹是一個遞歸的過程，偽代碼如下：

線段樹除了最后一層外，前面每一層的結(jié)點都是滿的，因此線段樹的深度

h =ceil(log(2n -1))=O(log n)。

（2）    區(qū)間查詢

區(qū)間查詢指用戶輸入一個區(qū)間，獲取該區(qū)間的有關(guān)信息，如區(qū)間中最大值，最小值，第N大的值等。

比如前面一個圖中所示的樹，如果詢問區(qū)間是[0,2]，或者詢問的區(qū)間是[3,3]，不難直接找到對應(yīng)的節(jié)點回答這一問題。但并不是所有的提問都這么容易回答，比如[0,3]，就沒有哪一個節(jié)點記錄了這個區(qū)間的最小值。當然，解決方法也不難找到：把[0,2]和[3,3]兩個區(qū)間（它們在整數(shù)意義上是相連的兩個區(qū)間）的最小值“合并”起來，也就是求這兩個最小值的最小值，就能求出[0,3]范圍的最小值。同理，對于其他詢問的區(qū)間，也都可以找到若干個相連的區(qū)間，合并后可以得到詢問的區(qū)間。

區(qū)間查詢的偽代碼如下：

可見，這樣的過程一定選出了盡量少的區(qū)間，它們相連后正好涵蓋了整個[l,r]，沒有重復(fù)也沒有遺漏。同時，考慮到線段樹上每層的節(jié)點最多會被選取2個，一共選取的節(jié)點數(shù)也是O(log n)的，因此查詢的時間復(fù)雜度也是O(log n)。

線段樹并不適合所有區(qū)間查詢情況，它的使用條件是“相鄰的區(qū)間的信息可以被合并成兩個區(qū)間的并區(qū)間的信息”。即問題是可以被分解解決的。

（3）    區(qū)間修改

當用戶修改一個區(qū)間的值時，如果連同其子孫全部修改，則改動的節(jié)點數(shù)必定會遠遠超過O(log n)個。因而，如果要想把區(qū)間修改操作也控制在O(log n)的時間內(nèi)，只修改O(log n)個節(jié)點的信息就成為必要。

借鑒前一節(jié)區(qū)間查詢用到的思路：區(qū)間修改時如果修改了一個節(jié)點所表示的區(qū)間，也不用去修改它的兒子節(jié)點。然而，對于被修改節(jié)點的祖先節(jié)點，也必須更新它所記錄的值，否則查詢操作就肯定會出問題（正如修改單個節(jié)點的情況一樣）。

這些選出的節(jié)點的祖先節(jié)點直接更新值即可，而選出的節(jié)點的子孫卻顯然不能這么簡單地處理：每個節(jié)點的值必須能由兩個兒子節(jié)點的值得到，如這幅圖中的例子：

這里，節(jié)點[0,1]的值應(yīng)該是4，但是兩個兒子的值又分別是3和5。如果查詢[0,0]區(qū)間的RMQ，算出來的結(jié)果會是3，而正確答案顯然是4。

問題顯然在于，盡管修改了一個節(jié)點以后，不用修改它的兒子節(jié)點，但是它的兒子節(jié)點的信息事實上已經(jīng)被改變了。這就需要我們在節(jié)點里增設(shè)一個域：標記。把對節(jié)點的修改情況儲存在標記里面，這樣，當我們自上而下地訪問某節(jié)點時，就能把一路上所遇到的所有標記都考慮進去。

但是，在一個節(jié)點帶上標記時，會給更新這個節(jié)點的值帶來一些麻煩。繼續(xù)上面的例子，如果我把位置0的數(shù)字從4改成了3，區(qū)間[0,0]的值應(yīng)該變回3，但實際上，由于區(qū)間[0,1]有一個“添加了1”的標記，如果直接把值修改為3，則查詢區(qū)間[0,0]的時候我們會得到3+1=4這個錯誤結(jié)果。但是，把這個3改成2，雖然正確，卻并不直觀，更不利于推廣（參見下面的一個例子）。

為此我們引入延遲標記的一些概念。每個結(jié)點新增加一個標記，記錄這個結(jié)點是否被進行了某種修改操作(這種修改操作會影響其子結(jié)點)。還是像上面的一樣，對于任意區(qū)間的修改，我們先按照查詢的方式將其劃分成線段樹中的結(jié)點，然后修改這些結(jié)點的信息，并給這些結(jié)點標上代表這種修改操作的標記。在修改和查詢的時候，如果我們到了一個結(jié)點p ，并且決定考慮其子結(jié)點，那么我們就要看看結(jié)點p 有沒有標記，如果有，就要按照標記修改其子結(jié)點的信息，并且給子結(jié)點都標上相同的標記，同時消掉p 的標記。代碼框架為：

3、應(yīng)用

下面給出線段樹的幾個應(yīng)用：

（1）有一列數(shù)，初始值全部為0。每次可以進行以下三種操作中的一種：

a. 給指定區(qū)間的每個數(shù)加上一個特定值；

b.將指定區(qū)間的所有數(shù)置成一個統(tǒng)一的值；

c.詢問一個區(qū)間上的最小值、最大值、所有數(shù)的和。

給出一系列a.b.操作后，輸出c的結(jié)果。

[問題分析]

這個是典型的線段樹的應(yīng)用。在每個節(jié)點上維護一下幾個變量：delta（區(qū)間增加值），same（區(qū)間被置為某個值），min（區(qū)間最小值），max（區(qū)間最大值），sum（區(qū)間和），其中delta和same屬于“延遲標記”。

（2）在所有不大于30000的自然數(shù)范圍內(nèi)討論一個問題：已知n條線段，把端點依次輸入給你，然后有m（≤30000）個詢問，每個詢問輸入一個點，要求這個點在多少條線段上出現(xiàn)過。

[問題分析]

在這個問題中，我們可以直接對問題處理的區(qū)間建立線段樹，在線段樹上維護區(qū)間被覆蓋的次數(shù)。將n條線段插入線段樹，然后對于詢問的每個點，直接查詢被覆蓋的次數(shù)即可。

但是我們在這里用這道題目，更希望能夠說明一個問題，那就是這道題目完全可以不用線段樹。我們將每個線段拆成(L,+1)，(R+1,-1)的兩個事件點，每個詢問點也在對應(yīng)坐標處加上一個詢問的事件點，排序之后掃描就可以完成題目的詢問。我們這里討論的問題是一個離線的問題，因此我們也設(shè)計出了一個很簡單的離線算法。線段樹在處理在線問題的時候會更加有效，因為它維護了一個實時的信息。

這個題目也告訴我們，有的題目盡管可以使用線段樹處理，但是如果我們能夠抓住題目的特點，就可能獲得更加優(yōu)秀的算法。

（3）某次列車途經(jīng)C個城市，城市編號依次為1到C，列車上共有S個座位，鐵路局規(guī)定售出的車票只能是坐票，即車上所有的旅客都有座，售票系統(tǒng)是由計算機執(zhí)行的，每一個售票申請包含三個參數(shù)，分別用O、D、N表示，O為起始站，D為目的地站，N為車票張數(shù)，售票系統(tǒng)對該售票申請作出受理或不受理的決定，只有在從O到D的區(qū)段內(nèi)列車上都有N個或N個以上的空座位時該售票申請才被受理，請你寫一個程序，實現(xiàn)這個自動售票系統(tǒng)。

[問題分析]

這里我們可以把所有的車站順次放在一個數(shù)軸上，在數(shù)軸上建立線段樹，在線段樹上維護區(qū)間的delta與max。每次判斷一個售票申請是否可行就是查詢區(qū)間上的最大值；每個插入一個售票請求，就是給一個區(qū)間上所有的元素加上購票數(shù)。

這道題目在線段樹上維護的信息既包括自下至上的遞推，也包括了自上至下的傳遞，能夠比較全面地對線段樹的基本操作進行訓(xùn)練。

（4）給一個n*n的方格棋盤，初始時每個格子都是白色?，F(xiàn)在要刷M次黑色或白色的油漆。每次刷漆的區(qū)域都是一個平行棋盤邊緣的矩形區(qū)域。

輸入n,M,以及每次刷漆的區(qū)域和顏色，輸出刷了M次之后棋盤上還有多少個棋格是白色。

[問題分析]

首先我們從簡單入手，考慮一維的問題。即對于一個長度為n的白色線段，對它進行M次修改（每次更新某一子區(qū)域的顏色）。問最后還剩下的白色區(qū)域有多長。

對于這個問題，很容易想到建立一棵線段樹的模型。復(fù)雜度為O(Mlgn)。

擴展到二維，需要把線段樹進行調(diào)整，即首先在橫坐標上建立線段樹，它的每個節(jié)點是一棵建立在縱坐標上的線段樹（即樹中有樹。稱為二維線段樹）。復(fù)雜度為O(M(logn)^2)。

4、總結(jié)

利用線段樹，我們可以高效地詢問和修改一個數(shù)列中某個區(qū)間的信息，并且代碼也不算特別復(fù)雜。

但是線段樹也是有一定的局限性的，其中最明顯的就是數(shù)列中數(shù)的個數(shù)必須固定，即不能添加或刪除數(shù)列中的數(shù)。

5、參考資料

（1）    楊弋文章：《線段樹》：

http://download.csdn.net/source/2255479

（2）    林濤文章《線段樹的應(yīng)用》：

http://wenku.baidu.com/view/d65cf31fb7360b4c2e3f64ac.html

（3）    朱全民文章《線段樹及其應(yīng)用》：

http://wenku.baidu.com/view/437ad3bec77da26925c5b0ba.html

（4）    線段樹：

http://wenku.baidu.com/view/32652a2d7375a417866f8f51.html

----------------------------------------------------------------------------------------------
更多關(guān)于數(shù)據(jù)結(jié)構(gòu)和算法的介紹，請查看：數(shù)據(jù)結(jié)構(gòu)與算法匯總
----------------------------------------------------------------------------------------------