線段樹（segment tree）是一種二叉搜索樹，也是平衡二叉樹，它的每一個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)區(qū)間?[L,R] ,葉子結(jié)點(diǎn)對(duì)應(yīng)的區(qū)間只有一個(gè)結(jié)點(diǎn)（L = R）。每一個(gè)非葉子結(jié)點(diǎn) [L , R] ，其左孩子區(qū)間為 [L, (L+R)/2] ,右孩子區(qū)間為 [ (L+R)/2+1, R] 。

????因?yàn)榫€段樹是平衡二叉樹，所以樹高為 log(n)，樹上的操作大多和樹高有關(guān)。線段樹主要用于更新和查詢，一般至少有一個(gè)是區(qū)間更新或查詢。更新和查新的種類變化多端，靈活運(yùn)用線段樹可以解決多種問(wèn)題。

????例如，區(qū)間最值查詢問(wèn)題（Rang Minimum/Maximum Query, RMQ），該問(wèn)題有兩種操作：(1) 點(diǎn)更新：修改一個(gè)元素的值；（2）區(qū)間查詢：查詢一個(gè)區(qū)間的最值。

1. 線段樹的實(shí)現(xiàn)

以區(qū)間最值查詢問(wèn)題為例，講述線段的實(shí)現(xiàn)過(guò)程。

（1）存儲(chǔ)方式

????因?yàn)橐樵儏^(qū)間最大值（最大值或最小值），因此每個(gè)結(jié)點(diǎn)包含三個(gè)域：l, r, mx, 其中 l?和 r 分別表示區(qū)間的左右端點(diǎn)， mx表示區(qū)間 [ l, r] 的最值。本題以最大值為例。例如，有 10個(gè)元素 a[ 1 ... 10] = {5, 3, 7, 2, 12, 1, 6, 4, 8, 15} ,線段樹如圖所示。

????由于線段樹除了最后一層外，其他層構(gòu)成一個(gè)滿二叉樹，因此可以采用順序存儲(chǔ)方式，用一個(gè)數(shù)組 tree[ ] 存儲(chǔ)結(jié)點(diǎn)。如果一個(gè)結(jié)點(diǎn)的存儲(chǔ)下標(biāo)為 k, 則左孩子的下標(biāo)為 2k, 右孩子的下標(biāo)為 2k+1 。 如圖所示：

????線段樹根節(jié)點(diǎn)的存儲(chǔ)下標(biāo)為 1，其左右孩子存儲(chǔ)下標(biāo)分別為 2，3 。。。

(2) 創(chuàng)建線段樹

????可以采用遞歸的方法創(chuàng)建線段樹，其創(chuàng)建過(guò)程如下：

????1） 如果是葉子結(jié)點(diǎn) （r = l）, 則結(jié)點(diǎn)的最值就是對(duì)應(yīng)位置的元素值；

????2） 如果是非葉子結(jié)點(diǎn)，遞歸創(chuàng)建左子樹 和右子樹；

????3）結(jié)點(diǎn)的區(qū)間最值等于該結(jié)點(diǎn)左右子樹最值的最大值；

????代碼實(shí)現(xiàn)：

（3） 點(diǎn)更新

????點(diǎn)更新是指修改一個(gè)元素的值，例如將 a[i] 修改為 v, 仍然采用遞歸的方法進(jìn)行點(diǎn)更新，其過(guò)程如下：

????1）如果是第 i 個(gè)元素所在的葉子結(jié)點(diǎn)（r = l 且 l = i）,則修改結(jié)點(diǎn)的最值為 v；

????2) 如果是非葉子結(jié)點(diǎn)，則判斷在左子樹中更新還是在右子樹中更新;

????3) 返回時(shí)更新結(jié)點(diǎn)的最值；

????代碼實(shí)現(xiàn)：

（4）區(qū)間查詢

????區(qū)間查詢是指查詢一個(gè)個(gè)區(qū)間的最值。仍然采用遞歸的方法進(jìn)行區(qū)間查詢，其過(guò)程如下：

????1）如果結(jié)點(diǎn)的區(qū)間被查詢區(qū)間 [l, r] 覆蓋，則返回該結(jié)點(diǎn)的最值；

????2）判斷在左子樹查詢，右子樹查詢；

????3）返回最值；

（5）區(qū)間更新

????對(duì) [l,r] 進(jìn)行區(qū)間更新：

????1) 如果結(jié)點(diǎn)的區(qū)間被查詢區(qū)間 [l,r] 覆蓋，僅對(duì)該結(jié)點(diǎn)進(jìn)行更新，并作懶標(biāo)記，表示該結(jié)點(diǎn)被更新過(guò)，對(duì)該結(jié)點(diǎn)的子結(jié)點(diǎn)不再進(jìn)行更新；

????2）判斷在左子樹查詢，右子樹查詢。查詢過(guò)程中，若當(dāng)前結(jié)點(diǎn)帶有懶標(biāo)記，懶標(biāo)記下傳給子結(jié)點(diǎn) (當(dāng)前結(jié)點(diǎn)懶標(biāo)記清除，子結(jié)點(diǎn)更新并做懶標(biāo)記)，繼續(xù)查詢；

????3）更新最值。

????例如，在[1 , 10] 的線段樹中修改 [4,8] 區(qū)間的值為 20.

代碼實(shí)現(xiàn)：

2. 線段樹的性能分析：

????線段樹采用了分治算法策略，其點(diǎn)更新，區(qū)間更新，區(qū)間查詢均可以在O(log n) 時(shí)間內(nèi)完成。樹狀數(shù)組和線段樹都用于頻繁的修改和查詢問(wèn)題，樹狀數(shù)組可以實(shí)現(xiàn)點(diǎn)更新，區(qū)間查詢，而線段樹還可以實(shí)現(xiàn)區(qū)間更新，區(qū)間查詢。線段樹的用途更廣，更靈活，樹狀數(shù)組比線段樹節(jié)省空間，代碼簡(jiǎn)單易懂，但是線段樹更靈活，凡是能用樹狀數(shù)組的問(wèn)題一定能用線段樹。