執行範圍最小查詢

執行 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))