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

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

, then the answer to the range minimum query for the sub-array `A = [0,5,2,5,4,3,1,6,3]`

`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