执行范围最小查询

执行 RMQ 的过程已在介绍中显示。用于检查范围最小查询的伪代码将是：

Procedure RangeMinimumQuery(SegmentTree, qLow, qHigh, low, high, position):
if qLow <= low and qHigh >= high        //Total Overlap
    Return SegmentTree[position]
else if qLow > high || qHigh < low      //No Overlap
    Return infinity
else                                    //Partial Overlap
    mid := (low+high)/2
    Return min(RangeMinimumQuery(SegmentTree, qLow, qHigh, low, mid, 2*position+1),
               RangeMinimumQuery(SegmentTree, qLow, qHigh, mid+1, high, 2*position+2))
end if

在这里，qLow = The lower range of our query，qHigh = The upper range of our query。low = starting index of Item array，high = Finishing index of Item array，position = root = 0。现在让我们尝试使用我们之前创建的示例来理解该过程：

我们的 SegmentTree 数组：

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

我们希望找到范围内的最小值 [1,3] 。
由于这是一个递归过程，我们将看到 RangeMinimumQuery 的操作使用递归表来跟踪 qLow，qHigh，low，high，position，mid 和 calling line。首先，我们调用 RangeMinimumQuery（SegmentTree，1,3,0,3,0 。这里，前两个条件不满足（部分重叠）。我们将得到一个 mid.calling line 表示在此声明后调用了 RangeMinimumQuery 我们将程序中的 RangeMinimumQuery 调用分别表示为 1 和 **2。**我们的表格如下所示：

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

所以当我们调用 RangeMinimumQuery-1 时，我们通过：low = 0，high = mid = 1，position = 2*position+1 = 1。有一件事你可以注意到，那就是 2*position+1 是节点的左子节点。这意味着我们正在检查 root 的左子。由于 [1,3] 部分重叠 [0,1] ，前两个条件不满足，我们得到一个 mid。我们的表：

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

在下一个递归调用中，我们通过 low = 0，high = mid = 0，position = 2*position+1 = 3。我们到达树的最左边的叶子。由于 [1,3] 不与 [0,0] 重叠，我们将 infinity 返回给我们的调用函数。递归表：

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

由于此递归调用已完成，我们将返回到递归表的上一行。我们得到：

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

在我们的程序中，我们执行 RangeMinimumQuery-2 调用。这一次，我们通过 low = mid+1 = 1，high = 1 和 position = 2*position+2 = 4。我们的 calling line changes to **2**。我们得到：

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

所以我们要去上一个节点的正确孩子。这次总重叠。我们返回值 SegmentTree[position] = SegmentTree[4] = 2。

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

回到调用函数，我们检查两个调用函数的两个返回值的最小值。显然最小值为 2 ，我们将 2 返回给调用函数。我们的递归表看起来像：

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

我们已经完成了查看分段树的左侧部分。现在我们从这里调用 RangeMinimumQuery-2。我们将通过 low = mid+1 = 1+1 =2，high = 3 和 position = 2*position+2 = 2。我们的表：

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

总重叠。所以我们返回值：SegmentTree[position] = SegmentTree[2] = 0。我们回到调用这两个子节点的递归，得到最小值 （4,0） ，即 0 并返回值。

执行该过程后，我们得到 0 ，这是从 index- 1 到 index- 3 的最小值。

此过程的运行时复杂性为 O(logn)，其中 n 是 Items 数组中的元素数。要执行范围最大查询，我们需要替换该行：

Return min(RangeMinimumQuery(SegmentTree, qLow, qHigh, low, mid, 2*position+1),
               RangeMinimumQuery(SegmentTree, qLow, qHigh, mid+1, high, 2*position+2))

有：

Return max(RangeMinimumQuery(SegmentTree, qLow, qHigh, low, mid, 2*position+1),
               RangeMinimumQuery(SegmentTree, qLow, qHigh, mid+1, high, 2*position+2))