Module Rmq

type min_array = {
length : int;(*

Number of elements in the array

*)
cmp : int -> int -> bool;(*

cmp i j returns true if the element at index i is less than or equal to the element at index j in the array

*)
}

An abstract representation of an array supporting the comparison of its elements.

val of_array : ( 'a -> 'a -> bool ) -> 'a array -> min_array

of_array cmp arr returns an implementation of min_array using cmp to compare the elements of the array arr. The function cmp x y should return true if x is less than or equal to the value y.

module type S = sig ... end
module Naive : S with type t = unit

O(N) query, O(1) preprocessing and memory.

module Dense : S

O(1) query, O(N^2) preprocessing and memory.

module Sparse : S

O(1) query, O(N logN) preprocessing and memory.

module Hybrid : S

O(1) query, O(N) preprocessing and memory.

module Segment : S

O(logN) query, O(N) preprocessing and memory.