Struct FenwickTree

pub struct FenwickTree<I>
where
    I: Default + Copy + AddAssign + SubAssign,
{ /* private fields */ }

An implementation of the binary indexed tree (Fenwick tree) data structure.

The tree is backed by a simple vec of the fixed size where each item is responsible for storing cumulative sum of some range, allowing to perform queries and updates in O(log n) time.

Implementations

impl<I> FenwickTree<I>

where I: Default + Copy + AddAssign + SubAssign,

pub fn with_len(len: usize) -> Self

Constructs a new Fenwick tree with the specified len with each element set as I::default().

The vector is initialized with vec![I::default(); len].

Panics

Vector initialization may panic if len is too big.

pub fn len(&self) -> usize

A length of the backing vector of the tree.

pub fn sum(&self, bounds: impl RangeBounds<usize>) -> Result<I, SumError>

A partial sum of the specified bounds.

Complexity: O(log n).

Note that sum for empty range (a range (i..j) where i >= j) is 0.

Also, bounds are converted into a pair (start, end) that represents [start, end) range. This means that boundary case tree.sum(i..=usize::MAX) fallbacks to tree.sum(0..usize::MAX). However, in practice, it’s not possible to construct such a big tree (Vec panics with capacity overflow).

pub fn add(&mut self, i: usize, delta: I) -> Result<(), AddError>

Updates the value at i by delta.

Complexity: O(log n).