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/

Example

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	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.
MaxOp
SumOp

Traits

PrefixOp

Fenwick tree prefix operator

Type Definitions

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