Struct LazySegmentTree

pub struct LazySegmentTree<M: ActedMonoid> {
    pub size: usize,
    /* private fields */
}

遅延評価セグメント木

Fields

size: usize

Implementations

impl<M: ActedMonoid> LazySegmentTree<M>

pub fn new(n: usize) -> Self

遅延評価セグメント木を初期化する

• n: 配列サイズ

pub fn from_vec(src: Vec<M::Val>) -> Self

配列から構築する

pub fn set(&mut self, i: usize, v: M::Val)

要素を更新する

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

要素を取得する

pub fn apply_at(&mut self, i: usize, f: M::Act)

要素へ作用させる

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

区間にvalを作用させる

• range: [left, right)

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

区間を取得する

• range: [left, right)

pub fn all_prod(&self) -> M::Val

全区間の集約

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

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

左端を固定した2分探索

• 返り値: (prod([l, Val)), Val)

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

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

右端を固定した2分探索

• 返り値: (prod([Val, r)), Val)

Trait Implementations

impl<M: Debug + ActedMonoid> Debug for LazySegmentTree<M>

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

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<M: ActedMonoid> FromIterator<<M as ActedMonoid>::Val> for LazySegmentTree<M>

fn from_iter<T: IntoIterator<Item = M::Val>>(iter: T) -> Self

Creates a value from an iterator.

impl<M> ShowBinaryTree<usize> for LazySegmentTree<M>

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

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

<required> 根を取得する

fn get_left(&self, i: &usize) -> Option<usize>

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

fn get_right(&self, i: &usize) -> Option<usize>

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

fn print_node(&self, i: &usize) -> String

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

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

再帰的にprintを行う

fn print_as_binary_tree(&self)

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