大家好，歡迎閱讀周三算法資料結構專題，今天我們來聊聊一個新的資料結構，叫做線段樹。
線段樹這個資料結構很多人可能會有點蒙，覺得沒有聽說過，但是它非常非常有名，尤其是在競賽圈，可以說是競賽圈的必備技能。是以如果以後遇到有人看了一點算法導論就在你面前裝逼，你就可以問他：請問線段樹更新的複雜度是多少？
不過如果你會線段樹，你也要小心一點，最好不要在面試的時候随便透露你會這個算法。否則面試官一下子就會知道你是圈裡人，然後你會發現你後面的面試問題比之前好像難不少。當然也有可能遇到面試官自己不會，為了防止尴尬強行讓你用非線段樹的解法來完成，比如我就遇到過……
例題
說了這麼多廢話，那麼線段樹究竟是什麼呢？線段樹的英文是segment tree，其實也算是一個直譯。因為這個資料結構和線段沒有特别大的關系，我個人感覺翻譯成區間樹可能更貼近一點。
我們先了解到這裡，就是這個資料結構大概和區間有點關系。我們先放一放，先來看一道例題，來實際體會一下，為什麼需要線段樹這個資料結構，以及它的使用場景究竟是什麼。這樣我們可以對它有一個更加直覺的感受，這道題很簡單也很經典，我就是在這道題遇到了面試官不讓用線段樹的突然襲擊。
這道題的題面是這樣，給定一個長度為n的數組。這個數組當中有n個整數，然後我們會有兩種操作。一種操作叫更新，我們指定更新某一個位置的某個數，第二個操作叫query，給定一個區間，要求這個區間裡面元素的最小值。n的範圍呢是
，操作的數量也是
，請問我們應該怎麼實作？
線段樹概念
當然你可能已經知道要用線段樹了，隻是不知道線段樹是什麼以及怎麼使用。我們先把這些疑惑放在一邊，就單純簡單地用最樸素的方法來思考的話，我們會發現我們每次查詢都是
的操作。最壞的情況下，我們就是要求整個數組的最小值，那麼我們需要依次周遊整個區間來求。那麼複雜度再乘上操作的數量，整個程式的複雜度會達到
。顯然這是一個非常巨大的數字，在算法競賽場景當中一定會逾時。
也就是說簡單粗暴是做不出來的，如果你有足夠多的做題經驗，你就會很自然地想到我們也許需要使用一些資料結構來優化這個查詢的複雜度。
肯定是不能接受的，即使不能優化到
，也至少可以試試。線段樹就是這樣的資料結構，我們直接來看一張圖，我們直接就可以搞明白線段樹究竟是幹嘛的，以及它的工作原理。
這張圖當中的a就是我們存資料的數組，這個數組上面的就是線段樹。我們從上往下看，給大家解釋一下。最上面一條隻有一個數字就是1，它代表的是整個數組的最小值是1。也就是說最上層維護的是整個區間的最小值。然後是第二層，在第二層我們看到了兩個數，分别是3和1。很明顯，3表示的是左半邊區間的最小值，1表示的右半邊區間的最小值。
到了第三行我們得到了4個數，同理，再下一層有8個數。很明顯這是一顆二叉樹，并且二叉樹當中的每一個節點維護了一個區間的值。它的葉子節點存儲的是長度為1的區間，也就是單個元素。我們把兩個兄弟節點維護的區間合并起來就得到了父節點的區間。在這道題當中，由于我們維護的是區間的最小值，是以我們可以得到這麼一個式子：
node.min = min(node.left.min, node.right.min)
是以線段樹就是利用了二叉樹這個層次結構對一個區間進行維護的資料結構。
線段樹查詢
我們已經了解了線段樹的結構了，剩下的就隻有兩個問題，一個是如何更新一個是如何求解。我發先來看求解，我們要求一個區間的最小值。我們來實際看一下，假設我們想要查詢下标是[2, 5]這個區間裡的最小值怎麼辦？
我們對照一下上面的數組a，下标[3, 6]這個區間對應的是[7, 9, 6, 4]這四個值。我們會發現不存在剛好隻包含這四個值的區間，那怎麼辦呢？其實很簡單，可以拼湊。我們可以發現我們可以把這個完整的區間轉化成兩個區間連接配接在一起的結果。比如下圖這樣。
這樣，我們就把原本比較[7, 9, 6, 4]四個值的一個查詢行為轉化成了隻需要比較4和7兩個值大小的比較行為了。這可以替我們節約大量的時間。這和記憶化搜尋有一點點像，相當于我們制定一個模式，根據這個模式把區間裡的最值存儲下來。這樣我們查詢的時候可以利用這些值來快速求解。
如果我們要求[2, 7]區間内的最小值，那麼我們可以轉而用這兩個區間的值求到。
線段樹更新
接下來我們來看下線段樹的更新，其實更新和查詢的原理是一樣的，同樣是從根節點出發一層層往下，一直到更新到葉子節點為止。假如說我們把資料當中的4更新成0，那麼會達成一種怎樣的效果呢？
從結果上來看，我們是把發生變更的葉子節點到樹根的這一整個鍊路都更新了。當然這個更新也不是強制發生的，因為如果我們更新的值比它的原值1要大的話，也是不會更新的。
代碼實作
關于線段樹的原理我們就差不多講完了，看起來不太長，這是很正常的。因為線段樹的原理其實很簡單，就是用一棵二叉樹來維護各個長度的區間。我們在查詢的時候就是要找到可以拼成我們查詢的區間的幾個子區間，用這些子區間的值來求到我們要查的區間的值。在我們更新的時候，不需要更新整棵樹，隻需要更新某一條從根節點到葉子節點的路徑就可以了。
原理看起來不難，了解起來也不難，但是要用代碼實作出來其實不太容易。因為線段樹的所有操作都是基于遞歸和回溯的，是以想要順利、深入地了解線段樹，對于遞歸以及回溯的掌握一定要過關。否則線段樹你寫起來很痛苦，寫完了調試會更痛苦。
我們會用面向對象的形式來建立一個線段樹，當然也有人喜歡用數組來模拟，這也是可以的，本質上都是一樣的。首先我們來建立一個節點類。這個節點類存儲的值有3個，一個是它維護的區間的值，在這個題目裡維護的是區間最小值。一個是區間的範圍， 左右邊界。另外一個是左右孩子節點。
由于我們在建立節點的時候還不知道它的左右孩子以及維護的值是什麼，是以我們先指派成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方法。我們建立線段樹的時候最重要的就是讓它當中的每一個節點能夠存儲對應區間的最小值。但是呢由于線段樹是有層次結構的，我們在建立區間[a, b]的時候，其實可以利用區間[a, m]和區間[m+1, b]兩個區間的最小值來擷取整個區間的最小值。也就是說我們可以利用目前節點的左右孩子節點完成，我們之前已經說過這點了。
我們來看代碼，通過遞歸可以很友善地完成這一點。
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表示區間範圍，左閉右開
if r - l < 1:
return None
node = Node(l, r)
# 如果區間長度是1，說明是葉子節點了，直接将val指派成對應的數值
if r - l == 1:
node.val = self.vals[l]
else:
# 否則遞歸調用
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
當然這個過程也可以用循環實作，隻不過用遞歸實作更加簡單。
如果你能看得到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這個節點維護的區間裡
if u.ls <= k < u.rs:
# 更新它的最小值
u.val = min(u.val, v)
m = (u.ls + u.rs) >> 1
# 判斷往左還是往右
if k < m:
self._update(u.left_child, k, v)
else:
self._update(u.right_child, k, v)
最後我們再來看query，query同樣是通過遞歸執行的。由于我們查詢的是一個區間，是以我們需要判斷我們查詢區間和節點維護區間之間的關系。隻要抓住了這一點，整個邏輯也是很簡單的。
def query(self, l, r):
return self._query(self.root, l, r)
def _query(self, u, l, r):
# l和r是查詢區間
# 如果查詢區間是u節點區間的超集
if l <= u.ls and r >= u.rs:
return u.val
# 如果查詢區間隻和u節點區間的左半部分有交集
elif r <= u.left_child.rs:
return self._query(u.left_child, l, r)
# 如果查詢區間隻和u節點右半部分有交集
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))
最後
到這裡，我們關于線段樹的基本介紹就算是結束了。注意我說的是基本介紹，因為線段樹有很多種用法，今天介紹的隻是其中最簡單的一種：單點更新區間查詢。除此之外還有區間更新單點查詢，區間更新區間查詢，掃描線等等相對高端一些的用法。由于篇幅所限不能一次講完，準備放在之後的文章當中分享給大家。
另外一點市面上線段樹的題目基本上都是用C++寫的，是以如果你想要找一道題試一下的話，可能需要用C++重新寫一遍。不過我相信這對于你們來說并不是什麼大問題。
今天的文章到這裡就結束了，如果喜歡本文的話，請給我一波三連支援吧（關注、轉發、點贊）。
原文連結，求個關注
本文使用 mdnice 排版
- END -
{{uploading-image-370795.png(uploading...)}}