Sparse Table Range Minimum Query Implementation in Python

By PRIYA KUMARI

Given module finds the minimum element in an array between position i to j. RMQ can be used in problems directly or can be applied to implement other task like the Lowest Common Ancestor problem.

-->Description of the method used

1. buildTable

 Parameters :- buildtable(arr,n).

Description: This method is to build the sparse table which accepts data in array form which is 1-based indexing (it should have n+1 elements and 0th index can have any value which you don't want to consider).

2. query:-

Parameters:-query (sparseTable,i,j)

Description:-This method iterate and give result   in O(log n)

3. optimisedRMQ :-

Parameters:-optimisedRMQ(sparseTable,i,j)

Description:-It finds the maximum and minimum element present in the array in O(1).

-->How to use

Create a new file where you want to use the module, and just write the code

then to test the code:-

1) Create the array in which you want to find the minimum element.

2) Build the sparse table by calling the method buildTable.

3) Print the minimum element in the table using the method optimisedRMQ.

 

O(Nlog⁡N)">O(NlogN).