Struct FenwickTree

pub struct FenwickTree<G: AbelianGroup> { /* private fields */ }

可換群の点更新・区間取得($O(\log n)$, $O(\log n)$)ができる。

Implementations

impl<G: AbelianGroup + Clone> FenwickTree<G>

pub fn new(size: usize) -> Self

長さsize、可換群groupからFenwickTree<G>を生成する。

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

i番目の要素をvalueで更新する。

Time complexity $O(\log n)$

pub fn fold_to(&self, _: RangeTo<usize>) -> G

範囲0..rで計算を集約した結果を返す。

Time complexity $O(\log n)$

pub fn fold(&self, _: Range<usize>) -> G

範囲l..rで計算を集約した結果を返す。

Time complexity $O(\log n)$

Trait Implementations

impl<G: Clone + AbelianGroup> Clone for FenwickTree<G>

fn clone(&self) -> FenwickTree<G>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<G: Default + AbelianGroup> Default for FenwickTree<G>

fn default() -> FenwickTree<G>

Returns the “default value” for a type.