Struct bio::data_structures::bit_tree::FenwickTree

pub struct FenwickTree<T: Default + Ord, Op: PrefixOp<T>> { /* private fields */ }

Max Bit Tree. get(i) will return the largest element e that has been added to the bit tree with set(j, e), where j <= i. Initially all positions have the value T::default(). Note that a set cannot be ‘undone’ by inserting a smaller element at the same index.

Implementations

impl<T: Ord + Default + Copy, Op: PrefixOp<T>> FenwickTree<T, Op>

pub fn new(len: usize) -> FenwickTree<T, Op>

Create a new bit tree with len elements

pub fn get(&self, idx: usize) -> T

get(i) returns the largest element e that has been added to the bit tree with set(j, e), where j <= i.

pub fn set(&mut self, idx: usize, val: T)

Set the value val at position idx. val will be returned for any get(j) where j >= idx, if it is the maximum value inserted between 0 and j. Inserting a value val2 after inserting val1 where val1 > val2