Struct SegtreeBidir

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

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

Implementations

impl<M: Monoid + Clone> SegtreeBidir<M>

pub fn new(n: usize) -> Self

Time complexity $O(n)$

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

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

Time complexity $O(|s|)$

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

Time complexity $O(\log n)$

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

Time complexity $O(\log n)$

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

Time complexity $O(\log n)$