Range Minimum Query | iCode

Range Minimum Query | iCode

Today we are going to learn about methods to find the minimum element in given range for an array, this problem is popularly known as range minimum query. First let us see, what are we looking at : Given an array say A[0,N-1], we are queried for the minimum element from some index 'i' to the index 'j' such that j>=i, the notation for rest of the post for this will be RMQ(i,j) s.t. j>=i. Ex: A = [3 , 2 , -1 , 4 , 2] RMQ(0,2) = -1 RMQ(3,4) = 2 RMQ(0,4) = -1 Time Complexity : construction O(1) , Query O(N) The idea is simple and straight forward, what we do is nothing but trivially search for the minimum from index 'i' to index 'j' by actually traversing the array between the indices. The worst case time complexity for the array traversal may be O(N). #include <cstdio> int RMQ(int A[],int s,int e){ int minindex = s; for(int i=s;i<=e;i++) if(A[i]<A[minindex]) minindex = i; return A[minindex]; } // driver programme int main(){ int A[10] = {3,1,2,-1,5,4,6,0,9,8};

Read full article from Range Minimum Query | iCode