Struct SegtreeBidir

pub struct SegtreeBidir<M: Monoid> { /* private fields */ }

非可換なモノイドを双方向から計算するセグメント木

Implementations

impl<M: Monoid> SegtreeBidir<M>

where M::Element: Clone,

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

Time complexity $O(n)$

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

モノイド列からSegtreeBidirを構築する。

Time complexity $O(|s|)$

pub fn fold_left<R: RangeBounds<usize>>(&self, range: R) -> M::Element

Time complexity $O(\log n)$

pub fn fold_right<R: RangeBounds<usize>>(&self, range: R) -> M::Element

Time complexity $O(\log n)$

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

Time complexity $O(\log n)$