Module bio::data_structures::bit_tree
source ·
[−]Expand description
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
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()
.
Traits
Fenwick tree prefix operator
Type Definitions
Fenwick tree specialized for prefix-max
Fenwick tree specialized for prefix-sum