此篇文章用于記錄《玩轉(zhuǎn)數(shù)據(jù)結(jié)構(gòu)》課程的學(xué)習(xí)筆記

什么是線段樹

線段樹也被稱為區(qū)間樹，英文名為Segment Tree或者Interval tree，是一種高級的數(shù)據(jù)結(jié)構(gòu)。這種數(shù)據(jù)結(jié)構(gòu)更多出現(xiàn)在競賽中，在常見的本科數(shù)據(jù)結(jié)構(gòu)教材里沒有介紹這種數(shù)據(jù)結(jié)構(gòu)。但是，在面試中卻有可能碰到和線段樹相關(guān)的問題。那么為什么會產(chǎn)生線段樹這種數(shù)據(jù)結(jié)構(gòu)，線段樹到底是為了解決什么樣的一種問題呢？

其實這里的線段可以理解為區(qū)間，線段樹就是為了解決區(qū)間問題的。

有一個很經(jīng)典的線段樹問題是：區(qū)間染色。

假設(shè)有一面墻，長度為 n，每次選擇一段墻進(jìn)行染色。

在區(qū)間染色的過程中，每次選擇一段區(qū)間進(jìn)行染色，這時新的顏色可能會覆蓋之前的顏色。

最后的問題是：

• 在經(jīng)過 m 次染色操作后，我們可以在整個區(qū)間看見多少種顏色？

更加普遍的說法是：

• 在經(jīng)過 m 次染色操作后，我們可以在區(qū)間 [i, j]內(nèi)看見多少種顏色？

由于第一個問題是第二個問題的一個特例，我們采用第二種問題來思考解決方法。

從上面可以看出，我們對于區(qū)間，有 2 種操作，分別是染色操作和查詢區(qū)間的顏色，使用更加一般的說法，染色操作就是更新區(qū)間，查詢區(qū)間的顏色就是查詢區(qū)間。

這類問題里面，更加常見的的是區(qū)間查詢：一個數(shù)組存放的不再是顏色，而是具體的數(shù)字，查詢某個區(qū)間[i, j]的統(tǒng)計值。這里的統(tǒng)計值是指：區(qū)間內(nèi)最大值、最小值、或者這個區(qū)間的數(shù)字和。

比如：

• 查詢 2018 年注冊的用戶中消費最高的用戶
• 查詢 2018 年注冊的用戶中消費最低的用戶

注意上面兩種情況都是動態(tài)查詢，我們查詢的消費數(shù)據(jù)不只是 2018 的消費數(shù)據(jù)。

如果我們想查詢 2018 年中消費最高的用戶，那么 2018 年的數(shù)據(jù)已經(jīng)固定了，我們直接在這一年的數(shù)據(jù)中進(jìn)行統(tǒng)計分析就行了。

但是一個 2018 年注冊的用戶，在 2019 年、2020 年都可能會有消費。我們實際上查詢的是：2018 年注冊的用戶中，到現(xiàn)在為止，消費最高的用戶。

這種情況下，數(shù)據(jù)是在動態(tài)變化的， 也就是說：2017 年注冊的用戶中，每個用戶的消費額是會更新的，這就對應(yīng)到更新區(qū)間的操作。

此時線段樹就是一種好的選擇。

按照通常的思路，使用數(shù)組存儲上述的元素是比較好的，思考上面兩個操作的時間復(fù)雜度：

• 更新區(qū)間：每次根據(jù)需要更新的區(qū)間的首尾索引，逐個遍歷區(qū)間中的元素進(jìn)行更新，時間復(fù)雜度為O(n)。
• 查詢區(qū)間：每次根據(jù)需要更新的區(qū)間的首尾索引，逐個遍歷區(qū)間種的元素進(jìn)行查詢，時間復(fù)雜度為O(n)。

兩個操作的時間復(fù)雜度均為O(n)，對于需要多次動態(tài)使用的場景來說，性能可能是不夠好的。

在這類問題中，我們關(guān)注的是一個個區(qū)間內(nèi)的元素的情況，線段樹就有用武之地了，線段樹的優(yōu)點就是把兩個操作的時間復(fù)雜度降到了O(logn)。

操作使用數(shù)組使用線段樹

更新	O(n)	O(logn)
查詢	O(n)	O(logn)

這里提一點，如果你看到一個算法的時間復(fù)雜度是O(logn)，那這個算法大多與二叉樹、分治算法有關(guān)。

這里也不例外，線段樹就是使用二叉樹來實現(xiàn)的。

那么一個區(qū)間是如何被構(gòu)建成為一個二叉樹的？

對于一個數(shù)組 A，如下所示：

對應(yīng)的線段樹就是：

二叉樹中每個非葉子節(jié)點表示的是區(qū)間內(nèi)元素的統(tǒng)計值，葉子節(jié)點存儲的就是元素本身。上面說了統(tǒng)計值是指：區(qū)間內(nèi)最大值、最小值、或者這個區(qū)間的數(shù)字和。比如你要求區(qū)間的最大值，每個每個節(jié)點存儲的就是這個區(qū)間內(nèi)元素的最大值。像下面這樣：

假設(shè)你要查詢[4,7]區(qū)間內(nèi)的最大值，那么不用查到葉子節(jié)點，而是查到A[4, 7]這個節(jié)點就行了。

當(dāng)然，并不是所有的區(qū)間都恰好落在一個節(jié)點，比如你要求[2, 5]區(qū)間內(nèi)的最大值。那么就要分別找到A[2, 3]和A[4,5]的最大值，再進(jìn)行比較。

可以看出，線段樹的查詢區(qū)間操作不需要遍歷區(qū)間中的每一個元素，只要找到對應(yīng)的樹節(jié)點就可以返回，時間復(fù)雜度為O(logn)。

總結(jié)

從更加抽象的角度來講，線段樹的使用場景就是，對于給定區(qū)間，進(jìn)行更新區(qū)間和查詢區(qū)間操作：

• 更新區(qū)間：更新區(qū)間中的一個元素或者一個區(qū)間的值。
• 查詢區(qū)間：查詢一個區(qū)間[i, j]的最大值、最小值、或者區(qū)間的數(shù)字和。

注意，在大多數(shù)情況下，我們是不考慮區(qū)間里添加元素和刪除元素的，我們假設(shè)區(qū)間的大小是固定的。

線段樹的表示

樹的一般表示方法是鏈?zhǔn)酱鎯?#xff0c;每個節(jié)點有兩個指針，一個指向左孩子，一個指向右孩子。但是滿二叉樹，和完全二叉樹，除了使用鏈表法來存儲，還可以使用數(shù)組來表示。

在滿二叉樹和完全二叉樹的數(shù)組表示中，假設(shè)一個節(jié)點的所以是i，那么左孩子的索引就是，右孩子的索引就是。

那么線段樹是不是滿二叉樹或者完全二叉樹呢？ 能不能使用數(shù)組來表示呢？

在上面的例子中，我們的二叉樹恰好是一棵滿二叉樹，這是因為我們的數(shù)組大小恰好是 8，也就是，只有數(shù)組大小恰好是 2 的 n 次冪，所對應(yīng)的線段樹才會是一個滿二叉樹。在大部分情況下，線段樹并不是一個滿二叉樹。如果一個數(shù)組的大小是 10 ，對應(yīng)的線段樹如下圖所示。

所以線段樹不是滿二叉樹，也不是完全二叉樹。但實際上：線段樹是平衡二叉樹，是可以保證O(logn)的時間復(fù)雜度的，這里就不證明了。

其實平衡二叉樹可以看作特殊的滿二叉樹，進(jìn)而使用數(shù)組來表示。

下一步就是確定：對于大小為 n 的數(shù)組，需要多大的空間來存儲線段樹。

首先說一個結(jié)論，對于高為 h 層的滿二叉樹，一共有個節(jié)點，而最后一層有個節(jié)點。那么：。也就是：前面所有層的節(jié)點數(shù)之和等于最后一層的節(jié)點數(shù)減 1。

那么線段樹所需要的節(jié)點數(shù)量，分兩種情況來討論：

• 如果 n 恰好是 2 的 k 次冪，由于線段樹最后一層的葉子節(jié)點存儲的是數(shù)組元素本身，最后一層的節(jié)點數(shù)就是 n，而根據(jù)上面的結(jié)論，前面所有層的節(jié)點數(shù)之和是，那么總節(jié)點數(shù)就是。為了方便起見，分配的空間。

• 如果 ?n 不是 2 的 k 次冪，最壞的情況就是，那么有一個元素需要開辟新的一層來存儲，需要的大小。為了方便起見，我們分配的空間，已經(jīng)足夠了。

綜上，首先需要判斷數(shù)組的大小是否為 ，是則使用 的空間，否則使用的 空間。下面線段樹的實現(xiàn)是基于數(shù)組來實現(xiàn)的，不過為了簡便起見，下面的實現(xiàn)統(tǒng)一使用 空間來存儲線段樹。

使用數(shù)組來存儲線段樹，會有一定的空間浪費，但是換來的時間復(fù)雜度的降低是可以接受的。同時，我也在最后會介紹鏈?zhǔn)酱鎯Φ膶崿F(xiàn)方式。

線段樹的實現(xiàn)

首先需要兩個數(shù)組，其中data存放原來的數(shù)據(jù)，tree就是存放線段樹。

基本的 API ?有g(shù)etSize()：返回數(shù)組元素個數(shù)；get(int index)：根據(jù)索引獲取數(shù)據(jù)。

其中每個元素使用泛型E表示，這是為了考慮可擴(kuò)展性：如果你的數(shù)組元素不是數(shù)字，而是自定義的類，那么使用泛型就是比較好的選擇。

public class SegmentTree { private E[] tree; //線段樹 private E[] data; //數(shù)據(jù) 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]; } } // 返回數(shù)組元素個數(shù) public int getSize() { return data.length; } // 根據(jù)索引獲取數(shù)據(jù) public E get(int index) { if (index < 0 || index > data.length) throw new IllegalArgumentException("Index is illegal"); return data[index]; }}

由于把線段樹看作一棵完全二叉樹，應(yīng)該定義兩個 API，根據(jù)一個節(jié)點獲取到它的左孩子和右孩子。

// 根據(jù)一個節(jié)點的索引 index，返回這個節(jié)點的左孩子的索引private int leftChild(int index) { return 2 * index + 1;}// 根據(jù)一個節(jié)點的索引 index，返回這個節(jié)點的右孩子的索引private int rightChild(int index) { return 2 * index + 2;}

線段樹的構(gòu)建

下面考慮的就是構(gòu)造線段樹的每個節(jié)點。這里以求區(qū)間的最大值為例。

根節(jié)點存儲的是整個[0,7]區(qū)間的最大值，左孩子存儲的是[0,3]區(qū)間內(nèi)的最大值，右孩子存儲的是[4,7]區(qū)間內(nèi)的最大值。

我們要求根節(jié)點的值，首先求得左右兩個孩子的值，再從左右兩個孩子中取出較大的值作為根節(jié)點的值。要求父節(jié)點區(qū)間的值，需要先求孩子節(jié)點區(qū)間的值，這是遞歸的性質(zhì)。所以可以通過遞歸來創(chuàng)建線段樹。

那么這個遞歸的終止條件，也就是 base case，是什么呢？

• base case：如果一個節(jié)點的區(qū)間長度為1，不能再劃分，也就是遞歸到底了，就返回這個元素本身。

明確了思路，那么我們的遞歸函數(shù)需要幾個參數(shù)？

首先，既然是創(chuàng)建節(jié)點，那么需要節(jié)點在tree數(shù)組中的索引；其次，這個節(jié)點對應(yīng)的區(qū)間的左邊界和右邊界。

總共需要 3 個參數(shù)，寫出的代碼如下：

// 在 treeIndex 的位置創(chuàng)建表示區(qū)間 [l,r] 的線段樹private void buildSegmentTree(int treeIndex, int l, int r) { // base case：遞歸到葉子節(jié)點了 if (l == r) { tree[treeIndex] = data[l]; return; } int leftTreeIndex = leftChild(treeIndex); int rightTreeIndex = rightChild(treeIndex); //劃分區(qū)間 int mid = l + (r - l) / 2; // 求(左孩子)左邊區(qū)間的最大值 buildSegmentTree(leftTreeIndex, l, mid); // 求(右孩子)右區(qū)間的最大值 buildSegmentTree(rightTreeIndex, mid + 1, r); //合并左右區(qū)間，求左區(qū)間和右區(qū)間點的最大值 tree[treeIndex] = Math.max(tree[leftTreeIndex], tree[rightTreeIndex]);}

當(dāng)然這里最后一句是會報錯的。因為tree的元素類型是泛型，不支持Math.max()函數(shù)。

還有一個問題是：如果你在這里把區(qū)間合并的邏輯寫成了只取最大值，那么這個線段樹就只能求某個區(qū)間的最大值，不能用于求取區(qū)間的最小值、或者區(qū)間的和，限制了線段樹的應(yīng)用場景。

一個更好的方法是：用戶可以根據(jù)自己的業(yè)務(wù)場景，自由選擇合并區(qū)間的邏輯。

要達(dá)成這個目的，我們需要創(chuàng)建一個接口，用戶需要實現(xiàn)這個接口來實現(xiàn)自己的區(qū)間合并邏輯。

//融合器，表示如何合并兩個區(qū)間的統(tǒng)計值public interface Merger { // a 表示左區(qū)間的統(tǒng)計值，b 表示有區(qū)間的統(tǒng)計值 //返回整個[左區(qū)間+右區(qū)間] 的統(tǒng)計值 E merge(E a, E b);}

在線段樹的構(gòu)造函數(shù)中，添加一個Merger參數(shù)，并且調(diào)用buildSegmentTree()構(gòu)建線段樹。

public class SegmentTree { private E[] tree; //線段樹 private E[] data; //數(shù)據(jù) private Merger merger;//融合器 public SegmentTree(E[] arr, Merger 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]; } //構(gòu)建線段樹 buildSegmentTree(0, 0, data.length - 1); } . . .}

然后，修改buildSegmentTree()方法的最后一行。

// 在 treeIndex 的位置創(chuàng)建表示區(qū)間 [l,r] 的線段樹private void buildSegmentTree(int treeIndex, int l, int r) { // base case：遞歸到葉子節(jié)點了 if (l == r) { tree[treeIndex] = data[l]; return; } int leftTreeIndex = leftChild(treeIndex); int rightTreeIndex = rightChild(treeIndex); //劃分區(qū)間 int mid = l + (r - l) / 2; // 求(左孩子)左區(qū)間的統(tǒng)計值 buildSegmentTree(leftTreeIndex, l, mid); // 求(右孩子)右區(qū)間的統(tǒng)計值 buildSegmentTree(rightTreeIndex, mid + 1, r); //求當(dāng)前節(jié)點 [左區(qū)間+右區(qū)間] 的統(tǒng)計值 tree[treeIndex] = merger.merge(tree[leftTreeIndex], tree[rightTreeIndex]);}

線段樹的查詢

我們用下面的數(shù)組構(gòu)建一棵線段樹，查詢區(qū)間[2,5]為例。

我們首先從根節(jié)點開始查詢：在區(qū)間[0,7]中查詢[2,5]。

將根節(jié)點的區(qū)間分為左孩子[0,3]和右孩子[4,7]，而我們的查詢的區(qū)間[2,5]，不能其中一個孩子的區(qū)間完全包括。

于是上述問題轉(zhuǎn)化為兩個子問題：

• 在區(qū)間[0,3]中查詢[2,3]；
• 在區(qū)間[4,7]中查詢[4,5]；
• 最后將[2,3]和[4,5]結(jié)果合并，得到區(qū)間[2,5]的結(jié)果。

將[0,3]劃分為左孩子[0,1]和右孩子[2,3]，此時右孩子剛好和查詢的區(qū)間重合，返回結(jié)果。

將[4,7]劃分為左孩子[4,5]和右孩子[6,7]，此時左孩子剛好和查詢的區(qū)間重合，返回結(jié)果。

從上面可以看出，在線段樹的區(qū)間查找過程中，不需要遍歷區(qū)間中的每個元素，只需要在線段樹中找到對應(yīng)的所有子區(qū)間，再將這些子區(qū)間的結(jié)果合并即可。而查詢所經(jīng)過的節(jié)點數(shù)最多是樹的高度，時間復(fù)雜度為O(logn)。

而且上面的過程也是遞歸的過程。

• 遞歸終止條件就是：查詢區(qū)間的邊界和節(jié)點的邊界完全重合，就返回該節(jié)點的統(tǒng)計值。

如果不重合，那怎么辦？

這時應(yīng)該分 3 種情況：

• 如果查詢區(qū)間的左邊界大于中間節(jié)點，那么就查詢右區(qū)間

• 如果查詢區(qū)間的右邊界小于等于中間節(jié)點，那么就查詢左區(qū)間

• 如果不屬于上述兩種情況，那么查詢的區(qū)間就要根據(jù)中間節(jié)點拆分

遞歸函數(shù)的參數(shù)應(yīng)該有 4 個，當(dāng)前節(jié)點所在的區(qū)間的左邊界和右邊界，用戶要查詢的的區(qū)間的左邊界和右邊界。

代碼如下：

//在以 treeIndex 為根的線段樹中 [l,r] 的范圍里，搜索區(qū)間 [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); // 如果左邊界大于中間節(jié)點，則查詢右區(qū)間 if (queryL > mid) return query(rightTreeIndex, mid + 1, r, queryL, queryR); // 如果右邊界小于等于中間節(jié)點，則查詢左區(qū)間 if (queryR <= mid) return query(leftTreeIndex, l, mid, queryL, queryR); // 如果上述兩種情況都不是，則根據(jù)中間節(jié)點，拆分為兩個查詢區(qū)間 E leftResult = query(leftTreeIndex, l, mid, queryL, mid); E rightResult = query(rightTreeIndex, mid + 1, r, mid + 1, queryR); //合并左右區(qū)間的查詢結(jié)果 return merger.merge(leftResult, rightResult);}

線段樹的更新

如下圖所示，更新A[i]=100，那么將需要更新的索引 i和區(qū)間的終點mid，分為兩種情況。

• 如果i>mid，那么索引i落在右區(qū)間，更新右區(qū)間；
• 如果i<=mid，那么索引i落在左區(qū)間，更新左區(qū)間；

那么遞歸的終止條件是什么呢？

• 當(dāng)遞歸到葉子節(jié)點的時候，就值更新這個節(jié)點：葉子節(jié)點就是區(qū)間長度為 1 的節(jié)點。

當(dāng)更新完葉子節(jié)點后，還需要回溯，更新父節(jié)點區(qū)間的統(tǒng)計值。

代碼如下：

//將 index 位置的值，更新為 epublic void update(int index, E e) { if (index < 0 || index >= data.length) throw new IllegalArgumentException("Index is illegal"); data[index] = e; //更新線段樹相應(yīng)的節(jié)點 updateTree(0, 0, data.length - 1, index, e);}// 在以 treeIndex 為根的線段樹中，更新 index 的值為 eprivate 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); //更新當(dāng)前節(jié)點 tree[treeIndex] = merger.merge(tree[leftTreeIndex], tree[rightTreeIndex]);}

完整代碼

public class SegmentTree { private E[] tree; //線段樹 private E[] data; //數(shù)據(jù) private Merger merger;//融合器 public SegmentTree(E[] arr, Merger 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]; } //構(gòu)建線段樹 buildSegmentTree(0, 0, data.length - 1); } // 返回數(shù)組元素個數(shù) public int getSize() { return data.length; } // 根據(jù)索引獲取數(shù)據(jù) public E get(int index) { if (index < 0 || index > data.length) throw new IllegalArgumentException("Index is illegal"); return data[index]; } //根據(jù)一個節(jié)點的索引 index，返回這個節(jié)點的左孩子的索引 private int leftChild(int index) { return 2 * index + 1; } //根據(jù)一個節(jié)點的索引 index，返回這個節(jié)點的右孩子的索引 private int rightChild(int index) { return 2 * index + 2; } // 在 treeIndex 的位置創(chuàng)建表示區(qū)間 [l,r] 的線段樹 private void buildSegmentTree(int treeIndex, int l, int r) { // base case：遞歸到葉子節(jié)點了 if (l == r) { tree[treeIndex] = data[l]; return; } int leftTreeIndex = leftChild(treeIndex); int rightTreeIndex = rightChild(treeIndex); //劃分區(qū)間 int mid = l + (r - l) / 2; // 求(左孩子)左區(qū)間的統(tǒng)計值 buildSegmentTree(leftTreeIndex, l, mid); // 求(右孩子)右區(qū)間的統(tǒng)計值 buildSegmentTree(rightTreeIndex, mid + 1, r); //求當(dāng)前節(jié)點 [左區(qū)間+右區(qū)間] 的統(tǒng)計值 tree[treeIndex] = merger.merge(tree[leftTreeIndex], tree[rightTreeIndex]); } //查詢區(qū)間，返回區(qū)間 [queryL, queryR] 的統(tǒng)計值 public E query(int queryL, int queryR) { //首先進(jìn)行邊界檢查 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] 的范圍里，搜索區(qū)間 [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); // 如果左邊界大于中間節(jié)點，則查詢右區(qū)間 if (queryL > mid) return query(rightTreeIndex, mid + 1, r, queryL, queryR); // 如果右邊界小于等于中間節(jié)點，則查詢左區(qū)間 if (queryR <= mid) return query(leftTreeIndex, l, mid, queryL, queryR); // 如果上述兩種情況都不是，則根據(jù)中間節(jié)點，拆分為兩個查詢區(qū)間 E leftResult = query(leftTreeIndex, l, mid, queryL, mid); E rightResult = query(rightTreeIndex, mid + 1, r, mid + 1, queryR); //合并左右區(qū)間的查詢結(jié)果 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; //更新線段樹相應(yīng)的節(jié)點 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); //更新當(dāng)前節(jié)點 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(); }}

使用例子

定義一個求區(qū)間的最大值的線段樹，代碼如下：

public class Main { public static void main(String[] args) { Integer[] nums = new Integer[]{34, 65, 8, 10, 21, 86, 79, 30}; SegmentTree segTree = new SegmentTree<>(nums, new Merger() { @Override public Integer merge(Integer a, Integer b) { //返回 a 和 b 的最大值 return Math.max(a, b); } }); // 查詢區(qū)間 [2,5] 的最大值 System.out.println(segTree.query(4, 7)); }}

當(dāng)然，你也可以定義一個求區(qū)間內(nèi)元素的和的線段樹，只需要修改merge()方法的實現(xiàn)即可：

public class Main { public static void main(String[] args) { Integer[] nums = new Integer[]{34, 65, 8, 10, 21, 86, 79, 30}; SegmentTree segTree = new SegmentTree<>(nums, new Merger() { @Override public Integer merge(Integer a, Integer b) { //返回 a 和 b 的和 return a + b; } }); // 查詢區(qū)間 [2,5] 的和 System.out.println(segTree.query(4, 7)); }}

LeetCode 上相關(guān)的題目

303. 區(qū)域檢索和-數(shù)組不可變

題目鏈接：303. 區(qū)域和檢索 - 數(shù)組不可變

線段樹求解

這道題是求取區(qū)間和，可以使用線段樹來實現(xiàn)。時間復(fù)雜度為O(logn)，空間復(fù)雜度為O(n)。

class NumArray { private int[] tree; private int[] data; public NumArray(int[] nums) { data = nums; tree = new int[nums.length * 4]; //當(dāng)數(shù)組長度大于 0 時，才創(chuàng)建線段樹 if (nums.length > 0) //創(chuàng)建線段樹 buildSegmentTree(0, 0, nums.length - 1); } //根據(jù)一個節(jié)點的索引 index，返回這個節(jié)點的左孩子的索引 private int leftChild(int index) { return 2 * index + 1; } //根據(jù)一個節(jié)點的索引 index，返回這個節(jié)點的右孩子的索引 private int rightChild(int index) { return 2 * index + 2; } // 在 treeIndex 的位置創(chuàng)建表示區(qū)間 [l,r] 的線段樹 private void buildSegmentTree(int treeIndex, int l, int r) { //遞歸終止條件：區(qū)間長度為 1 if (l == r) { tree[treeIndex] = data[l]; return; } int leftTreeIndex = leftChild(treeIndex); int rightTreeIndex = rightChild(treeIndex); int mid = l + (r - l) / 2; //創(chuàng)建左區(qū)間(左孩子)的和 buildSegmentTree(leftTreeIndex, l, mid); //創(chuàng)建右區(qū)間(右孩子)的和 buildSegmentTree(rightTreeIndex, mid + 1, r); //合并做有區(qū)間的和 tree[treeIndex] = tree[leftTreeIndex] + tree[rightTreeIndex]; } public int sumRange(int i, int j) { //tree.length == 1 表示數(shù)組沒有元素，直接返回 0 if (tree.length == 1) return 0; return queryRange(0, 0, data.length - 1, i, j); } //在以 treeIndex 為根的線段樹中 [l,r] 的范圍里，搜索區(qū)間 [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); // 如果左邊界大于中間節(jié)點，則查詢右區(qū)間 if (queryL > mid) return queryRange(rightTreeIndex, mid + 1, r, queryL, queryR); // 如果右邊界小于等于中間節(jié)點，則查詢左區(qū)間 if (queryR <= mid) return queryRange(leftTreeIndex, l, mid, queryL, queryR); // 如果上述兩種情況都不是，則根據(jù)中間節(jié)點，拆分為兩個查詢區(qū)間 int leftResult = queryRange(leftTreeIndex, l, mid, queryL, mid); int rightResult = queryRange(rightTreeIndex, mid + 1, r, mid + 1, queryR); //合并左右區(qū)間的查詢結(jié)果 return leftResult + rightResult; }}

前綴和求解

其實這道題有更加高效的解法，那就是前綴和。

前綴和的定義是：定義一個前綴和數(shù)組sum，每個元素sum[i]表示的是nums[0...i]區(qū)間中的元素的和。

那么我們要求[i,j]區(qū)間的和，就可以使用sum[j]-sum[i-1]得到。

注意當(dāng)i=0時，i-1=-1會溢出。因此sums數(shù)組應(yīng)該整體向后移動一位。

sum[0]=0表示前面沒有元素，和應(yīng)該是 0。

此時[i,j]區(qū)間的和應(yīng)該是sum[j+1]-sum[i]。

代碼如下：

class NumArray { //前綴和數(shù)組 private int[] sums; public NumArray(int[] nums) { //邊界條件判斷 if (nums == null || nums.length == 0) { sums = new int[]{}; } int n = nums.length; //由于整體后移了一位，長度應(yīng)該為 n+1 sums = new int[n + 1]; //構(gòu)建前綴和 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; //直接返回前綴和相減的結(jié)果 return sums[j + 1] - sums[i]; }}

使用前綴和數(shù)組的空間復(fù)雜度依然是O(n)，但時間復(fù)雜度是O(1)，優(yōu)于線段樹。

那既然這樣，區(qū)間問題為什么還要用線段樹呢？

因為這道題目加了一個限制：數(shù)組不可變，也就是說數(shù)組里的元素是固定的。

如果數(shù)組的內(nèi)容是可變的，那么每次更新索引[i]的數(shù)據(jù)，相應(yīng)的[i...n]區(qū)間的前綴和都需要更新。前綴和數(shù)組更新的時間時間復(fù)雜度是O(n)，而線段樹的更新復(fù)雜度是O(logn)。

因此，在數(shù)組內(nèi)容可變的情況下，線段樹依然是更優(yōu)的選擇。

303. 區(qū)域檢索和-數(shù)組可修改

題目鏈接：307. 區(qū)域和檢索 - 數(shù)組可修改

前綴和求解

根據(jù)上面前綴和的做法，我們只需要添加更新數(shù)據(jù)和對應(yīng)的前綴和的邏輯即可。

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; //由于整體后移了一位，長度應(yīng)該為 n+1 sums = new int[n + 1]; //構(gòu)建前綴和 for (int i = 0; i < n; i++) { sums[i + 1] = sums[i] + nums[i]; } } public void update(int i, int val) { // 更新數(shù)組 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; //直接返回前綴和相減的結(jié)果 return sums[j + 1] - sums[i]; }}

update()方法的時間復(fù)雜度是O(n)，sumRange()方法的時間復(fù)雜度是O(1)。

線段樹求解

同理，這里只需要在上面 303. 區(qū)域和檢索 - 數(shù)組不可變 的線段樹解法上，添加更新的線段樹的邏輯即可。

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：遞歸到葉子節(jié)點了 if (l == r) { tree[treeIndex] = data[l]; return; } //劃分區(qū)間 int mid = l + (r - l) / 2; int leftTreeIndex = leftChild(treeIndex); int rightTreeIndex = rightChild(treeIndex); // 求(左孩子)左區(qū)間的統(tǒng)計值 buildSegmentTree(leftTreeIndex, l, mid); // 求(右孩子)右區(qū)間的統(tǒng)計值 buildSegmentTree(rightTreeIndex, mid + 1, r); //求當(dāng)前節(jié)點 [左區(qū)間+右區(qū)間] 的統(tǒng)計值 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) { // 更新數(shù)組 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); //更新當(dāng)前節(jié)點 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()方法的時間復(fù)雜度都是O(n)。

總結(jié)與擴(kuò)展

線段樹，雖然不是滿二叉樹。但是我們卻可以把它看作一棵滿二叉樹，進(jìn)而使用數(shù)組來存儲這棵樹。

其次，在線段樹中，我們定義了每個節(jié)點，存儲的數(shù)據(jù)是這個節(jié)點對應(yīng)區(qū)間的統(tǒng)計值(最大值、最小值、區(qū)間和)。通過這一點，你可以體會到，對于樹中的節(jié)點，你可以賦予它獨特的定義，進(jìn)而可以高效地解決各種各樣的問題。因此，樹的使用范圍是非常廣泛的。

對于，線段樹的構(gòu)建、更新區(qū)間、和查詢區(qū)間，這 3 個操作，都是先遞歸訪問葉子節(jié)點，然后再回溯訪問父節(jié)點，合并左右孩子區(qū)間的結(jié)果，這本質(zhì)上是一種后序遍歷的思想。

對一個區(qū)間進(jìn)行更新

在本文的例子中，每次更新都是對一個元素進(jìn)行更新。現(xiàn)在考慮另一種更新：對某個區(qū)間內(nèi)的所有元素進(jìn)行更新。

比如：將[2,5]區(qū)間中的所有元素都加 3，就需要遍歷這個區(qū)間中的每個元素，區(qū)間更新的時間復(fù)雜度就變?yōu)榱薕(n)。為了降低區(qū)間更新的復(fù)雜度，有一種專門的方法：懶惰更新。

懶惰更新的思想是：在每次更新區(qū)間時，我們實際上先不更新實際的數(shù)據(jù)，而是使用另一個lazy數(shù)組，來標(biāo)記這些未更新的內(nèi)容。

那么什么時候才會更新這些節(jié)點呢？

當(dāng)我們下一次更新或者查詢到這些數(shù)據(jù)時，先查一下lazy數(shù)組中是否有數(shù)據(jù)未更新，然后將未更新的內(nèi)容進(jìn)行更新，再訪問對應(yīng)的數(shù)據(jù)。

例如：

• 第一次：將[2,5]區(qū)間中的所有元素都加 3，實際上lazy數(shù)組就會標(biāo)記[2,5]區(qū)間的數(shù)據(jù)未更新；
• 第二次：將[4,7]區(qū)間中的所有元素都減 5。這時，查詢lazy數(shù)組中，發(fā)現(xiàn)[4,5]區(qū)間的數(shù)據(jù)未更新，那么先更新[4,5]區(qū)間的內(nèi)容，[2,3]區(qū)間的標(biāo)記不變。然后標(biāo)記[4,7]區(qū)間中的內(nèi)容未更新。

通過懶惰更新，時間復(fù)雜度降為了O(logn)。

二維線段樹

在這篇文章中，我們處理的都是一維的線段樹，實際中還可以產(chǎn)生二位線段樹。

一維線段樹，就是數(shù)據(jù)都是一維數(shù)組，每個節(jié)點記錄的區(qū)間只有左右兩個邊界。

在二維線段樹中，數(shù)據(jù)是二維數(shù)組，也就是一個矩陣，每個節(jié)點記錄的區(qū)間有上下左右兩個邊界。那么每個節(jié)點就有 4 個孩子。

進(jìn)一步擴(kuò)展，你也可以設(shè)計出 3 維的線段樹，甚至更高維的線段樹。

線段樹是一種設(shè)計思想，利用樹這種數(shù)據(jù)結(jié)構(gòu)，如何把一個大的數(shù)據(jù)單元，遞歸地拆分為小的數(shù)據(jù)單元，同時，利用樹這種數(shù)據(jù)結(jié)構(gòu)，可以高效地進(jìn)行查詢、更新等操作。

動態(tài)線段樹

在這篇文章中，我使用了數(shù)組這種數(shù)據(jù)結(jié)構(gòu)來存儲樹，造成了空間的浪費。實際上，我們可以也使用鏈?zhǔn)酱鎯?#xff0c;可以更好地利用空間。

實際上，動態(tài)線段樹有一個更加重要的應(yīng)用，。例如，我們要存儲 10000000 大小的線段樹，但是不會對這么大一個區(qū)間中的每一個部分都進(jìn)行訪問，可能只會對一種某個小部分進(jìn)行訪問。

那么我們可以不用一開始就創(chuàng)建這么巨大的線段樹，而是只創(chuàng)建一個根節(jié)點，等到實際訪問某個區(qū)間時，在根據(jù)區(qū)間的邊界，動態(tài)地創(chuàng)建線段樹。

樹狀數(shù)組

這篇文章講的線段樹，實際上是對區(qū)間操作的一種數(shù)據(jù)結(jié)構(gòu)。與區(qū)間操作相關(guān)的數(shù)據(jù)結(jié)構(gòu)，還有另外一個：樹狀數(shù)組，英文名為Binary Index Tree。感興趣可以自行查閱。

總結(jié)

以上是生活随笔為你收集整理的如何在vs中创建r树索引代码_线段树详解与实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。