段樹簡介

假設我們有一個陣列：

+-------+-----+-----+-----+-----+-----+-----+
| `Index` |  0  |  1  |  2  |  3  |  4  |  5  |
+-------+-----+-----+-----+-----+-----+-----+
| `Value` |  -1 |  3  |  4  |  0  |  2  |  1  |
+-------+-----+-----+-----+-----+-----+-----+

我們想對這個陣列執行一些查詢。例如：

• index- 2 到 index- 4 的最小值是多少？ - > 0
• index- 0 到 index- 3 的最大值是多少？ - > 4
• 從 index- 1 到 index- 5 的總和是多少？ - > 10

我們怎麼找到它？

蠻力：
我們可以遍歷陣列從起始索引到完成索引並回答我們的查詢。在這種方法中，每個查詢都需要 O(n) 時間，其中 n 是起始索引和結束索引之間的差異。但是，如果有數百萬的數字和數百萬的查詢呢？對於 m 個查詢，需要時間。因此，對於我們陣列中的 10⁵值，如果我們進行 10⁵查詢，對於最壞情況，我們需要遍歷 10 個專案。

動態程式設計：
我們可以建立一個 6X6 矩陣來儲存不同範圍的值。對於範圍最小查詢（RMQ），我們的陣列看起來像：

              0     1     2     3     4     5
     +-----+-----+-----+-----+-----+-----+-----+
     |     |  -1 |  3  |  4  |  0  |  2  |  1  |
     +-----+-----+-----+-----+-----+-----+-----+
  0  |  -1 |  -1 |  -1 |  -1 |  -1 |  -1 |  -1 |
     +-----+-----+-----+-----+-----+-----+-----+
  1  |  3  |     |  3  |  3  |  0  |  0  |  0  |
     +-----+-----+-----+-----+-----+-----+-----+
  2  |  4  |     |     |  4  |  0  |  0  |  0  |
     +-----+-----+-----+-----+-----+-----+-----+
  3  |  0  |     |     |     |  0  |  0  |  0  |
     +-----+-----+-----+-----+-----+-----+-----+
  4  |  2  |     |     |     |     |  2  |  1  |
     +-----+-----+-----+-----+-----+-----+-----+
  5  |  1  |     |     |     |     |     |  1  |
     +-----+-----+-----+-----+-----+-----+-----+

一旦我們有了這個矩陣構建，就足以回答所有的 RMQ。這裡， Matrix [i] [j] 將索引 -i 的最小值儲存到 index- j 。例如：從 index- 2 到 index- 4 的最小值是 Matrix [2] [4] = 0 。這個矩陣在 O(1) 時間內回答查詢，但是需要 O（n²） 時間來構建這個矩陣和 O(n²) 空間來儲存它。因此，如果 n 是一個非常大的數字，那麼它的擴充套件性不是很好。

段樹：
一個線段樹是用於儲存間隔，或段樹資料結構。它允許查詢哪些儲存的段包含給定的點。構建一個分段樹需要花費時間，它需要 O(n) 空間來維護它，並且它會在時間上回答一個查詢。

段樹是二叉樹，給定陣列的元素將是該樹的葉子。我們將通過將陣列分成兩半來建立分段樹，直到我們到達單個元素。所以我們的部門會為我們提供：

現在，如果我們用葉子的最小值替換非葉子節點，我們得到：

所以這是我們的分段樹。我們可以注意到，根節點包含整個陣列的最小值（範圍[0,5]），其左子節點包含左陣列的最小值（範圍[0,2]），右子節點包含最小值我們的右陣列的值（範圍[3,5]）等等。葉節點包含每個單獨點的最小值。我們得到：

現在讓我們在這棵樹上做一個範圍查詢。要進行範圍查詢，我們需要檢查三個條件：

• 部分重疊：我們檢查兩個葉子。
• 總重疊：我們返回儲存在節點中的值。
• 沒有重疊：我們返回一個非常大的值或無窮大。

假設我們想檢查範圍 [2,4] ，這意味著我們想要找到從索引 2 到 4 的最小值。我們將從根開始，檢查節點中的範圍是否與查詢範圍重疊。這裡，

• [2,4] 不完全重疊 [0,5] 。所以我們會檢查兩個方向。
  • 在左子樹， [2,4] 部分重疊 [0,2] 。我們會檢查兩個方向。
    • 在左子樹， [2,4] 不重疊 [0,1] ，所以這不會有助於我們的答案。我們迴歸無限。
    • 在右子樹， [2,4] 完全重疊 [2,2] 。我們返回 4 。
      這兩個返回值（4，無窮大）中的最小值為 4 。我們從這部分得到 4 分。
  • 在右子樹， [2,4] 部分重疊。所以我們會檢查兩個方向。
    • 在左子樹， [2,4] 完全重疊 [3,4] 。我們返回 0 。
    • 在右子樹， [2,4] 不重疊 [5,5] 。我們迴歸無限。
      這兩個返回值（0，無窮大）中的最小值為 0 。我們從這部分得到 0 。
• 返回值(4,0)的最小值為 0 。這是我們期望的最小範圍 [2,4] 。

現在我們可以檢查一下，無論我們的查詢是什麼，最多需要 4 個步驟才能從這個分段樹中找到所需的值。

使用：

• 範圍最小查詢
• 最低的共同祖先
• 懶惰的傳播
• 動態子樹總和
• 忽視和最小
• 雙場
• 找到第 k 個最小元素
• 查詢無序對的數量