Module bio::data_structures::bit_tree

BIT-tree (Binary Indexed Trees, aka Fenwick Tree) maintains a prefix-sum or prefix-max that can be efficiently queried and updated. From: Peter M. Fenwick (1994). “A new data structure for cumulative frequency tables”. Software: Practice and Experience. 24 (3): 327–336. Implementation outlined here: https://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/

Time Complexity: O(log n) where n = tree.len(). Memory Complexity: O(n) where n = tree.len().

Example for a max bit tree

use bio::data_structures::bit_tree::*;

let mut bit = MaxBitTree::new(10);
bit.set(0, (1,0));
bit.set(1, (0,1));
bit.set(2, (2,2));
bit.set(3, (4,3));

assert_eq!(bit.get(0), (1, 0));
assert_eq!(bit.get(1), (1, 0));
assert_eq!(bit.get(2), (2, 2));
assert_eq!(bit.get(3), (4, 3));
assert_eq!(bit.get(4), (4, 3));

Structs

FenwickTree	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().
MaxOp
SumOp

Traits

PrefixOp

Fenwick tree prefix operator

Type Definitions

MaxBitTree	Fenwick tree specialized for prefix-max
SumBitTree	Fenwick tree specialized for prefix-sum