Given a preprocessed array, a Range Minimum Query (RMQ) returns the minimum element in a chosen subarray:

This library provides various implementations with different trade-offs:

	Preprocessing and Memory	Query
Naive	O(1)	O(N)	No preprocessing
Dense	O(N²)	O(1)	Precompute all queries
Sparse	O(N logN)	O(1)	Precompute queries with a power-of-two length
Hybrid	O(N)	O(1)	Combine Dense and Sparse to shave a log!
Segment	O(N)	O(logN)	Binary partitioning of precomputed queries

Since RMQ is a useful building block for more advanced algorithms, this package exposes a low-level interface returning the index of the minimum element: online documentation

let arr = [| "b" ; "a" ; "d" ; "c" ; "e" ; "a" |] (* given an array *)
let min_array = Rmq.of_array ( <= ) arr (* configure its [min] function *)
module Impl = Rmq.Hybrid (* choose an RMQ implementation *)
let t = Impl.preprocess min_array (* to precompute some answers *)
let found_index = Impl.minimum_index min_array t ~i:2 ~len:3 (* query range [2..4] for its minimum *)
let () = assert (arr.(found_index) = "c")

As an example application, consider finding the Lowest Common Ancestor (LCA) between any two nodes in a tree:

• An array of nodes is obtained by an in-order traversal of the tree from left to right (in dashed red)
• The minimum element (by depth) between any two nodes in the array is their lowest common ancestor

When applied to a suffix tree, this yields a constant time "Longest Common Prefix (LCP)" between any substrings! (with linear preprocessing)