Struct umgap::rmq::RMQ

pub struct RMQ<T: Ord + Display> {
    pub array: Vec<T>,
    pub block_min: Vec<usize>,
    pub sparse: Vec<Vec<usize>>,
    pub labels: Vec<usize>,
}

Represents a Range Minimum Query (RMQ), which can efficiently return the minimal value in a given range of an array.

Fields

array: Vec<T>

The full array.

block_min: Vec<usize>

The absolute position (i.e. the index in array) of the minimum for each block.

sparse: Vec<Vec<usize>>

sparse[i][j] is the position of the minimum in block[i] to block[i + 2^(j+1) - 1].

labels: Vec<usize>

The j’th bit of labels[i] is 1 iff j is the first position (in the block) left of i where array[j] < array[i].

Implementations

impl<T: Ord + Display> RMQ<T>

pub fn new(array: Vec<T>) -> RMQ<T>

Constructs an RMQ for the given array.

pub fn block_min(array: &[T]) -> Vec<usize>

Calculates the position of each block’s minimum.

pub fn sparse(array: &[T], block_min: &[usize]) -> Vec<Vec<usize>>

Calculate the values of the sparse field.

pub fn labels(array: &[T]) -> Vec<usize>

Calculate the values of the label field.

pub fn query(&self, start: usize, end: usize) -> usize

Returns the position of the minimal value in a given sublist.