data-structures Segment Tree Performing a Range Minimum Query
Example
The procedure to perform a RMQ is already shown in introduction. The pseudo-code for checking Range Minimum Query will be:
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
Here, 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. Now let's try to understand the procedure using the example we created before:
Our SegmentTree array:
0 1 2 3 4 5 6
+-----+-----+-----+-----+-----+-----+-----+
| -1 | -1 | 0 | -1 | 2 | 4 | 0 |
+-----+-----+-----+-----+-----+-----+-----+
We want to find the minimum in range [1,3].
Since this is a recursive procedure, we'll see the operation of the RangeMinimumQuery using a recursion table that keeps track of qLow, qHigh, low, high, position, mid and calling line. At first, we call RangeMinimumQuery(SegmentTree, 1, 3, 0, 3, 0. Here, the first two conditions are not met(partial overlap). We'll get a mid. The calling line indicates which RangeMinimumQuery is called after this statement. We denote the RangeMinimumQuery calls inside the procedure as 1 and 2 respectively. Our table will look like:
+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 3 | 0 | 1 | 1 |
+------+-------+-----+------+----------+-----+--------------+
So when we call RangeMinimumQuery-1, we pass: low = 0, high = mid = 1, position = 2*position+1 = 1. One thing you can notice, that is 2*position+1 is the left child of a node. That means we're checking the left child of root. Since [1,3] partially overlaps [0,1], the first two conditions are not met, we get a mid. Our table:
+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 3 | 0 | 1 | 1 |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 1 | 1 | 0 | 1 |
+------+-------+-----+------+----------+-----+--------------+
In the next recursive call, we pass low = 0, high = mid = 0, position = 2*position+1 = 3. We reach the leftmost leaf of our tree. Since [1,3] doesn't overlap with [0,0], we return infinity to our calling function. Recursion table:
+------+-------+-----+------+----------+-----+--------------+
| 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 | | |
+------+-------+-----+------+----------+-----+--------------+
Since this recursive call is complete, we go back to the previous row of our recursion table. We get:
+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 3 | 0 | 1 | 1 |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 1 | 1 | 0 | 1 |
+------+-------+-----+------+----------+-----+--------------+
In our procedure, we execute RangeMinimumQuery-2 call. This time, we pass low = mid+1 = 1, high = 1 and position = 2*position+2 = 4. Our calling line changes to **2**. We get:
+------+-------+-----+------+----------+-----+--------------+
| 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 | | |
+------+-------+-----+------+----------+-----+--------------+
So we are going to the right child of previous node. This time there is a total overlap. We return the value SegmentTree[position] = SegmentTree[4] = 2.
+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 3 | 0 | 1 | 1 |
+------+-------+-----+------+----------+-----+--------------+
Back at the calling function, we are checking what is the minimum of the two returned values of two calling functions. Obviously the minimum is 2, we return 2 to the calling function. Our recursion table looks like:
+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 3 | 0 | 1 | 1 |
+------+-------+-----+------+----------+-----+--------------+
We're done looking at the left portion of our segment tree. Now we'll call RangeMinimumQuery-2 from here. We'll pass low = mid+1 = 1+1 =2, high = 3 and position = 2*position+2 = 2. Our table:
+------+-------+-----+------+----------+-----+--------------+
| qLow | qHigh | low | high | position | mid | calling line |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 0 | 3 | 0 | 1 | 1 |
+------+-------+-----+------+----------+-----+--------------+
| 1 | 3 | 2 | 3 | 2 | | |
+------+-------+-----+------+----------+-----+--------------+
There is a total overlap. So we return the value: SegmentTree[position] = SegmentTree[2] = 0. We come back to the recursion from where these two children were called and get the minimum of (4,0), that is 0 and return the value.
After executing the procedure, we get 0, which is the minimum from index-1 to index-3.
The runtime complexity for this procedure is O(logn) where n is the number of elements in the Items array. To perform a Range Maximum Query, we need to replace the line:
Return min(RangeMinimumQuery(SegmentTree, qLow, qHigh, low, mid, 2*position+1),
RangeMinimumQuery(SegmentTree, qLow, qHigh, mid+1, high, 2*position+2))
with:
Return max(RangeMinimumQuery(SegmentTree, qLow, qHigh, low, mid, 2*position+1),
RangeMinimumQuery(SegmentTree, qLow, qHigh, mid+1, high, 2*position+2))
