Coders Packet

Sparse Table Range Minimum Query Implementation in Python

By PRIYA KUMARI

  • sparseTable/
  • 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

    from sparse_table_rmq import buildTable,optmisedRMQ

    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).

     

     

    Download Complete Code

    Comments

    Comments for the packet "Sparse Table Range Minimum Query Implementation in Python";
    No comments yet