1、概述

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

2、線段樹(shù)基本操作

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

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

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

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

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

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

（2）    區(qū)間查詢

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

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

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

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

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

（3）    區(qū)間修改

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

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

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

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

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

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

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

3、應(yīng)用

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

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

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

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

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

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

[問(wèn)題分析]

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

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

[問(wèn)題分析]

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

但是我們?cè)谶@里用這道題目，更希望能夠說(shuō)明一個(gè)問(wèn)題，那就是這道題目完全可以不用線段樹(shù)。我們將每個(gè)線段拆成(L,+1)，(R+1,-1)的兩個(gè)事件點(diǎn)，每個(gè)詢問(wèn)點(diǎn)也在對(duì)應(yīng)坐標(biāo)處加上一個(gè)詢問(wèn)的事件點(diǎn)，排序之后掃描就可以完成題目的詢問(wèn)。我們這里討論的問(wèn)題是一個(gè)離線的問(wèn)題，因此我們也設(shè)計(jì)出了一個(gè)很簡(jiǎn)單的離線算法。線段樹(shù)在處理在線問(wèn)題的時(shí)候會(huì)更加有效，因?yàn)樗S護(hù)了一個(gè)實(shí)時(shí)的信息。

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

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

[問(wèn)題分析]

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

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

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

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

[問(wèn)題分析]

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

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

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

4、總結(jié)

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

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

5、參考資料

（1）    楊弋文章：《線段樹(shù)》：

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

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

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

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

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

（4）    線段樹(shù)：

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

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