NAME

RangeQuery - retrieves the minimum/maximum value from a set within a given range.

SYNOPSIS

    use RangeQuery qw(min_value max_value);

    my @set = (4,2,8,6,1,2);
    my $range = RangeQuery->new(@set);
    my $min = $range->min_value(1,3);   # 2
    my $max = $range->max_value (4, 6); # 6

DESCRIPTION

Retrieves the minimum/maximum value from a set within a given range. The range is represented with two 1-based indexes. It takes O(n log n) to build the object and O(1) to retrieve a value.

METHODS

new

Creates a new RangeQuery object. This builds the appropriate data structure in order to retrieve values efficiently.

max_value

Retrieves the maximum value within a given range. This receives two 1-based indexes.

min_value

Retrieves the minimum value within a given range. This receives two 1-based indexes.

ToDo

Implement the same funcionality with segment trees.

SEE ALSO

You can check a tutorial from TopCoder, http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor

You can check an implementation in C here http://web.ist.utl.pt/joao.carreira/rmq.html

AUTHOR

João Carreira, joao.carreira@ist.utl.pt

COPYRIGHT AND LICENSE

Copyright (C) 2009 by João Carreira

This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself, either Perl version 5.10.0 or, at your option, any later version of Perl 5 you may have available.