使用数组实现段树

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])