Range minimum query

Malay Gain
Last Updated: May 13, 2022

Introduction

‘Range minimum query’ is a well-known problem that can be solved using the segment tree. In this article, we will see how to solve such query problems efficiently using a segment tree.

 

Segment tree is a special kind of data structure that is used to store information about intervals or segments of an array. Let’s see its representation.

 

Representation of segment tree

  • The segment tree is represented as an array just like a heap. For a node of the segment tree at index i of the segment tree, its left child will be at index   2*i + 1, and its right child will be at index 2*i+2.

 

  • The leaf nodes of the segment tree are the elements of the input array whose information about intervals we are storing.

 

  • Each internal node of the tree is merging its child nodes. The method of merging depends on the problem. For the ‘range minimum query’, problem merging is the minimum of its child nodes.

 

Problem Statement

You are given an array of integers, given m numbers of queries of range (specified by indices of the array). You need to return minimum elements for each given range.

Example

Input:

 

n=5  (size of array)

arr[ ]={1,2,3,4,5}

m=3  (numbers of queries)

0  4

0  3

2  4

 

Output:

1

1

3

 

For 1st query min(1,2,3,4,5)=1;

      2nd query min(1,2,3,4)=1;

      3rd query min(3,4,5)=3

 

Method

Brute Force approach

The brute force approach is for each query to run a loop in the given range and find the minimum in that range.

So, for m, such queries on an array of size n, the time complexity will be O(m*log n) in the worst case.

 

Segment Tree-based approach

 

Step 1: construction of segment tree of the given array

 

Initially, we start with the given array arr[0 . . . n-1] as the initial segment. In each step, we divide the current segment into two halves(until it becomes a segment of length equal to 1), and then call the same procedure on both halves, and for each segment, we store the minimum value of the segment in a segment tree node. 

 

The segment tree will be a full binary tree as we always divide segments into two halves at every level. As the constructed tree is a full binary tree with n leaves(i.e., elements of the input array), there will be n-1 internal nodes. So, the total number of nodes in the segment tree will be 2*n – 1. 

 

The time complexity for constructing the segment tree is O(n) as there are 2*n-1 nodes whose value is calculated only once.

 

Step 2: querying for the minimum value of the given range

 

We will now follow an algorithm to find the minimum of a given range from the segment tree.

// function for answering each query
query(int idx,int l,int r)
{
if the segment of node at idx is part of
  the given range 

return st[idx];


if the segment of node at idx is outside of the given range

    return INT_MAX;



if the given range overlaps with segment of the node

left=query(2*idx+1,l,r); // min of left half of the given range
right=query(2*idx+2,l,r); // min of right half of the given range

 return min(left,right);
}

 

 

Code

// c++ code for range minimum query problem

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


// constructing segment tree from the given array 

void buildST(int idx, int low,int high,vector<int> &st,int arr[])
{
// if there is one element in the array
if(low==high)
{
st[idx]=arr[low];
return;
}


// if there is  more than one element,
// recur for left and right subtrees

int mid=(high+low)/2;

buildST(2*idx+1,low,mid,st,arr);
buildST(2*idx+2,mid+1,high,st,arr);

st[idx]=min(st[2*idx+1],st[2*idx+2]);
}




// function for answering each query
int query(int idx,int low,int high,int l,int r,vector<int> st)
{
// if the segment of node at idx is part of
// the given range 
if(l<=low && r>=high)
{
return st[idx];
}

// the segement of node at idx is ouside of the given range
if(high<l || low>r) return INT_MAX;



//if the given range overlaps with segment of the node

int mid=(high+low)/2;

int left=query(2*idx+1,low,mid,l,r,st);
int right=query(2*idx+2,mid+1,high,l,r,st);

return min(left,right);
}


// Driver code

int main()
{
int n=5;

int arr[]={1,2,3,4,5};

vector<int> st(2*n-1); // array representation of segment tree

buildST(0,0,n-1,st,arr);

int m=3// no of queries
int l,r;

while(m--)
{
cin>>l>>r;
cout<<query(0,0,n-1,l,r,st)<<endl;
}


}

 

Input(query)

0  4

0  3

2  4

 

Output

1

1

3

 

Complexity

The time complexity for the above algorithm for each query is O(log n) where n is the size of the given array as the number of levels in the segment tree is O(log n).

 

Here space complexity is O(n) as we are using extra space for constructing the segment tree with (2*n - 1) nodes.

 

FAQs

  1. What is a segment tree?
    Segment tree is a special kind of data structure that is used to store information about intervals or segments of an array. It is represented by an array.
     
  2. Is a segment tree a binary tree?
    As for each parent node, there are at most two child nodes; segment tree is a binary tree.
     
  3. Is it a complete tree or a full tree?
    The segment tree is a full binary tree as we always divide segments of the given array into halves at every level.
     
  4. What is the difference between segment tree and heap?
    Heap is a complete binary tree, but the segment tree is a full binary tree. Their use cases are also different.
     
  5. In what kind of problem segment tree is used?
    → To solve min, max, or sum queries of a given range on an array.
    → Here we have discussed the range minimum query problem.

 

Key Takeaways

This article covered the range minimum query problem. We have learned about the application of the segment tree to solve problems like the range minimum query problem.

Apart from this, you can practice a wide range of coding questions commonly asked in interviews in CodeStudio. Along with coding questions, we can also find the interview experience of scholars working in renowned product-based companies here. 

Happy learning!

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think