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.

 

Here I am going to show you another example:

Example:

arr[] = {3, 9, 8, 10, 7, 4, 6, 5}
range[1,4] = 3
range[4,7] = 4

3 is the minimum number in the range[1,4] and similarly,
4 is minimum in the range[4,7]

We have to find the minimum number in the range[lb,ul].

 

C++ program to find the minimum number in the given range from an Array

 

BRUTE FORCE

Approach:

  1. Initialize minimum=INT_MAX
  2. Iterate from ‘lb’ to ‘ub’ :
    Update minimum if the element at the current position is less than minimum
  3. Return minimum

Code:

#include <bits/stdc++.h>
using namespace std;

//Function to find minimum in a range[lb,ub]
int minRangeQuery(vector<int> a, int lb, int ub)
{
    int minimum = INT_MAX;

    //iteratin from lb to ub to find the minimum
    for (int i = lb; i <= ub; i++)
        minimum = min(minimum, a[i]);
    return minimum;
}

//Function to input lb & ub and display respective output
void inputRange(vector<int> a, int q)
{
    while (q--)
    {
        int lb, ub;
        cout << "\nEnter lower-bound and upper-bound: ";
        cin >> lb >> ub;

        if (lb < 1 || ub > a.size() || lb > ub)
            cout << "Invalid entry";
        else
        {
            cout << "Minimum in the range[" << lb << "," << ub << "]: ";
            cout << minRangeQuery(a, lb - 1, ub - 1);
        }
    }
}

int main()
{
    int n;
    cout << "Enter the size of array: ";
    cin >> n;

    vector<int> a;
    cout << "\nEnter array elements: ";
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        a.emplace_back(x);
    }

    int q;
    cout << "\nEnter no. of queries: ";
    cin >> q;

    inputRange(a, q);
    return 0;
}

Input/Output:

Enter the size of the array: 8

Enter array elements: 3 9 8 10 7 4 6 5

Enter no. of queries: 2

Enter lower-bound and upper-bound: 1 4
The minimum in the range[1,4]: 3

Enter lower-bound and upper-bound: 4 7
The minimum in the range[4,7]: 4

Time Complexity:
Time complexity of inputRange() = O(q)
Time complexity of minRangeQuery() = O(n)
Total time complexity = O(q*n)
Where,
q = no. of queries
n = size of the array

USING SEGMENT TREE

In this, we will treat all elements of the array as leaf nodes and will use them to form a segment tree.
The segment tree will be a full binary tree in which the value of each parent element will be the minimum of its child nodes.

arr[] = {3, 9, 8, 10, 7, 4, 6 5}

By using the array we can create the following segemnt tree array:
segmentTree[] = {3, 3, 5, 3, 8, 4, 5, 3, 9, 8, 10, 7, 4, 6, 5}

Let us see how we got the values of segmentTree[]:

Range Minimum Query in Segment Tree using C++

Position of child nodes with respect to the parent node in segmentTree[]:

  • Position of parent node = i
  • Position of left child node = (2*i)+1
  • Position of right child node = (2*i)+2

Position of parent node with respect to a child node in segmentTree[]:

  • Position of left/right child node = i
  • Position of parent node = (i-1)/2

Height of segment tree = log2(n)

Code:

#include <bits/stdc++.h>
using namespace std;

//lb - lower-bound of the range query
//ub - upper-bound of the range query
//position - index of current node of segment tree
//low - starting index of our array
//high - ending index of our array

//Function for constructing segemnt tree
void constructSegemntTree(vector<int> &segmentTree, const vector<int> &a,
                          int low, int high, int position)
{
    /*It is the condition when low and the high pointer points at the 
      same location*/
    if (low == high)
    {
        segmentTree[position] = a[low];
        return;
    }

    /*Here the tree is divied and then values of its child nodes are 
      obtained using recursion*/
    /*With the help of the child nodes we can get the value of parent
      node*/
    int mid = (low + high) / 2;

    //Creates LeftChildNode
    constructSegemntTree(segmentTree, a, low, mid, 2 * position + 1);

    //Creates RightChildNode
    constructSegemntTree(segmentTree, a, mid + 1, high, 
                         2 * position + 2);

    //ParentNode = min(LeftChildNode, RightChildNode)
    segmentTree[position] = min(segmentTree[2 * position + 1], 
                                segmentTree[2 * position + 2]);
}

//Function to find minimum in a range[lb,ub]
int minRangeQuery(vector<int> &segmentTree, int low, int high, int lb, 
                  int ub, int position)
{

    //Total overlap
    /*It is the condition when our given range is exactly equal to the
    range of the segment tree node*/
    if (lb <= low && ub >= high)
        return segmentTree[position];

    //No overlap
    /*It is the condition when our given range is outside the
    range of the segment tree node*/
    if (lb > high || ub < low)
        return INT_MAX;

    //Partial overlap
    /*It is the condition when either lb or ub overlaps with the
    range of the segment tree node*/
    int mid = (low + high) / 2;
    int min1 = minRangeQuery(segmentTree, low, mid, lb, ub, 
                             2 * position + 1);
    int min2 = minRangeQuery(segmentTree, mid + 1, high, lb, ub, 
                             2 * position + 2);
    return min(min1, min2);
}

//Function to input lb & ub and display respective output
void inputRange(vector<int> &segmentTree, vector<int> a, int q)
{

    //query loop
    //it will take the query and give the output
    while (q--)
    {
        int lb, ub;
        cout << "\nEnter lower-bound and upper-bound: ";
        cin >> lb >> ub;

        if (lb < 1 || ub > a.size() || lb > ub)
            cout << "Invalid entry";
        else
        {
            cout << "The minimum in the range[" << lb << "," << ub << "]: ";
            cout << minRangeQuery(segmentTree, 0, a.size() - 1, lb - 1, 
                                  ub - 1, 0);
        }
    }
}

int main()
{
    int n;
    cout << "Enter the size of the array: ";
    cin >> n;

    vector<int> a;
    cout << "\nEnter array elements: ";
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        a.emplace_back(x);
    }

    //Calculating the maximum size of the segment tree
    int x = ceil(log(n) / log(2));
    int size = 2 * pow(2, x) - 1;

    vector<int> segmentTree;
    for (int i = 0; i < size; i++)
        segmentTree.emplace_back(INT_MAX);
    constructSegemntTree(segmentTree, a, 0, n - 1, 0);

    int q;
    cout << "\nEnter no. of queries: ";
    cin >> q;

    inputRange(segmentTree, a, q);
    return 0;
}

Input/Output:

Enter the size of the array: 8   

Enter array elements: 3 9 8 10 7 4 6 5

Enter no. of queries: 2

Enter lower-bound and upper-bound: 1 4
The minimum in the range[1,4]: 3
Enter lower-bound and upper-bound: 4 7
The minimum in the range[4,7]: 4

Time Complexity:
Time complexity of inputRange() = O(q)
Time complexity of minRangeQuery() = O(log2n)
Total time complexity = O(q*log2n)
Where,
q = no. of queries
n = size of the array

Space Complexity:
Worst case space complexity = O(4*n) = O(n)
It is the extra space allocated for segmentTree[]

 

Also, read:

Leave a Reply

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