Struct SegmentTreeCtx

pub struct SegmentTreeCtx<M: MonoidCtx> {
    pub N: usize,
    /* private fields */
}

セグメント木

Fields

N: usize

要素数

Implementations

impl<M: MonoidCtx> SegmentTreeCtx<M>

pub fn new(N: usize, monoid: M) -> Self

セグメント木を初期化する

• 時間計算量: $O(N)$

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

配列から初期化する

• 時間計算量: $O(N)$

pub fn update(&mut self, index: usize, value: M::Val)

index番目の要素をvalueに更新する

• 時間計算量: $O(\log N)$

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

i番目の要素の可変な参照を返す

• 時間計算量: $O(\log N)$

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

区間rangeの集約を行う

• 時間計算量: $O(\log N)$

impl<M: MonoidCtx> SegmentTreeCtx<M>

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

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

左端を固定した2分探索

• 引数lと関数fに対して，

  • f( seg.get(l..x) ) = true
  • f( seg.get(l..x+1) ) = false

  
  を満たすxを返す

引数

• f :
  • f(e) = true
  • 任意のiに対して，f( seg.get(l..i) ) = falseならば，f( seg.get(l..i+1) ) = false

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

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

右端を固定した2分探索

• 引数rと関数fに対して，

  • f( seg.get(x..r) ) = true
  • f( seg.get(x-1..r) ) = false

  
  となるようなxを返す

引数

• f :
  • f(e) = true
  • 任意のiに対して，f( seg.get(i..r) ) = falseならば，f( seg.get(i-1..r) ) = false

Trait Implementations

impl<M> Debug for SegmentTreeCtx<M>

where M: MonoidCtx, M::Val: Debug,

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

Formats the value using the given formatter.

impl<M: MonoidCtx> Index<usize> for SegmentTreeCtx<M>

type Output = <M as MonoidCtx>::Val

The returned type after indexing.

fn index(&self, idx: usize) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<M> ShowBinaryTree<usize> for SegmentTreeCtx<M>

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