線段樹詳解與實現
此篇文章用於記錄《玩轉資料結構》課程的學習筆記
什麼是線段樹
線段樹也被稱為區間樹，英文名為
Segment Tree
或者
Interval tree
，是一種高階的資料結構。這種資料結構更多出現在競賽中，在常見的本科資料結構教材裡沒有介紹這種資料結構。但是，在面試中卻有可能碰到和線段樹相關的問題。那麼為什麼會產生線段樹這種資料結構，線段樹到底是為了解決什麼樣的一種問題呢？
其實這裡的
線段
可以理解為
區間
，線段樹就是為了解決區間問題的。
有一個很經典的線段樹問題是：區間染色。
假設有一面牆，長度為 n，每次選擇一段牆進行染色。
在區間染色的過程中，每次選擇一段區間進行染色，這時新的顏色可能會覆蓋之前的顏色。
最後的問題是：
在經過 m 次染色操作後，我們可以在整個區間看見多少種顏色？
更加普遍的說法是：
在經過 m 次染色操作後，我們可以在區間
［i， j］
內看見多少種顏色？
由於第一個問題是第二個問題的一個特例，我們採用第二種問題來思考解決方法。
從上面可以看出，我們對於區間，有 2 種操作，分別是
染色操作
和
查詢區間的顏色
，使用更加一般的說法，
染色操作
就是
更新區間
，
查詢區間的顏色
就是
查詢區間
。
這類問題裡面，更加常見的的是區間查詢：一個數組存放的不再是顏色，而是具體的數字，查詢某個區間
［i， j］
的
統計值
。這裡的統計值是指：區間內最大值、最小值、或者這個區間的數字和。
比如：
查詢 2018 年註冊的使用者中消費最高的使用者
查詢 2018 年註冊的使用者中消費最低的使用者
注意上面兩種情況都是動態查詢，我們查詢的消費資料
不只是 2018 的消費資料
。
如果我們想查詢 2018 年中消費最高的使用者，那麼 2018 年的資料已經固定了，我們直接在這一年的資料中進行統計分析就行了。
但是一個 2018 年註冊的使用者，在 2019 年、2020 年都可能會有消費。我們實際上查詢的是：2018 年註冊的使用者中，到現在為止，消費最高的使用者。
這種情況下，資料是在動態變化的， 也就是說：2017 年註冊的使用者中，每個使用者的消費額是會更新的，這就對應到
更新區間
的操作。
此時線段樹就是一種好的選擇。
按照通常的思路，使用陣列儲存上述的元素是比較好的，思考上面兩個操作的時間複雜度：
更新區間
：每次根據需要更新的區間的首尾索引，逐個遍歷區間中的元素進行更新，時間複雜度為
O（n）
。
查詢區間
：每次根據需要更新的區間的首尾索引，逐個遍歷區間種的元素進行查詢，時間複雜度為
O（n）
。
兩個操作的時間複雜度均為
O（n）
，對於需要多次動態使用的場景來說，效能可能是不夠好的。
在這類問題中，我們關注的是一個個區間內的元素的情況，線段樹就有用武之地了，線段樹的優點就是把兩個操作的
時間複雜度降到了O(logn)
。
操作使用陣列使用線段樹
更新O（n）O（logn）查詢O（n）O（logn）
這裡提一點，如果你看到一個演算法的時間複雜度是
O（logn）
，那這個演算法大多與
二叉樹
、
分治
演算法有關。
這裡也不例外，線段樹就是使用二叉樹來實現的。
那麼一個區間是如何被構建成為一個二叉樹的？
對於一個數組 A，如下所示：
對應的線段樹就是：
二叉樹中每個
非葉子節點
表示的是區間內元素的
統計值
，
葉子節點
儲存的就是
元素本身
。上面說了統計值是指：區間內最大值、最小值、或者這個區間的數字和。比如你要求區間的最大值，每個每個節點儲存的就是這個區間內元素的最大值。像下面這樣：
假設你要查詢
［4，7］
區間內的最大值，那麼不用查到葉子節點，而是查到
A［4， 7］
這個節點就行了。
當然，並不是所有的區間都恰好落在一個節點，比如你要求
［2， 5］
區間內的最大值。那麼就要分別找到
A［2， 3］
和
A［4，5］
的最大值，再進行比較。
可以看出，線段樹的查詢區間操作不需要遍歷區間中的每一個元素，只要找到對應的樹節點就可以返回，時間複雜度為
O（logn）
。
總結
從更加抽象的角度來講，線段樹的使用場景就是，對於給定區間，進行更新區間和查詢區間操作：
更新區間：更新區間中的一個元素或者一個區間的值。
查詢區間：查詢一個區間
［i， j］
的最大值、最小值、或者區間的數字和。
注意，在大多數情況下，我們是不考慮區間裡新增元素和刪除元素的，我們假設區間的大小是固定的。
線段樹的表示
樹的一般表示方法是鏈式儲存，每個節點有兩個指標，一個指向左孩子，一個指向右孩子。但是滿二叉樹，和完全二叉樹，除了使用連結串列法來儲存，還可以使用陣列來表示。
在滿二叉樹和完全二叉樹的陣列表示中，假設一個節點的所以是
i
，那麼左孩子的索引就是
，右孩子的索引就是
。
那麼線段樹是不是滿二叉樹或者完全二叉樹呢？ 能不能使用陣列來表示呢？
在上面的例子中，我們的二叉樹恰好是一棵滿二叉樹，這是因為我們的陣列大小恰好是 8，也就是
，只有陣列大小恰好是 2 的 n 次冪，所對應的線段樹才會是一個滿二叉樹。在大部分情況下，線段樹並不是一個滿二叉樹。如果一個數組的大小是 10 ，對應的線段樹如下圖所示。
所以線段樹不是滿二叉樹，也不是完全二叉樹。但實際上：線段樹是平衡二叉樹，是可以保證
O（logn）
的時間複雜度的，這裡就不證明了。
其實平衡二叉樹可以看作特殊的滿二叉樹，進而使用陣列來表示。
下一步就是確定：對於大小為 n 的陣列，需要多大的空間來儲存線段樹。
首先說一個結論，對於高為 h 層的滿二叉樹，一共有
個節點，而最後一層有
個節點。那麼：
。也就是：前面所有層的節點數之和等於最後一層的節點數減 1。
那麼線段樹所需要的節點數量，分兩種情況來討論：
如果 n 恰好是 2 的 k 次冪，由於線段樹最後一層的葉子節點儲存的是陣列元素本身，最後一層的節點數就是 n，而根據上面的結論，前面所有層的節點數之和是
，那麼總節點數就是
。為了方便起見，分配
的空間。
如果 n 不是 2 的 k 次冪，最壞的情況就是
，那麼有一個元素需要開闢新的一層來儲存，需要
的大小。為了方便起見，我們分配
的空間，已經足夠了。
綜上，首先需要判斷陣列的大小是否為
，是則使用
的空間，否則使用的
空間。下面線段樹的實現是基於陣列來實現的，不過為了簡便起見，下面的實現統一使用
空間來儲存線段樹。
使用陣列來儲存線段樹，會有一定的空間浪費，但是換來的時間複雜度的降低是可以接受的。同時，我也在最後會介紹鏈式儲存的實現方式。
線段樹的實現
首先需要兩個陣列，其中
data
存放原來的資料，
tree
就是存放線段樹。
基本的 API 有
getSize（）
：返回陣列元素個數；
get（int index）
：根據索引獲取資料。
其中每個元素使用泛型
E
表示，這是為了考慮可擴充套件性：如果你的陣列元素不是數字，而是自定義的類，那麼使用泛型就是比較好的選擇。
public class SegmentTree
private E［］ tree； //線段樹
private E［］ data； //資料
public SegmentTree（E［］ arr） {
data = （E［］） new Object［arr。length］；
tree = （E［］） new Object［arr。length * 4］； //大小為 4 * n
for （int i = 0； i < arr。length； i++） {
data［i］ = arr［i］；
}
}
// 返回陣列元素個數
public int getSize（） {
return data。length；
}
// 根據索引獲取資料
public E get（int index） {
if （index < 0 || index > data。length）
throw new IllegalArgumentException（“Index is illegal”）；
return data［index］；
}
}
由於把線段樹看作一棵完全二叉樹，應該定義兩個 API，根據一個節點獲取到它的左孩子和右孩子。
// 根據一個節點的索引 index，返回這個節點的左孩子的索引
private int leftChild（int index） {
return 2 * index + 1；
}
// 根據一個節點的索引 index，返回這個節點的右孩子的索引
private int rightChild（int index） {
return 2 * index + 2；
}
線段樹的構建
下面考慮的就是構造線段樹的每個節點。這裡以求區間的最大值為例。
根節點儲存的是整個
［0，7］
區間的最大值，左孩子儲存的是
［0，3］
區間內的最大值，右孩子儲存的是
［4，7］
區間內的最大值。
我們要求根節點的值，首先求得左右兩個孩子的值，再從左右兩個孩子中取出較大的值作為根節點的值。要求父節點區間的值，需要先求孩子節點區間的值，這是遞迴的性質。所以可以透過遞迴來建立線段樹。
那麼這個遞迴的終止條件，也就是 base case，是什麼呢？
base case：如果一個節點的區間長度為1，不能再劃分，也就是遞迴到底了，就返回這個元素本身。
明確了思路，那麼我們的遞迴函式需要幾個引數？
首先，既然是建立節點，那麼需要節點在
tree
陣列中的索引；其次，這個節點對應的區間的左邊界和右邊界。
總共需要 3 個引數，寫出的程式碼如下：
// 在 treeIndex 的位置建立表示區間 ［l，r］ 的線段樹
private void buildSegmentTree（int treeIndex， int l， int r） {
// base case：遞迴到葉子節點了
if （l == r） {
tree［treeIndex］ = data［l］；
return；
}
int leftTreeIndex = leftChild（treeIndex）；
int rightTreeIndex = rightChild（treeIndex）；
//劃分區間
int mid = l + （r - l） / 2；
// 求（左孩子）左邊區間的最大值
buildSegmentTree（leftTreeIndex， l， mid）；
// 求（右孩子）右區間的最大值
buildSegmentTree（rightTreeIndex， mid + 1， r）；
//合併左右區間，求左區間和右區間點的最大值
tree［treeIndex］ = Math。max（tree［leftTreeIndex］， tree［rightTreeIndex］）；
}
當然這裡最後一句是會報錯的。因為
tree
的元素型別是泛型，不支援
Math。max（）
函式。
還有一個問題是：如果你在這裡把
區間合併的邏輯
寫成了只取最大值，那麼這個線段樹就只能求某個區間的最大值，不能用於求取區間的最小值、或者區間的和，限制了線段樹的應用場景。
一個更好的方法是：使用者可以根據自己的業務場景，自由選擇合併區間的邏輯。
要達成這個目的，我們需要建立一個介面，使用者需要實現這個介面來實現自己的區間合併邏輯。
//融合器，表示如何合併兩個區間的統計值
public interface Merger
// a 表示左區間的統計值，b 表示有區間的統計值
//返回整個［左區間+右區間］ 的統計值
E merge（E a， E b）；
}
線上段樹的建構函式中，新增一個
Merger
引數，並且呼叫
buildSegmentTree（）
構建線段樹。
public class SegmentTree
private E［］ tree； //線段樹
private E［］ data； //資料
private Merger
public SegmentTree（E［］ arr， Merger
this。merger = merger；
data = （E［］） new Object［arr。length］；
tree = （E［］） new Object［arr。length * 4］； //大小為 4 * n
for （int i = 0； i < arr。length； i++） {
data［i］ = arr［i］；
}
//構建線段樹
buildSegmentTree（0， 0， data。length - 1）；
}
。
。
。
}
然後，修改
buildSegmentTree（）
方法的最後一行。
// 在 treeIndex 的位置建立表示區間 ［l，r］ 的線段樹
private void buildSegmentTree（int treeIndex， int l， int r） {
// base case：遞迴到葉子節點了
if （l == r） {
tree［treeIndex］ = data［l］；
return；
}
int leftTreeIndex = leftChild（treeIndex）；
int rightTreeIndex = rightChild（treeIndex）；
//劃分區間
int mid = l + （r - l） / 2；
// 求（左孩子）左區間的統計值
buildSegmentTree（leftTreeIndex， l， mid）；
// 求（右孩子）右區間的統計值
buildSegmentTree（rightTreeIndex， mid + 1， r）；
//求當前節點 ［左區間+右區間］ 的統計值
tree［treeIndex］ = merger。merge（tree［leftTreeIndex］， tree［rightTreeIndex］）；
}
線段樹的查詢
我們用下面的陣列構建一棵線段樹，查詢區間
［2，5］
為例。
我們首先從根節點開始查詢：在區間
［0，7］
中查詢
［2，5］
。
將根節點的區間分為左孩子
［0，3］
和右孩子
［4，7］
，而我們的查詢的區間
［2，5］
，
不能其中一個孩子的區間完全包括
。
於是上述問題轉化為兩個子問題：
在區間
［0，3］
中查詢
［2，3］
；
在區間
［4，7］
中查詢
［4，5］
；
最後將
［2，3］
和
［4，5］
結果合併，得到區間
［2，5］
的結果。
將
［0，3］
劃分為左孩子
［0，1］
和右孩子
［2，3］
，此時
右
孩子剛好和查詢的區間重合，返回結果。
將
［4，7］
劃分為左孩子
［4，5］
和右孩子
［6，7］
，此時
左
孩子剛好和查詢的區間重合，返回結果。
從上面可以看出，線上段樹的區間查詢過程中，不需要遍歷區間中的每個元素，只需要線上段樹中找到對應的所有子區間，再將這些子區間的結果合併即可。而查詢所經過的節點數最多是樹的高度，時間複雜度為
O（logn）
。
而且上面的過程也是遞迴的過程。
遞迴終止條件就是：查詢區間的邊界和節點的邊界完全重合，就返回該節點的統計值。
如果不重合，那怎麼辦？
這時應該分 3 種情況：
如果查詢區間的
左邊界大於中間節點
，那麼就查詢右區間
如果查詢區間的
右邊界小於等於中間節點
，那麼就查詢左區間
如果不屬於上述兩種情況，那麼查詢的區間就要根據中間節點拆分
遞迴函式的引數應該有 4 個，
當前節點所在的區間的左邊界和右邊界
，
使用者要查詢的的區間的左邊界和右邊界
。
程式碼如下：
//在以 treeIndex 為根的線段樹中 ［l，r］ 的範圍裡，搜尋區間 ［queryL， queryR］
private E query（int treeIndex， int l， int r， int queryL， int queryR） {
if （l == queryL && r == queryR） {
return tree［treeIndex］；
}
int mid = l + （r - l） / 2；
int leftTreeIndex = leftChild（treeIndex）；
int rightTreeIndex = rightChild（treeIndex）；
// 如果左邊界大於中間節點，則查詢右區間
if （queryL > mid）
return query（rightTreeIndex， mid + 1， r， queryL， queryR）；
// 如果右邊界小於等於中間節點，則查詢左區間
if （queryR <= mid）
return query（leftTreeIndex， l， mid， queryL， queryR）；
// 如果上述兩種情況都不是，則根據中間節點，拆分為兩個查詢區間
E leftResult = query（leftTreeIndex， l， mid， queryL， mid）；
E rightResult = query（rightTreeIndex， mid + 1， r， mid + 1， queryR）；
//合併左右區間的查詢結果
return merger。merge（leftResult， rightResult）；
}
線段樹的更新
如下圖所示，更新
A［i］=100
，那麼將需要更新的索引
i
和區間的終點
mid
，分為兩種情況。
如果
i>mid
，那麼索引
i
落在右區間，更新右區間；
如果
i<=mid
，那麼索引
i
落在左區間，更新左區間；
那麼遞迴的終止條件是什麼呢？
當遞迴到葉子節點的時候，就值更新這個節點：葉子節點就是區間長度為 1 的節點。
當更新完葉子節點後，還需要回溯，更新父節點區間的統計值。
程式碼如下：
//將 index 位置的值，更新為 e
public void update（int index， E e） {
if （index < 0 || index >= data。length）
throw new IllegalArgumentException（“Index is illegal”）；
data［index］ = e；
//更新線段樹相應的節點
updateTree（0， 0， data。length - 1， index， e）；
}
// 在以 treeIndex 為根的線段樹中，更新 index 的值為 e
private void updateTree（int treeIndex， int l， int r， int index， E e） {
//遞迴終止條件
if （l == r） {
tree［treeIndex］ = e；
return；
}
int mid = l + （r - l） / 2；
int leftTreeIndex = leftChild（treeIndex）；
int rightTreeIndex = rightChild（treeIndex）；
if （index > mid）
updateTree（rightTreeIndex， mid + 1， r， index， e）；
else //index <= mid
updateTree（leftTreeIndex， l， mid， index， e）；
//更新當前節點
tree［treeIndex］ = merger。merge（tree［leftTreeIndex］， tree［rightTreeIndex］）；
}
完整程式碼
public class SegmentTree
private E［］ tree； //線段樹
private E［］ data； //資料
private Merger
public SegmentTree（E［］ arr， Merger
this。merger = merger；
data = （E［］） new Object［arr。length］；
tree = （E［］） new Object［arr。length * 4］； //大小為 4 * n
for （int i = 0； i < arr。length； i++） {
data［i］ = arr［i］；
}
//構建線段樹
buildSegmentTree（0， 0， data。length - 1）；
}
// 返回陣列元素個數
public int getSize（） {
return data。length；
}
// 根據索引獲取資料
public E get（int index） {
if （index < 0 || index > data。length）
throw new IllegalArgumentException（“Index is illegal”）；
return data［index］；
}
//根據一個節點的索引 index，返回這個節點的左孩子的索引
private int leftChild（int index） {
return 2 * index + 1；
}
//根據一個節點的索引 index，返回這個節點的右孩子的索引
private int rightChild（int index） {
return 2 * index + 2；
}
// 在 treeIndex 的位置建立表示區間 ［l，r］ 的線段樹
private void buildSegmentTree（int treeIndex， int l， int r） {
// base case：遞迴到葉子節點了
if （l == r） {
tree［treeIndex］ = data［l］；
return；
}
int leftTreeIndex = leftChild（treeIndex）；
int rightTreeIndex = rightChild（treeIndex）；
//劃分區間
int mid = l + （r - l） / 2；
// 求（左孩子）左區間的統計值
buildSegmentTree（leftTreeIndex， l， mid）；
// 求（右孩子）右區間的統計值
buildSegmentTree（rightTreeIndex， mid + 1， r）；
//求當前節點 ［左區間+右區間］ 的統計值
tree［treeIndex］ = merger。merge（tree［leftTreeIndex］， tree［rightTreeIndex］）；
}
//查詢區間，返回區間 ［queryL， queryR］ 的統計值
public E query（int queryL， int queryR） {
//首先進行邊界檢查
if （queryL < 0 || queryL > data。length || queryR < 0 || queryR > data。length || queryL > queryR） {
throw new IllegalArgumentException（“Index is illegal”）；
}
return query（0， 0， data。length - 1， queryL， queryR）；
}
//在以 treeIndex 為根的線段樹中 ［l，r］ 的範圍裡，搜尋區間 ［queryL， queryR］
private E query（int treeIndex， int l， int r， int queryL， int queryR） {
if （l == queryL && r == queryR） {
return tree［treeIndex］；
}
int mid = l + （r - l） / 2；
int leftTreeIndex = leftChild（treeIndex）；
int rightTreeIndex = rightChild（treeIndex）；
// 如果左邊界大於中間節點，則查詢右區間
if （queryL > mid）
return query（rightTreeIndex， mid + 1， r， queryL， queryR）；
// 如果右邊界小於等於中間節點，則查詢左區間
if （queryR <= mid）
return query（leftTreeIndex， l， mid， queryL， queryR）；
// 如果上述兩種情況都不是，則根據中間節點，拆分為兩個查詢區間
E leftResult = query（leftTreeIndex， l， mid， queryL， mid）；
E rightResult = query（rightTreeIndex， mid + 1， r， mid + 1， queryR）；
//合併左右區間的查詢結果
return merger。merge（leftResult， rightResult）；
}
//將 index 位置的值，更新為 e
public void update（int index， E e） {
if （index < 0 || index >= data。length）
throw new IllegalArgumentException（“Index is illegal”）；
data［index］ = e；
//更新線段樹相應的節點
updateTree（0， 0， data。length - 1， index， e）；
}
// 在以 treeIndex 為根的線段樹中，更新 index 的值為 e
private void updateTree（int treeIndex， int l， int r， int index， E e） {
//遞迴終止條件
if （l == r） {
tree［treeIndex］ = e；
return；
}
int mid = l + （r - l） / 2；
int leftTreeIndex = leftChild（treeIndex）；
int rightTreeIndex = rightChild（treeIndex）；
if （index > mid）
updateTree（rightTreeIndex， mid + 1， r， index， e）；
else //index <= mid
updateTree（leftTreeIndex， l， mid， index， e）；
//更新當前節點
tree［treeIndex］ = merger。merge（tree［leftTreeIndex］， tree［rightTreeIndex］）；
}
public String toString（） {
StringBuffer res = new StringBuffer（）；
res。append（‘［’）；
for （int i = 0； i < tree。length； i++） {
if （tree［i］ ！= null）
res。append（tree［i］）；
else res。append（“null”）；
if （i ！= tree。length - 1）
res。append（“， ”）；
}
res。append（‘］’）；
return res。toString（）；
}
}
使用例子
定義一個求區間的最大值的線段樹，程式碼如下：
public class Main {
public static void main（String［］ args） {
Integer［］ nums = new Integer［］{34， 65， 8， 10， 21， 86， 79， 30}；
SegmentTree
@Override
public Integer merge（Integer a， Integer b） {
//返回 a 和 b 的最大值
return Math。max（a， b）；
}
}）；
// 查詢區間 ［2，5］ 的最大值
System。out。println（segTree。query（4， 7））；
}
}
當然，你也可以定義一個求區間內元素的和的線段樹，只需要修改
merge（）
方法的實現即可：
public class Main {
public static void main（String［］ args） {
Integer［］ nums = new Integer［］{34， 65， 8， 10， 21， 86， 79， 30}；
SegmentTree
@Override
public Integer merge（Integer a， Integer b） {
//返回 a 和 b 的和
return a + b；
}
}）；
// 查詢區間 ［2，5］ 的和
System。out。println（segTree。query（4， 7））；
}
}
LeetCode 上相關的題目
303. 區域檢索和-陣列不可變
題目連結：
303. 區域和檢索 - 陣列不可變
線段樹求解
這道題是求取區間和，可以使用線段樹來實現。時間複雜度為
O（logn）
，空間複雜度為
O（n）
。
class NumArray {
private int［］ tree；
private int［］ data；
public NumArray（int［］ nums） {
data = nums；
tree = new int［nums。length * 4］；
//當陣列長度大於 0 時，才建立線段樹
if （nums。length > 0）
//建立線段樹
buildSegmentTree（0， 0， nums。length - 1）；
}
//根據一個節點的索引 index，返回這個節點的左孩子的索引
private int leftChild（int index） {
return 2 * index + 1；
}
//根據一個節點的索引 index，返回這個節點的右孩子的索引
private int rightChild（int index） {
return 2 * index + 2；
}
// 在 treeIndex 的位置建立表示區間 ［l，r］ 的線段樹
private void buildSegmentTree（int treeIndex， int l， int r） {
//遞迴終止條件：區間長度為 1
if （l == r） {
tree［treeIndex］ = data［l］；
return；
}
int leftTreeIndex = leftChild（treeIndex）；
int rightTreeIndex = rightChild（treeIndex）；
int mid = l + （r - l） / 2；
//建立左區間（左孩子）的和
buildSegmentTree（leftTreeIndex， l， mid）；
//建立右區間（右孩子）的和
buildSegmentTree（rightTreeIndex， mid + 1， r）；
//合併做有區間的和
tree［treeIndex］ = tree［leftTreeIndex］ + tree［rightTreeIndex］；
}
public int sumRange（int i， int j） {
//tree。length == 1 表示陣列沒有元素，直接返回 0
if （tree。length == 1）
return 0；
return queryRange（0， 0， data。length - 1， i， j）；
}
//在以 treeIndex 為根的線段樹中 ［l，r］ 的範圍裡，搜尋區間 ［queryL， queryR］
private int queryRange（int treeIndex， int l， int r， int queryL， int queryR） {
if （queryL == l && queryR == r）
return tree［treeIndex］；
int mid = l + （r - l） / 2；
int leftTreeIndex = leftChild（treeIndex）；
int rightTreeIndex = rightChild（treeIndex）；
// 如果左邊界大於中間節點，則查詢右區間
if （queryL > mid）
return queryRange（rightTreeIndex， mid + 1， r， queryL， queryR）；
// 如果右邊界小於等於中間節點，則查詢左區間
if （queryR <= mid）
return queryRange（leftTreeIndex， l， mid， queryL， queryR）；
// 如果上述兩種情況都不是，則根據中間節點，拆分為兩個查詢區間
int leftResult = queryRange（leftTreeIndex， l， mid， queryL， mid）；
int rightResult = queryRange（rightTreeIndex， mid + 1， r， mid + 1， queryR）；
//合併左右區間的查詢結果
return leftResult + rightResult；
}
}
字首和求解
其實這道題有更加高效的解法，那就是
字首和
。
字首和的定義是：定義一個字首和陣列
sum
，每個元素
sum［i］
表示的是
nums［0。。。i］
區間中的元素的和。
那麼我們要求
［i，j］
區間的和，就可以使用
sum［j］-sum［i-1］
得到。
注意當
i=0
時，
i-1=-1
會溢位。因此
sums
陣列應該整體向後移動一位。
sum［0］=0
表示前面沒有元素，和應該是 0。
此時
［i，j］
區間的和應該是
sum［j+1］-sum［i］
。
程式碼如下：
class NumArray {
//字首和陣列
private int［］ sums；
public NumArray（int［］ nums） {
//邊界條件判斷
if （nums == null || nums。length == 0） {
sums = new int［］{}；
}
int n = nums。length；
//由於整體後移了一位，長度應該為 n+1
sums = new int［n + 1］；
//構建字首和
for （int i = 0； i < n； i++） {
sums［i + 1］ = sums［i］ + nums［i］；
}
}
public int sumRange（int i， int j） {
if （sums。length == 0）
return 0；
//直接返回字首和相減的結果
return sums［j + 1］ - sums［i］；
}
}
使用字首和陣列的空間複雜度依然是
O（n）
，但時間複雜度是
O（1）
，優於線段樹。
那既然這樣，區間問題為什麼還要用線段樹呢？
因為這道題目加了一個限制：
陣列不可變
，也就是說數組裡的元素是固定的。
如果陣列的內容是可變的，那麼每次更新索引
［i］
的資料，相應的
［i。。。n］
區間的字首和都需要更新。字首和陣列更新的時間時間複雜度是
O（n）
，而線段樹的更新複雜度是
O（logn）
。
因此，在陣列內容可變的情況下，線段樹依然是更優的選擇。
303. 區域檢索和-陣列可修改
題目連結：
307. 區域和檢索 - 陣列可修改
字首和求解
根據上面字首和的做法，我們只需要新增更新資料和對應的字首和的邏輯即可。
class NumArray {
int［］ sums；
int［］ data；
public NumArray（int［］ nums） {
//邊界條件判斷
if （nums == null || nums。length == 0） {
sums = new int［］{}；
}
data = nums；
int n = nums。length；
//由於整體後移了一位，長度應該為 n+1
sums = new int［n + 1］；
//構建字首和
for （int i = 0； i < n； i++） {
sums［i + 1］ = sums［i］ + nums［i］；
}
}
public void update（int i， int val） {
// 更新陣列
data［i］ = val；
//更新從 i 到 n 的字首和
for （int j = i； j < data。length； j++） {
sums［j + 1］ = sums［j］ + data［j］；
}
}
public int sumRange（int i， int j） {
if （sums。length == 0）
return 0；
//直接返回字首和相減的結果
return sums［j + 1］ - sums［i］；
}
}
update（）
方法的時間複雜度是
O（n）
，
sumRange（）
方法的時間複雜度是
O（1）
。
線段樹求解
同理，這裡只需要在上面
303. 區域和檢索 - 陣列不可變
的線段樹解法上，新增更新的線段樹的邏輯即可。
class NumArray {
int［］ tree；
int［］ data；
public NumArray（int［］ nums） {
data = nums；
int n = nums。length；
if （nums == null || nums。length == 0） {
tree = new int［］{}；
return；
}
tree = new int［n * 4］；
buildSegmentTree（0， 0， data。length - 1）；
}
private void buildSegmentTree（int treeIndex， int l， int r） {
// base case：遞迴到葉子節點了
if （l == r） {
tree［treeIndex］ = data［l］；
return；
}
//劃分區間
int mid = l + （r - l） / 2；
int leftTreeIndex = leftChild（treeIndex）；
int rightTreeIndex = rightChild（treeIndex）；
// 求（左孩子）左區間的統計值
buildSegmentTree（leftTreeIndex， l， mid）；
// 求（右孩子）右區間的統計值
buildSegmentTree（rightTreeIndex， mid + 1， r）；
//求當前節點 ［左區間+右區間］ 的統計值
tree［treeIndex］ = tree［leftTreeIndex］ + tree［rightTreeIndex］；
}
private int leftChild（int treeIndex） {
return 2 * treeIndex + 1；
}
private int rightChild（int treeIndex） {
return 2 * treeIndex + 2；
}
//將 index 位置的值，更新為 e
public void update（int i， int val） {
// 更新陣列
data［i］ = val；
//更新線段樹
updateTree（0， i， 0， data。length - 1）；
}
// 在以 treeIndex 為根的線段樹中，更新 index 的值為 e
private void updateTree（int treeIndex， int index， int l， int r） {
//遞迴終止條件
if （l == r） {
tree［treeIndex］ = data［l］；
return；
}
int mid = l + （r - l） / 2；
int leftTreeIndex = leftChild（treeIndex）；
int rightTreeIndex = rightChild（treeIndex）；
if （index <= mid）
updateTree（leftTreeIndex， index， l， mid）；
else //index <= mid
updateTree（rightTreeIndex， index， mid + 1， r）；
//更新當前節點
tree［treeIndex］ = tree［leftTreeIndex］ + tree［rightTreeIndex］；
}
public int sumRange（int i， int j） {
if （data。length == 0）
return 0；
return queryRange（0， 0， data。length - 1， i， j）；
}
private int queryRange（int treeIndex， int l， int r， int queryL， int queryR） {
if （l == queryL && r == queryR） {
return tree［treeIndex］；
}
int mid = l + （r - l） / 2；
int leftTreeIndex = leftChild（treeIndex）；
int rightTreeIndex = rightChild（treeIndex）；
if （queryL > mid）
return queryRange（rightTreeIndex， mid + 1， r， queryL， queryR）；
if （queryR <= mid）
return queryRange（leftTreeIndex， l， mid， queryL， queryR）；
int leftResult = queryRange（leftTreeIndex， l， mid， queryL， mid）；
int rightResult = queryRange（rightTreeIndex， mid + 1， r， mid + 1， queryR）；
return leftResult + rightResult；
}
}
update（）
方法和
sumRange（）
方法的時間複雜度都是
O（n）
。
總結與擴充套件
線段樹，雖然不是滿二叉樹。但是我們卻可以把它看作一棵滿二叉樹，進而使用陣列來儲存這棵樹。
其次，線上段樹中，我們定義了每個節點，儲存的資料是這個節點對應區間的統計值（最大值、最小值、區間和）。透過這一點，你可以體會到，對於樹中的節點，你可以賦予它獨特的定義，進而可以高效地解決各種各樣的問題。因此，樹的使用範圍是非常廣泛的。
對於，線段樹的構建、更新區間、和查詢區間，這 3 個操作，都是先遞迴訪問葉子節點，然後再回溯訪問父節點，合併左右孩子區間的結果，這本質上是一種
後序遍歷
的思想。
對一個區間進行更新
在本文的例子中，每次更新都是對一個元素進行更新。現在考慮另一種更新：對某個區間內的所有元素進行更新。
比如：將
［2，5］
區間中的所有元素都加 3，就需要遍歷這個區間中的每個元素，區間更新的時間複雜度就變為了
O（n）
。為了降低區間更新的複雜度，有一種專門的方法：
懶惰更新
。
懶惰更新的思想是：在每次更新區間時，我們實際上先不更新實際的資料，而是使用另一個
lazy
陣列，來標記這些未更新的內容。
那麼什麼時候才會更新這些節點呢？
當我們下一次更新或者查詢到這些資料時，先查一下
lazy
陣列中是否有資料未更新，然後將未更新的內容進行更新，再訪問對應的資料。
例如：
第一次：將
［2，5］
區間中的所有元素都加 3，實際上
lazy
陣列就會標記
［2，5］
區間的資料未更新；
第二次：將
［4，7］
區間中的所有元素都減 5。這時，查詢
lazy
陣列中，發現
［4，5］
區間的資料未更新，那麼先更新
［4，5］
區間的內容，
［2，3］
區間的標記不變。然後標記
［4，7］
區間中的內容未更新。
透過懶惰更新，時間複雜度降為了
O（logn）
。
二維線段樹
在這篇文章中，我們處理的都是一維的線段樹，實際中還可以產生二位線段樹。
一維線段樹，就是資料都是一維陣列，每個節點記錄的區間只有左右兩個邊界。
在二維線段樹中，資料是二維陣列，也就是一個矩陣，每個節點記錄的區間有上下左右兩個邊界。那麼每個節點就有 4 個孩子。
進一步擴充套件，你也可以設計出 3 維的線段樹，甚至更高維的線段樹。
線段樹是一種設計思想，利用樹這種資料結構，如何把一個大的資料單元，遞迴地拆分為小的資料單元，同時，利用樹這種資料結構，可以高效地進行查詢、更新等操作。
動態線段樹
在這篇文章中，我使用了陣列這種資料結構來儲存樹，造成了空間的浪費。實際上，我們可以也使用鏈式儲存，可以更好地利用空間。
實際上，動態線段樹有一個更加重要的應用，。例如，我們要儲存 10000000 大小的線段樹，但是不會對這麼大一個區間中的每一個部分都進行訪問，可能只會對一種某個小部分進行訪問。
那麼我們可以不用一開始就建立這麼巨大的線段樹，而是隻建立一個根節點，等到實際訪問某個區間時，在根據區間的邊界，動態地建立線段樹。
樹狀陣列
這篇文章講的線段樹，實際上是對區間操作的一種資料結構。與區間操作相關的資料結構，還有另外一個：樹狀陣列，英文名為
Binary Index Tree
。感興趣可以自行查閱。
如果你覺得這篇文章對你有幫助，不妨點個贊，讓我有更多動力寫出好文章。
我的文章會首發在公眾號上，歡迎掃碼關注我的公眾號
「張賢同學」
。
