Struct sfcpl::structure::fenwick_tree::FenwickTree

pub struct FenwickTree<T: Add> { /* fields omitted */ }

更新、区間和の取得がともにO(log n)で 可能なデータ構造

Implementations

impl<T: Add + Sub<Output = T> + Zero + Clone + Ord + Into<usize>> FenwickTree<T>

pub fn new(n: usize) -> Self

サイズを指定して、zerosで初期化

pub fn from(vec: &[T]) -> Self

配列から構築

pub fn len(&self) -> usize

扱える要素の最大値

pub fn add(&mut self, i: usize, v: T)

更新

i番目の要素 += v

O(log n)

pub fn sum(&self, i: usize) -> T

[0..i)の区間和

O(log n)

pub fn partial_sum(&self, a: usize, b: usize) -> T

[a..b)の区間和

O(log n)

Trait Implementations

impl<T: Clone + Add> Clone for FenwickTree<T>

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

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T: Debug + Add> Debug for FenwickTree<T>

fn fmt(&self, f: &mut Formatter) -> Result

Formats the value using the given formatter.