范围最小值查询（RMQ）

这个crate实现了一种简洁的数据结构，用于在常数时间和线性空间内解决范围最小值查询（RMQ）问题。

此代码几乎直接来源于Giuseppe Ottaviano的简洁C++库中的RMQ简洁版本： https://github.com/ot/succinct.

什么是RMQ（来自维基百科）

在计算机科学中，范围最小值查询（RMQ）解决的是在可比较对象数组的一个子数组中找到最小值的问题。范围最小值查询在计算机科学中有多个用途，如最低公共祖先问题和最长公共前缀问题（LCP）。

例如，当 A = [0,5,2,5,4,3,1,6,3] 时，子数组 A[2...7] = [2,5,4,3,1,6] 的范围最小查询答案是 6，因为 A[6] = 1。

用法

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

许可证

MIT