Range Minimum Query in Segment Tree using C++

In this tute, we will discuss the Range Minimum Query in Segment Tree using C++. Before heading into the tute, make sure that you’ve understood the sum of range in the segment tree well enough. Range Minimum Query (RMQ) is one of the applications of Segment Tree.

 

In a nutshell, if you are given an array ar[0..n-1]. To find the least element of a given range [strt..end] in the array, what would you do?

A simple approach is to run through all elements in [strt..end] to find the minimum in O(n) time complexity.

Another approach is to create a 2D matrix/array in which min[x][y] would give the least element in the range [x.y]. The query takes O(1) time complexity. However, creating the matrix requires n2 iterations. Hence, this results in O(n2) time complexity. Note that here we can’t use prefix or suffix arrays as we did in the previous posts on sum and xor of range in segment tree.

An efficient approach is to use a Segment tree. This reduces the query time to O(Log2n). Since this is a variation of the Sum Segment tree, we are going to use the query approach similar to the sum of range using segment trees. But, the difference here is that each intermediate node stores the minimum of its two children.

Range Minimum Query in Segment Tree:

For the RMQs, you’ll have to find the least element in the range strt & end in the array. The following algorithm is used to answer the RMQ.

  1. Firstly, start at the root node.
  2. If the current node’s range is entirely within the desired range, return this value.
  3. Else, continue with the child/children containing some elements of the desired range.
  4. Continue this till all the desired range of elements are accessed.
  5. While tracing back to the root, take minimum for all the returned values at each level. The value returned by the root is the least element of the given range.

Implementation:

// C++ program to show Segment Tree - Range Minimum Query (RMQ)
#include<bits/stdc++.h>
using namespace std;

#define MAX 100010
int tree[MAX];
vector<int> ar;

/* Function to display elements of the Segment Tree
   level by level. */
void showSegTree(int n)
{
  int i, j, h = ceil(log2(n));
  for(i=0 ; i<=h ; ++i)
  {
    for(j=0 ; j<pow(2, i) ; ++j)
      cout<<tree[int(pow(2, i)-1 + j)]<<' ';
    cout<<endl;
  }
}

/* Function to construct the Segment Tree recursively.
   At each node, if it is not the leaf, two children are
   processed further. Otherwise, the leaf is assigned an
   array alement. strt and end are range in the array,
   idx is the index used in the segment tree */
int constSegTree(int strt, int end, int idx)
{
  // Saves tree[idx] = ar[strt] and then returns tree[idx]
  if(strt == end)
    return tree[idx] = ar[strt];

  int mid = (strt + end) / 2;
  return tree[idx] = min(constSegTree(strt, mid, 2*idx+1),
              constSegTree(mid+1, end, 2*idx+2));
}
void constSegTree(int n)
{
  constSegTree(0, n-1, 0);
}

/* Function to get the minimum of elements of array in the
   range [strt..end]. l & r are the range of current node.
   indx is the index of node in segment tree */
int RMQ(int strt, int end, int l, int r, int idx)
{
  if(strt <= l && r <= end)
    return tree[idx];
  
  if(end < l || r < strt || l > r)
    return INT_MAX;		// To avoid undesired values
  
  int mid = (l + r) / 2;
  return min(RMQ(strt, end, l, mid, 2*idx+1),
        RMQ(strt, end, mid+1, r, 2*idx+2));
}
int RMQ(int n, int strt, int end)
{
  return RMQ(strt, end, 0, n-1, 0);
}

int main()
{
  int n = 7;
  ar = {18, 17, 1, 19, 15, 11, 20};

  constSegTree(n);

  cout<<"n = 7, ar = {18, 17, 1, 19, 15, 11, 20}"<<endl;
  showSegTree(n);

  cout<<"\nMinimum of ar[1..4] = "<<RMQ(n, 1, 4)<<endl;

    return 0;
}

Output:

n = 7, ar = {18, 17, 1, 19, 15, 11, 20}
1 
1 11 
17 1 11 20 
18 17 1 19 15 11 0 0 

Minimum of ar[1..4] = 1

Bonus: Still find it difficult to understand the implementation? Remove all comments in the code and start tracing for your inputs.

Also, read:

Leave a Reply

Your email address will not be published. Required fields are marked *