‘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.
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.
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
returnINT_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> usingnamespacestd;
// constructing segment tree from the given array
voidbuildST(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
// function for answering each query intquery(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
intmain() { int n=5;
int arr[]={1,2,3,4,5};
vector<int> st(2*n-1); // array representation of segment tree
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
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.
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.
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.
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.
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 Coding Ninjas Studio. Along with coding questions, we can also find the interview experience of scholars working in renowned product-based companies here.
38+ registered 