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)
Read full article from Range Minimum Query | iCode
No comments:
Post a Comment