Range Minimum Query

For each query iterate all the elements in the range [L, R] and return the minimum element.

The steps are as follows :

1. Declare ‘ans’ array to store the minimum element of each query.
2. Process each query one at a time, for each query initialize a variable ‘minElement’ equal to INT_MAX, now simply iterate the range [L, R] using a FOR loop and store the minimum element of this range in ‘minElement’. Insert the ‘minElement’ in ‘ans’.
3. Finally, return ‘ans’ array.

This is a standard question on the segment tree. In general, many questions involving range query can be solved using a segment tree, segment tree reduces the linear search time into logarithmic time for each query, though there is an initial preprocessing cost that is linear in time. Rather than directly jumping to the implementation of a segment tree, we will give an overview of this data structure.

Suppose you have an array = {1, 2, 1, 3, 4, 2, 5, 3, 6, 5, 4, 8, 6}, and we have to do multiple queries on this array, let one the query’s for the time being be to find the minimum in the range [3, 12].

Refer to the image above, we add some extra elements at the end of the array, such that these elements do not alter our answer, simply choosing elements equal to infinity works here as we need to find the minimum element in a range and an infinite number won’t alter our result. We add these elements to the end so that the tree that we build in future is a full binary tree, hence we need to add elements until the total elements in the array are equal to 2^x - 1 (x is any natural number).

We will now start building a segment tree (a full binary tree in our case), we can easily store this tree as an array (recall that we don’t need adjacency list, etc. to store a complete/ full binary tree, an array is just sufficient to do it). Fill all the leaf nodes of this tree with the array elements, now simply fill the rest of the elements of this segment tree, to do this refer to the things in Yellow in the image above, we can easily fill the i^th position with the minimum of the values at 2*i’th and 2*i + 1’th positions. This will finally help us, as now we need not have to search each element in a range, we are precomputing things and we can directly use that later, for example: if a query has the range [4, 7] inside it, then we will not need to check for each of the element from Arr[4] to Arr[7], we can simply consider the value Seg[2] as it stores the minimum of that range.

Now let’s discuss how to process a query, for the given array if we have a query to find the minimum from the range [3, 12] for the above array, then instead of finding the minimum of each element in this range, we can simply find the minimum of Seg[3], Seg[5] and Seg[19] (marked with green circles in the image), this is because Seg[3] stores the minimum element for the range [8, 12], Seg[5] stores the minimum element for the range [4, 7] and Seg[19] stores the element equal to Arr[3], this clearly shows that by just considering three elements of our segment tree we are able to find the minimum element of the range [3, 12]. You can easily notice that as the range increases, the number of lookups required will be much less than the linear time complexity of the brute force method.

There is a standard procedure to implement segment trees, to process the query we start from the root node of the tree (1’st node of the segment tree), and then recursively call both the children. We return the recursive call if a segment covered by the current node completely lies in our query range.

The steps are as follows :

1. Run a while loop, and insert INT_MAX in ‘Arr’ till the size of the array is not equal to 2^x - 1 (where X is some natural number), Inside while loop, keep incrementing the value of ‘N’ so that it stores the updated size of the ‘Arr’.
2. Now, declare an array ‘segTree’ of size equal to 2*N, indices from 0 to 2*N - 1 will store the elements of the segment tree. Fill the array elements in the last ‘N’ indices of the ‘segTree’, to fill the first ‘N’ values, simply run a for loop for a variable ‘i’ from N - 1 to 1, and update the value of segTree[i] equal to min(segTree[2*i], segTree[2*i+1]).
3. Initialize an array ‘ans’ to store the answer to each query.
4. Now process each query one at a time.
   • For each query make an initial call to recursive function ‘minQuery’, pass the ‘curNode’ equal to 1 (root node), ‘rangeL’ equal to 0, ‘rangeH’ equal to N - 1, ‘queryL’ equal to ‘L’ and ‘queryR’ equal to ‘R’. Here ‘rangeL’ and  ‘rangeH’ signify the index range of the original array that is covered by the ‘curNode’ of the segment tree.
   • In the recursive function check if the current range [rangeL, rangeH] lies completely inside [queryL, queryR], if so then return the value stored in the ‘curNode’ of the segment tree. If in case [rangeL, rangeH] lies completely outside [queryL, queryH] then return INT_MAX.
   • If in case, [rangeL, rangeH] lies partially inside [queryL, queryR], then initialize the value of ‘mid’ equal to ( rangeL + rangeH ) / 2 and make recursive calls to the child nodes of ‘curNode’, for the left-child 2*curNode pass the new range as [rangeL, mid] and for the right-child 2*curNode + 1, pass the new range as [mid+1, rangeH]. Return the minimum of the value calculated from the recursive calls made to both the child node.
5. For each query store the minimum value calculated in the ‘ans’ array.
6. Finally, return ‘ans’ array.