ACMer不得不會的線段樹，究竟是種怎樣的數(shù)據(jù)結構？
今天我們來聊聊一個新的數(shù)據(jù)結構，叫做線段樹。
線段樹這個數(shù)據(jù)結構很多人可能會有點蒙，覺得沒有聽說過，但是它非常非常有名，尤其是在競賽圈，可以說是競賽圈的必備技能。所以如果以后遇到有人看了一點算法導論就在你面前裝逼，你就可以問他：請問線段樹更新的復雜度是多少？
不過如果你會線段樹，你也要小心一點，最好不要在面試的時候隨便透露你會這個算法。否則面試官一下子就會知道你是圈里人，然后你會發(fā)現(xiàn)你后面的面試問題比之前好像難不少。當然也有可能遇到面試官自己不會，為了防止尷尬強行讓你用非線段樹的解法來完成，比如我就遇到過……
例題
說了這么多廢話，那么線段樹究竟是什么呢？線段樹的英文是segment tree，其實也算是一個直譯。因為這個數(shù)據(jù)結構和線段沒有特別大的關系，我個人感覺翻譯成區(qū)間樹可能更貼近一點。
我們先理解到這里，就是這個數(shù)據(jù)結構大概和區(qū)間有點關系。我們先放一放，先來看一道例題，來實際體會一下，為什么需要線段樹這個數(shù)據(jù)結構，以及它的使用場景究竟是什么。這樣我們可以對它有一個更加直觀的感受，這道題很簡單也很經(jīng)典，我就是在這道題遇到了面試官不讓用線段樹的突然襲擊。
這道題的題面是這樣，給定一個長度為n的數(shù)組。這個數(shù)組當中有n個整數(shù)，然后我們會有兩種操作。一種操作叫更新，我們指定更新某一個位置的某個數(shù)，第二個操作叫query，給定一個區(qū)間，要求這個區(qū)間里面元素的最小值。n的范圍呢是，操作的數(shù)量也是，請問我們應該怎么實現(xiàn)？
線段樹概念
當然你可能已經(jīng)知道要用線段樹了，只是不知道線段樹是什么以及怎么使用。我們先把這些疑惑放在一邊，就單純簡單地用最樸素的方法來思考的話，我們會發(fā)現(xiàn)我們每次查詢都是的操作。最壞的情況下，我們就是要求整個數(shù)組的最小值，那么我們需要依次遍歷整個區(qū)間來求。那么復雜度再乘上操作的數(shù)量，整個程序的復雜度會達到。顯然這是一個非常巨大的數(shù)字，在算法競賽場景當中一定會超時。
也就是說簡單粗暴是做不出來的，如果你有足夠多的做題經(jīng)驗，你就會很自然地想到我們也許需要使用一些數(shù)據(jù)結構來優(yōu)化這個查詢的復雜度。肯定是不能接受的，即使不能優(yōu)化到，也至少可以試試。線段樹就是這樣的數(shù)據(jù)結構，我們直接來看一張圖，我們直接就可以搞明白線段樹究竟是干嘛的，以及它的工作原理。
這張圖當中的a就是我們存數(shù)據(jù)的數(shù)組，這個數(shù)組上面的就是線段樹。我們從上往下看，給大家解釋一下。最上面一條只有一個數(shù)字就是1，它代表的是整個數(shù)組的最小值是1。也就是說最上層維護的是整個區(qū)間的最小值。然后是第二層，在第二層我們看到了兩個數(shù)，分別是3和1。很明顯，3表示的是左半邊區(qū)間的最小值，1表示的右半邊區(qū)間的最小值。
到了第三行我們得到了4個數(shù)，同理，再下一層有8個數(shù)。很明顯這是一顆二叉樹，并且二叉樹當中的每一個節(jié)點維護了一個區(qū)間的值。它的葉子節(jié)點存儲的是長度為1的區(qū)間，也就是單個元素。我們把兩個兄弟節(jié)點維護的區(qū)間合并起來就得到了父節(jié)點的區(qū)間。在這道題當中，由于我們維護的是區(qū)間的最小值，所以我們可以得到這么一個式子：
node.min?=?min(node.left.min,?node.right.min)
所以線段樹就是利用了二叉樹這個層次結構對一個區(qū)間進行維護的數(shù)據(jù)結構。
線段樹查詢
我們已經(jīng)了解了線段樹的結構了，剩下的就只有兩個問題，一個是如何更新一個是如何求解。我發(fā)先來看求解，我們要求一個區(qū)間的最小值。我們來實際看一下，假設我們想要查詢下標是[2, 5]這個區(qū)間里的最小值怎么辦？
我們對照一下上面的數(shù)組a，下標[3, 6]這個區(qū)間對應的是[7, 9, 6, 4]這四個值。我們會發(fā)現(xiàn)不存在剛好只包含這四個值的區(qū)間，那怎么辦呢？其實很簡單，可以拼湊。我們可以發(fā)現(xiàn)我們可以把這個完整的區(qū)間轉(zhuǎn)化成兩個區(qū)間連接在一起的結果。比如下圖這樣。
這樣，我們就把原本比較[7, 9, 6, 4]四個值的一個查詢行為轉(zhuǎn)化成了只需要比較4和7兩個值大小的比較行為了。這可以替我們節(jié)約大量的時間。這和記憶化搜索有一點點像，相當于我們制定一個模式，根據(jù)這個模式把區(qū)間里的最值存儲下來。這樣我們查詢的時候可以利用這些值來快速求解。
如果我們要求[2, 7]區(qū)間內(nèi)的最小值，那么我們可以轉(zhuǎn)而用這兩個區(qū)間的值求到。
線段樹更新
接下來我們來看下線段樹的更新，其實更新和查詢的原理是一樣的，同樣是從根節(jié)點出發(fā)一層層往下，一直到更新到葉子節(jié)點為止。假如說我們把數(shù)據(jù)當中的4更新成0，那么會達成一種怎樣的效果呢？
從結果上來看，我們是把發(fā)生變更的葉子節(jié)點到樹根的這一整個鏈路都更新了。當然這個更新也不是強制發(fā)生的，因為如果我們更新的值比它的原值1要大的話，也是不會更新的。
代碼實現(xiàn)
關于線段樹的原理我們就差不多講完了，看起來不太長，這是很正常的。因為線段樹的原理其實很簡單，就是用一棵二叉樹來維護各個長度的區(qū)間。我們在查詢的時候就是要找到可以拼成我們查詢的區(qū)間的幾個子區(qū)間，用這些子區(qū)間的值來求到我們要查的區(qū)間的值。在我們更新的時候，不需要更新整棵樹，只需要更新某一條從根節(jié)點到葉子節(jié)點的路徑就可以了。
原理看起來不難，理解起來也不難，但是要用代碼實現(xiàn)出來其實不太容易。因為線段樹的所有操作都是基于遞歸和回溯的，所以想要順利、深入地理解線段樹，對于遞歸以及回溯的掌握一定要過關。否則線段樹你寫起來很痛苦，寫完了調(diào)試會更痛苦。
我們會用面向?qū)ο蟮男问絹韯?chuàng)建一個線段樹，當然也有人喜歡用數(shù)組來模擬，這也是可以的，本質(zhì)上都是一樣的。首先我們來創(chuàng)建一個節(jié)點類。這個節(jié)點類存儲的值有3個，一個是它維護的區(qū)間的值，在這個題目里維護的是區(qū)間最小值。一個是區(qū)間的范圍， 左右邊界。另外一個是左右孩子節(jié)點。
由于我們在創(chuàng)建節(jié)點的時候還不知道它的左右孩子以及維護的值是什么，所以我們先賦值成None。
class?Node:
????def?__init__(self,?left_side,?right_side):
????????self.val?=?None
????????self.ls,?self.rs?=?left_side,?right_side
????????self.left_child,?self.right_child?=?None,?None
Node類有了之后，我們就可以利用它來建樹了。我們首先來看看建樹的方法，也就是常說的build方法。我們創(chuàng)建線段樹的時候最重要的就是讓它當中的每一個節(jié)點能夠存儲對應區(qū)間的最小值。但是呢由于線段樹是有層次結構的，我們在創(chuàng)建區(qū)間[a, b]的時候，其實可以利用區(qū)間[a, m]和區(qū)間[m+1, b]兩個區(qū)間的最小值來獲取整個區(qū)間的最小值。也就是說我們可以利用當前節(jié)點的左右孩子節(jié)點完成，我們之前已經(jīng)說過這點了。
我們來看代碼，通過遞歸可以很方便地完成這一點。
class?SegmentTree:
????def?__init__(self,?arr):
????????self.n?=?len(arr)
????????self.vals?=?arr[:]
????????self.root?=?self.build(0,?self.n)
????def?build(self,?l,?r):
????????#?傳入的l和r表示區(qū)間范圍，左閉右開
????????if?r?-?l?1:
????????????return?None
????????node?=?Node(l,?r)
????????#?如果區(qū)間長度是1，說明是葉子節(jié)點了，直接將val賦值成對應的數(shù)值
????????if?r?-?l?==?1:
????????????node.val?=?self.vals[l]
????????else:
????????????#?否則遞歸調(diào)用
????????????m?=?(l?+?r)?>>?1
????????????node.left_child?=?self.build(l,?m)
????????????node.right_child?=?self.build(m,?r)
????????????node.val?=?min(node.left_child.val,?node.right_child.val)
????????return?node
當然這個過程也可以用循環(huán)實現(xiàn)，只不過用遞歸實現(xiàn)更加簡單。
如果你能看得到build方法，那么update和query對你來說也都不是問題，其實原理都是一樣的，只不過一個是通過遞歸的形式去更新一個是遞歸去查詢而已。我們先來看update：
????def?update(self,?k,?v):
????????self._update(self.root,?k,?v)
????def?_update(self,?u,?k,?v):
????????if?u?is?None:
????????????return
????????#?如果k在u這個節(jié)點維護的區(qū)間里
????????if?u.ls?<=?k?????????????#?更新它的最小值
????????????u.val?=?min(u.val,?v)
????????????m?=?(u.ls?+?u.rs)?>>?1
????????????#?判斷往左還是往右
????????????if?k?????????????????self._update(u.left_child,?k,?v)
????????????else:
????????????????self._update(u.right_child,?k,?v)
最后我們再來看query，query同樣是通過遞歸執(zhí)行的。由于我們查詢的是一個區(qū)間，所以我們需要判斷我們查詢區(qū)間和節(jié)點維護區(qū)間之間的關系。只要抓住了這一點，整個邏輯也是很簡單的。
????def?query(self,?l,?r):
????????return?self._query(self.root,?l,?r)
????def?_query(self,?u,?l,?r):
????????#?l和r是查詢區(qū)間
????????#?如果查詢區(qū)間是u節(jié)點區(qū)間的超集
????????if?l?<=?u.ls?and?r?>=?u.rs:
????????????return?u.val
????????#?如果查詢區(qū)間只和u節(jié)點區(qū)間的左半部分有交集
????????elif?r?<=?u.left_child.rs:
????????????return?self._query(u.left_child,?l,?r)
????????#?如果查詢區(qū)間只和u節(jié)點右半部分有交集
????????elif?l?>=?u.right_child.ls:
????????????return?self._query(u.right_child,?l,?r)
????????#?如果都有交集
????????return?min(self._query(u.left_child,?l,?r),?self._query(u.right_child,?l,?r))
最后
到這里，我們關于線段樹的基本介紹就算是結束了。注意我說的是基本介紹，因為線段樹有很多種用法，今天介紹的只是其中最簡單的一種：單點更新區(qū)間查詢。除此之外還有區(qū)間更新單點查詢，區(qū)間更新區(qū)間查詢，掃描線等等相對高端一些的用法。由于篇幅所限不能一次講完，準備放在之后的文章當中分享給大家。
另外一點市面上線段樹的題目基本上都是用C++寫的，所以如果你想要找一道題試一下的話，可能需要用C++重新寫一遍。不過我相信這對于你們來說并不是什么大問題。
推薦閱讀
1、帥地入職鵝廠的這 180 天里，談一談自己的不足與收獲吧
3、哭了，帥地手握兩臺 mac ，1000頁的《程序員內(nèi)功修煉》第二版......