Struct nekolib::ds::N1Rmq

pub struct N1Rmq<T> { /* private fields */ }

$\langle O(n), O(1)\rangle$ RMQ。

Idea

簡潔データ構造の文脈でよくあるように、配列を数個ずつの要素からなるブロックに区切り、 各ブロック内では表引きを行う。ここでは特に簡潔の実装にはしていないことに注意。

ブロックサイズは $b = \frac{1}{4}\log_2(n)$ とする。 ブロック内の最小値たちを、$\langle O(n\log(n)), O(1)\rangle$ の RMQ である sparse table で管理する。$O(n/\log(n)\cdot \log(n/\log(n))) = O(n)$ なので ok。

$b = \frac{1}{4}\log_2(n)$ サイズの小ブロックたちについて、それらの argmin を表引きすることを考える。Cartesian tree を考えると、argmin のテーブルは $2^{2b} = \sqrt{n}$ 種類しかないことがわかる。よって、各種類ごとに愚直に求めても $O(\sqrt{n}\,\log(n)^2)$ 時間なので、こちらも ok。

Implementations

impl<T: Clone + Ord> N1Rmq<T>

pub fn min(&self, l: usize, r: usize) -> &T

Trait Implementations

impl<T: Clone + Ord> From<Vec<T, Global>> for N1Rmq<T>

fn from(base: Vec<T>) -> Self

Converts to this type from the input type.