Struct Segtree

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

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

Implementations

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

pub fn new(n: usize) -> Self

Time complexity $O(n)$

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

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

Time complexity $O(|s|)$

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

モノイド列をスライスで返す。

pub fn fold<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)$

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

Time complexity $O(\log n)$

Trait Implementations

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

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

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<M: Monoid + Clone> From<&Segtree<M>> for Vec<M>

fn from(from: &Segtree<M>) -> Self

Converts to this type from the input type.

impl<M: Monoid> Index<usize> for Segtree<M>

type Output = M

The returned type after indexing.

fn index(&self, i: usize) -> &Self::Output

Performs the indexing (container[index]) operation.