Struct ImplicitTreap

pub struct ImplicitTreap<M: ActedMonoid> {
    pub root: Option<Ptr>,
    /* private fields */
}

Implicit Treap

• 動的な列を管理するデータ構造

Fields

root: Option<Ptr>

Implementations

impl<M: ActedMonoid> ImplicitTreap<M>

pub fn get(&mut self, i: usize) -> M::Val

i 番目の要素の値を取得する（clone）

pub fn insert(&mut self, i: usize, val: M::Val)

i 番目に要素 val を挿入する

• self.len() <= i の場合，末尾に追加する．

pub fn push_back(&mut self, val: M::Val)

末尾に要素 val を挿入する

pub fn remove(&mut self, i: usize)

i 番目の要素を削除する

• self.len() <= i の場合，None を返す．

pub fn get_range<R: RangeBounds<usize> + Debug>(&mut self, range: R) -> M::Val

区間の集約値を返す

pub fn apply<R: RangeBounds<usize> + Debug>(&mut self, range: R, act: M::Act)

区間に作用を適用する

pub fn reverse<R: RangeBounds<usize> + Debug>(&mut self, range: R)

区間反転

pub fn is_empty(&self) -> bool

空であるか判定する

pub fn len(&self) -> usize

要素数をカウントする

pub fn split_nth( &mut self, ptr: Option<Ptr>, n: usize, ) -> (Option<Ptr>, Option<Ptr>)

ptr を根とする木を，左から n 番目までのノードとそれ以外のノードに分解する

pub fn merge(&mut self, left: Option<Ptr>, right: Option<Ptr>) -> Option<Ptr>

left, right を根とする木を併合する

impl<M: ActedMonoid> ImplicitTreap<M>

pub fn max_right<F>(&mut self, l: usize, f: F) -> (M::Val, usize)

where F: Fn(M::Val) -> bool,

左端固定二分探索（segtree の max_right と同じ）

返り値：(get_range(l..x), x) 条件：f(M::e()) == true

pub fn min_left<F>(&mut self, r: usize, f: F) -> (M::Val, usize)

where F: Fn(M::Val) -> bool,

右端固定二分探索（segtree の min_left と同じ）

返り値：(get_range(x..r), x) 条件：f(M::e()) == true

Trait Implementations

impl<M: ActedMonoid> Default for ImplicitTreap<M>

fn default() -> Self

Returns the “default value” for a type.

impl<M> ShowBinaryTree<Ptr> for ImplicitTreap<M>

where M: ActedMonoid, M::Val: Debug, M::Act: Debug,

fn get_root(&self) -> Option<Ptr>

<required> 根を取得する

fn get_left(&self, ptr: &Ptr) -> Option<Ptr>

<required> 左の子のポインタを取得する

fn get_right(&self, ptr: &Ptr) -> Option<Ptr>

<required> 右の子のポインタを取得する

fn print_node(&self, ptr: &Ptr) -> String

<required> ノードの値を表示する

fn print_inner(&self, ptr: P, fill: &mut Vec<&'static str>, last: &'static str)

再帰的にprintを行う

fn print_as_binary_tree(&self)

2分木としてフォーマットする