Struct nekolib::ds::n1_rmq::N1Rmq

source ·
pub struct N1Rmq<T> { /* private fields */ }
Expand description

$\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§

source§

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

source

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

Trait Implementations§

source§

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

source§

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

Converts to this type from the input type.

Auto Trait Implementations§

§

impl<T> RefUnwindSafe for N1Rmq<T>where T: RefUnwindSafe,

§

impl<T> Send for N1Rmq<T>where T: Send,

§

impl<T> Sync for N1Rmq<T>where T: Sync,

§

impl<T> Unpin for N1Rmq<T>where T: Unpin,

§

impl<T> UnwindSafe for N1Rmq<T>where T: UnwindSafe,

Blanket Implementations§

source§

impl<T> Any for Twhere T: 'static + ?Sized,

source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
source§

impl<T> Borrow<T> for Twhere T: ?Sized,

source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
source§

impl<T> BorrowMut<T> for Twhere T: ?Sized,

source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
source§

impl<T> From<T> for T

source§

fn from(t: T) -> T

Returns the argument unchanged.

source§

impl<T, U> Into<U> for Twhere U: From<T>,

source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

source§

impl<T, U> TryFrom<U> for Twhere U: Into<T>,

§

type Error = Infallible

The type returned in the event of a conversion error.
source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
source§

impl<T, U> TryInto<U> for Twhere U: TryFrom<T>,

§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.
§

impl<V, T> VZip<V> for Twhere V: MultiLane<T>,

§

fn vzip(self) -> V