Struct DynamicSegmentTree

pub struct DynamicSegmentTree<I: PrimInt, M: ActedMonoidWithSize> {
    pub n: I,
    /* private fields */
}

Fields

n: I

Implementations

impl<I: PrimInt + ToPrimitive, M: ActedMonoidWithSize> DynamicSegmentTree<I, M>

pub fn new(min: I, max: I) -> Self

pub fn update(&mut self, index: I, val: M::Val)

点更新

• 計算量：(O(\log (max-min)))

pub fn get(&mut self, index: I) -> M::Val

点取得（未生成は M::e_with_size()）

• 遅延があるので push するため &mut self

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

区間の集約値（RangeBounds を受け取る）

• 遅延があるので push するため &mut self

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

区間に作用を適用（遅延）

pub fn get_mut(&mut self, i: I) -> Option<ValMut<'_, I, M>>

get_mut（Drop で update）

impl<I, M> DynamicSegmentTree<I, M>

where I: PrimInt, M: ActedMonoidWithSize, M::Val: Debug,

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

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

左端固定二分探索 返り値：(get_range(l..x), x)

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

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

右端固定二分探索 返り値：(get_range(x..r), x)

Trait Implementations

impl<I, M> ShowBinaryTree<Ptr> for DynamicSegmentTree<I, M>

where I: PrimInt, M: ActedMonoidWithSize, 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分木としてフォーマットする