Struct LazySegtree

pub struct LazySegtree<M: Monoid, A: Act<M>> { /* private fields */ }

モノイド列の区間更新・区間取得($O(\log n)$, $O(\log n)$)ができる。

Implementations

impl<M, A> LazySegtree<M, A>

where M: Monoid, A: Act<M>, M::Element: Clone, A::Element: Clone + PartialEq,

pub fn new(monoid: M, act: A, n: usize) -> Self

長さnのLazySegtreeを生成する。

pub fn from_vec(monoid: M, act: A, s: Vec<M::Element>) -> Self

VecからLazySegtreeを構築する。

Time complexity $O(|s|)$

pub fn to_slice(&mut self) -> &[M::Element]

遅延操作を完了させたモノイド列をスライスで返す。

Time complexity $O(n)$

pub fn get(&mut self, i: usize) -> M::Element

i番目の値を返す。

pub fn fold(&mut self, range: impl RangeBounds<usize>) -> M::Element

区間rangeで計算を集約して返す。

pub fn assign(&mut self, i: usize, value: M::Element)

i番目の値をvalueで置き換える。

pub fn update(&mut self, range: impl RangeBounds<usize>, x: A::Element)

区間rangeを値xで更新する。