Range Minimum Query

Download

Download jar file or use maven. psjava requires Java 1.6 (or above)

<dependency>
    <groupId>org.psjava</groupId>
    <artifactId>psjava</artifactId>
    <version>0.1.19</version>
</dependency>

Example Code

Array<String> array = ArrayFromVarargs.create("A", "E", "B", "C", "G");

RangeMinimumQuerySession session = GoodRangeMinimumQuery.getInstance().preprocess(array, new DefaultComparator<String>());

int index1 = session.getIndex(1, 4); // must be 2, that is the index of "B" among ("E", "B", "C")

int index2 = session.getIndex(0, 3); // must be 0, that is the index of "A" among ("A", "E", "B")

// There are several implementations of range minimum query problem.
// They have different time & space complexity. See the detail in an article of TopCoder
// http://www.topcoder.com/tc?d1=tutorials&d2=lowestCommonAncestor&module=Static

RangeMinimumQueryUsingSegmentTree.getInstance(GoodSegmentTreeFactory.getInstance());
RangeMinimumQueryBySquareRootApproach.getInstance();
RangeMinimumQueryUsingSparseTable.getInstance();

See Also

Implementation

Copyright 2014 psjava team. View on GitHub