Expand description
A binary indexed tree (Fenwick tree) for efficient prefix sums.
A BITree<T> maintains prefix sums over a mutable sequence of values.
Both point updates and prefix queries run in O(log n) time, and the
whole structure lives in a single Vec<T> the same length as the
logical array.
This crate is no_std-compatible; it depends only on alloc. Values are
generic over any T implementing AddAssign<&T> — and, where a method
requires subtraction, SubAssign<&T>. T: Copy is not required, so
arbitrary-precision integers and similar types are supported.
§Examples
use bitree::BITree;
let mut bitree = BITree::from_iter([1, 6, 3, 9, 2]);
// Prefix sums in O(log n); `prefix_sum(i)` covers `[0..i)`.
assert_eq!(bitree.prefix_sum(3), 10);
assert_eq!(bitree.prefix_sum(5), 21);
// Point update.
bitree.add_at(1, 5);
assert_eq!(bitree.prefix_sum(3), 15);
// Grow and shrink like a `Vec`.
bitree.push(4);
bitree.pop();
// Recover the original values.
assert_eq!(Vec::from(bitree), vec![1, 11, 3, 9, 2]);§Crate features
serde— deriveSerializeandDeserializeforBITree<T>.
Structs§
- BITree
- A binary indexed tree (Fenwick tree) over a sequence of
Tvalues.