Struct comlib_range::Bit

pub struct Bit<T>(_);

Binary indexed tree.

Binary indexed tree, also known as Fenwick tree, is a data structure that allows effectively updating a single value and querying the sum of values over a range.

Note that unlike most binary indexed tree implementations, this implementation uses 0-indexing instead of 1-indexing.

Time complexity

All operations on binary indexed tree take O(log n) time, unless otherwise stated.

Implementations

impl<T> Bit<T>

pub fn sum<R: RangeBounds<usize>>(&self, range: R) -> T where
    T: Add<Output = T> + Sub<Output = T> + Clone + Default, 

Computes the sum of values on the given range.

pub fn add(&mut self, index: usize, value: T) where
    T: AddAssign + Clone, 

Increases the value at the given index by the given value.

pub fn sub(&mut self, index: usize, value: T) where
    T: SubAssign + Clone, 

Decreases the value at the given index by the given value.

Trait Implementations

impl<T: Clone> Clone for Bit<T>

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

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T> Debug for Bit<T> where
    T: Add<Output = T> + Sub<Output = T> + Clone + Default + Debug, 

Debug on Bit prints the original values of the array, not the values in the nodes of the tree.

Time complexity

Printing takes O(n log n) time.

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

Formats the value using the given formatter.

impl<T> From<Vec<T, Global>> for Bit<T> where
    T: AddAssign + Clone, 

fn from(data: Vec<T>) -> Self

Constructs binary indexed tree from the given Vec.

Time complexity

Construction takes O(n log n) time.

impl<T: PartialEq> PartialEq<Bit<T>> for Bit<T>

fn eq(&self, other: &Bit<T>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Bit<T>) -> bool

This method tests for !=.

impl<T: Eq> Eq for Bit<T>

impl<T> StructuralEq for Bit<T>

impl<T> StructuralPartialEq for Bit<T>