range_minimum_query
| Crates.io | range_minimum_query |
| lib.rs | range_minimum_query |
| version | 0.2.0 |
| source | src |
| created_at | 2022-09-27 01:49:55.003782 |
| updated_at | 2024-10-02 03:48:23.565407 |
| description | Range Minimum Query (RMQ) is used on arrays to find the position of an element with the minimum value between two specified indices. |
| homepage | https://github.com/mpetri/rmq-rs |
| repository | https://github.com/mpetri/rmq-rs |
| max_upload_size | |
| id | 674647 |
| size | 47,674 |
Matthias Petri (mpetri)
documentation
https://docs.rs/range_minimum_query
README
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 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