Trait FenwickTree

pub trait FenwickTree {
    type Value: FenwickTreeValue;

    // Required methods
    fn query(&self, idx: usize) -> Result<Self::Value, TreeError>;
    fn update(
        &mut self,
        idx: usize,
        value: Self::Value,
    ) -> Result<(), TreeError>;

    // Provided method
    fn range_query(
        &self,
        from: usize,
        to: usize,
    ) -> Result<Self::Value, TreeError> { ... }
}

Fenwick tree trait, API of that data structure

Required Associated Types

type Value: FenwickTreeValue

Required Methods

fn query(&self, idx: usize) -> Result<Self::Value, TreeError>

Returns sum of values across all indexes lesser or equal than idx.

Errors

This function will returns an error if idx is out of bounds. GrowingFenwick tree implementation never returns error.

fn update(&mut self, idx: usize, value: Self::Value) -> Result<(), TreeError>

Add new value to the idx stored value, which is 0 by default.

Errors

This function will return an error if idx is out of bounds. GrowingFenwick tree implementation never returns error.

Provided Methods

fn range_query(&self, from: usize, to: usize) -> Result<Self::Value, TreeError>

Returns sum of values across all indexes in between from and to indexes (including edges).

Errors

This function will return an error if any index is out of bounds. GrowingFenwick tree implementation never return error.

Implementors

impl<T: FenwickTreeValue> FenwickTree for FixedSizeFenwickTree<T>

type Value = T

impl<T: FenwickTreeValue> FenwickTree for GrowingFenwickTree<T>

type Value = T