#rmq #range-minimum-query

range_minimum_query

Range Minimum Query (RMQ) is used on arrays to find the position of an element with the minimum value between two specified indices

1 unstable release

Uses new Rust 2021

0.1.0 Sep 27, 2022

#743 in Data structures

MIT license

47KB
980 lines

Range Minimum Query (RMQ) Crates.io Docs.rs MIT licensed

This crate implements a succinct data structure to solve the Range Minimum Query (RMQ) problem in constant time and linear space.

This code was derived (almost verbatim) from a succinct version of RMQ, implemented by Giuseppe Ottaviano's succinct c++ library: https://github.com/ot/succinct.

What is RMQ (taken from Wikipedia)

In computer science, a range minimum query (RMQ) solves the problem of finding the minimal value in a sub-array of an array of comparable objects. Range minimum queries have several use cases in computer science, such as the lowest common ancestor problem and the longest common prefix problem (LCP).

For example, when A = [0,5,2,5,4,3,1,6,3], then the answer to the range minimum query for the sub-array A[2...7] = [2,5,4,3,1,6] is 6, as A[6] = 1.

Usage

use range_minimum_query::Rmq;

let a = [0,5,2,5,4,3,1,6,3];
let rmq = Rmq::from_iter(a);
let res = rmq.range_minimum(2..=7);
assert_eq!(res.unwrap(),6);

License

MIT

Dependencies

~1MB
~26K SLoC