Struct cp_library_rs::data_structure::dynamic_segment_tree::DynamicSegmentTree

pub struct DynamicSegmentTree<K: Ord, M: Monoid> {
    pub root: Option<Box<NodeInner<K, M>>>,
    /* private fields */
}

動的セグメント木

• 平行2分木（AA木）
• 遅延評価なし

Fields

root: Option<Box<NodeInner<K, M>>>

Implementations

impl<K: Ord, M: Monoid> DynamicSegmentTree<K, M>

pub fn get(&self, key: &K) -> &M::Val

1点取得（不変参照）

• 値 key を持つノードの不変参照を取得する

pub fn get_mut(&mut self, key: K) -> NodeEntry<'_, K, M>

1点取得（可変参照）

• 値 key を持つノードの可変参照を取得する

pub fn insert(&mut self, key: K, value: M::Val)

要素の更新

• key：更新するキー
• value：更新後の値

pub fn remove(&mut self, key: &K) -> Option<M::Val>

要素の削除

• key：削除するキー

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

区間の取得

• 区間 range の要素を集約する

pub fn len(&self) -> usize

要素数を取得

pub fn is_empty(&self) -> bool

impl<K, M> DynamicSegmentTree<K, M>where K: Ord + Debug, M: Monoid, M::Val: Debug,

pub fn print_as_binary_tree(&self)

2分木として出力する

Trait Implementations

impl<K: Ord, M: Monoid> Default for DynamicSegmentTree<K, M>

fn default() -> Self

動的セグ木の初期化