使用陣列實現段樹

Created: November-22, 2018

比方說，我們有一個陣列：Item = {-1, 0, 3, 6}。我們想構造 SegmentTree 陣列以找出給定範圍內的最小值。我們的細分樹將如下所示：

StackOverflow 文件

節點下面的數字顯示了我們將儲存在 SegmentTree 陣列中的每個值的索引。我們可以看到，要儲存 4 個元素，我們需要一個大小為 7 的陣列。該值由以下公式確定：

Procedure DetermineArraySize(Item):
multiplier := 1
n := Item.size
while multiplier < n
    multiplier := multiplier * 2
end while
size := (2 * multiplier) - 1
Return size

因此，如果我們有一個長度為 5 的陣列，我們的 SegmentTree 陣列的大小將為：（ 8 * 2 ） - 1 = 15 。現在，要確定節點的左右子節點的位置，如果節點在索引 i 中，則其位置為：

左孩子用：（2 * i） + 1 表示。
右孩子用：（2 * i） + 2 表示。

並且索引 i 中任何節點的父節點的索引可以由下式確定：（i - 1） / 2 。 **** **** **** ****

所以代表我們的例子的 SegmentTree 陣列看起來像：

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

讓我們看一下構造這個陣列的虛擬碼：

Procedure ConstructTree(Item, SegmentTree, low, high, position):
if low is equal to high
    SegmentTree[position] := Item[low]
else
    mid := (low+high)/2
    constructTree(Item, SegmentTree, low, mid, 2*position+1)
    constructTree(Item, SegmentTree, mid+1, high, 2*position+2)
    SegmentTree[position] := min(SegmentTree[2*position+1], SegmentTree[2*position+2])
end if

首先，我們輸入值並使用 infinity 初始化 SegmentTree 陣列，使用 Item 陣列的長度作為其大小。我們使用以下方法呼叫該過程：

low = Item 陣列的起始索引。
high = Item 陣列的完成索引。
position = 0，表示我們的 Segment Tree 的根。

現在，讓我們嘗試使用一個示例來理解該過程： StackOverflow 文件

Item 陣列的大小為 4 。我們建立一個長度為（4 * 2） - 1 = 7 的陣列，並用 infinity 初始化它們。你可以使用非常大的值。我們的陣列看起來像：

   0     1     2     3     4     5     6
+-----+-----+-----+-----+-----+-----+-----+
| `inf` | inf | inf | inf | inf | inf | inf |
+-----+-----+-----+-----+-----+-----+-----+

由於這是一個遞迴過程，我們將看到 ConstructTree 的操作使用一個遞迴表，在每次呼叫時跟蹤 low，high，position，mid 和 calling line。首先，我們呼叫 ConstructTree(Item, SegmentTree, 0,3,0) 。在這裡，low 與 high 不同，我們將獲得一個 mid。calling line 表示在此宣告之後呼叫哪個 ConstructTree。我們將過程中的 ConstructTree 呼叫分別表示為 1 和 2 。我們的表格如下：

+-----+------+----------+-----+--------------+
| `low` | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
|  0  |   3  |     0    |  1  |       1      |
+-----+------+----------+-----+--------------+

所以當我們呼叫 ConstructTree-1 時，我們通過：low = 0，high = mid = 1，position = 2*position+1 = 2*0+1 = 1。有一件事你可以注意到，那就是 2*position+1 是 root 的左子，是 1 。由於 low 不等於 high，我們得到了一個 mid。我們的表格如下：

+-----+------+----------+-----+--------------+
| `low` | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
|  0  |   3  |     0    |  1  |       1      |
+-----+------+----------+-----+--------------+
|  0  |   1  |     1    |  0  |       1      |
+-----+------+----------+-----+--------------+

在下一個遞迴呼叫中，我們通過 low = 0，high = mid = 0，position = 2*position+1 = 2*1+1=3。同樣，索引 1 的左子節點是 3 。在這裡，low 是 ehigh，所以我們設定 SegmentTree[position] = SegmentTree[3] = Item[low] = Item[0] = -1。我們的 SegmentTree 陣列將如下所示：

   0     1     2     3     4     5     6
+-----+-----+-----+-----+-----+-----+-----+
| `inf` | inf | inf |  -1 | inf | inf | inf |
+-----+-----+-----+-----+-----+-----+-----+

我們的遞迴表將如下所示：

+-----+------+----------+-----+--------------+
| `low` | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
|  0  |   3  |     0    |  1  |       1      |
+-----+------+----------+-----+--------------+
|  0  |   1  |     1    |  0  |       1      |
+-----+------+----------+-----+--------------+
|  0  |   0  |     3    |     |              |
+-----+------+----------+-----+--------------+

所以你可以看到， -1 已經找到了正確的位置。由於此遞迴呼叫已完成，我們將返回到遞迴表的上一行。桌子：

+-----+------+----------+-----+--------------+
| `low` | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
|  0  |   3  |     0    |  1  |       1      |
+-----+------+----------+-----+--------------+
|  0  |   1  |     1    |  0  |       1      |
+-----+------+----------+-----+--------------+

在我們的程式中，我們執行 ConstructTree-2 呼叫。這一次，我們通過 low = mid+1 = 1，high = 1，position = 2*position+2 = 2*1+2 = 4。我們的 calling line 變為 2 。我們得到：

+-----+------+----------+-----+--------------+
| `low` | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
|  0  |   3  |     0    |  1  |       1      |
+-----+------+----------+-----+--------------+
|  0  |   1  |     1    |  0  |       2      |
+-----+------+----------+-----+--------------+

由於 low 等於 high，我們設定：SegmentTree[position] = SegmentTree[4] = Item[low] = Item[1] = 2。我們的 SegmentTree 陣列：

   0     1     2     3     4     5     6
+-----+-----+-----+-----+-----+-----+-----+
| `inf` | inf | inf |  -1 |  2  | inf | inf |
+-----+-----+-----+-----+-----+-----+-----+

我們的遞迴表：

+-----+------+----------+-----+--------------+
| `low` | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
|  0  |   3  |     0    |  1  |       1      |
+-----+------+----------+-----+--------------+
|  0  |   1  |     1    |  0  |       2      |
+-----+------+----------+-----+--------------+
|  1  |   1  |     4    |     |              |
+-----+------+----------+-----+--------------+

再次你可以看到， 2 已經找到了正確的位置。在這個遞迴呼叫之後，我們返回到遞迴表的前一行。我們得到：

+-----+------+----------+-----+--------------+
| `low` | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
|  0  |   3  |     0    |  1  |       1      |
+-----+------+----------+-----+--------------+
|  0  |   1  |     1    |  0  |       2      |
+-----+------+----------+-----+--------------+

我們執行程式的最後一行，SegmentTree[position] = SegmentTree[1] = min(SegmentTree[2*position+1], SegmentTree[2*position+2]) = min(SegmentTree[3], SegmentTree[4]) = min(-1,2) = -1。我們的 SegmentTree 陣列：

   0     1     2     3     4     5     6
+-----+-----+-----+-----+-----+-----+-----+
| `inf` |  -1 | inf |  -1 |  2  | inf | inf |
+-----+-----+-----+-----+-----+-----+-----+

由於此遞迴呼叫已完成，我們將返回到遞迴表的上一行並呼叫 ConstructTree-2：

+-----+------+----------+-----+--------------+
| `low` | high | position | mid | calling line |
+-----+------+----------+-----+--------------+
|  0  |   3  |     0    |  1  |       2      |
+-----+------+----------+-----+--------------+

我們可以看到我們的分段樹的左側部分是完整的。如果我們以這種方式繼續，在完成整個過程後，我們將最終得到一個完整的 SegmentTree 陣列，它看起來像：

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

構造此 SegmentTree 陣列的時間和空間複雜度為：O(n)，其中 n 表示 Item 陣列中的元素數。我們構造的 SegmentTree 陣列可用於執行範圍最小查詢（RMQ） 。要構造一個陣列來執行範圍最大查詢，我們需要替換該行：

SegmentTree[position] := min(SegmentTree[2*position+1], SegmentTree[2*position+2])

有：

SegmentTree[position] := max(SegmentTree[2*position+1], SegmentTree[2*position+2])