Struct LazySegtree

pub struct LazySegtree<A: Action> { /* private fields */ }

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

Implementations

impl<A: Action> LazySegtree<A>

where A::Output: Clone + PartialEq, A::Lazy: Clone + PartialEq,

pub fn new(n: usize) -> Self

長さnのLazySegtreeを生成する。

pub fn from_vec(s: Vec<A::Output>) -> Self

VecからLazySegtreeを構築する。

Time complexity $O(|s|)$

pub fn to_slice(&mut self) -> &[A::Output]

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

Time complexity $O(n)$

pub fn get(&mut self, i: usize) -> A::Output

i番目の値を返す。

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

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

pub fn assign(&mut self, i: usize, value: A::Output)

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

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

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