Struct DualSegtree

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

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

Implementations

impl<M: Monoid> DualSegtree<M>

where M::Element: Clone,

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

Time complexity $O(n)$

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

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

Time complexity $O(|a|)$

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

Time complexity $O(\log n)$

pub fn to_vec(&self) -> Vec<M::Element>

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

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

Time complexity $O(\log n)$

Trait Implementations

impl<M: Clone + Monoid> Clone for DualSegtree<M>

where M::Element: Clone,

fn clone(&self) -> DualSegtree<M>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.