Struct SegmentTree

pub struct SegmentTree<M: Monoid> {
    pub N: usize,
    /* private fields */
}

セグメント木

Fields

N: usize

要素数

Implementations

impl<T: Ord + Bounded + Clone> SegmentTree<Indexed<Min<T>>>

pub fn new_with_index(N: usize) -> Self

セグメント木（インデックス付きで）を初期化する

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

impl<T: Ord + Bounded + Clone> SegmentTree<Indexed<Max<T>>>

pub fn new_with_index(N: usize) -> Self

セグメント木を（インデックス付きで）初期化する

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

impl<M: Monoid> SegmentTree<M>

pub fn new(N: usize) -> Self

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

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

pub fn from_vec(src: Vec<M::Val>) -> 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: Monoid> SegmentTree<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 SegmentTree<M>

where M: Monoid, M::Val: Debug,

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

Formats the value using the given formatter.

impl<M: Monoid> FromIterator<<M as Monoid>::Val> for SegmentTree<M>

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

Creates a value from an iterator.

impl<M: Monoid> Index<usize> for SegmentTree<M>

type Output = <M as Monoid>::Val

The returned type after indexing.

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

Performs the indexing (container[index]) operation.

impl<M> ShowBinaryTree<usize> for SegmentTree<M>

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