Struct bio::data_structures::bit_tree::FenwickTree

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

In a max bit tree or Fenwick 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. Time Complexity: O(n) to build a new tree or O(log n) for get() and set() operations, where n = tree.len().

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

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 will have no effect.