3 unstable releases
0.1.0 | May 29, 2021 |
---|---|
0.0.2 | May 13, 2021 |
0.0.1 | May 11, 2021 |
#1691 in Data structures
18KB
233 lines
fenwick-tree
An implementation of the binary indexed tree (or Fenwick tree) data structure in Rust.
Overview
fenwick-tree
provides a simple implementation of the Fenwick tree that can be used as a building block in some algorithms like weighted random.
The basic API is simple and consists of add
and sum
methods (both take O(log n) time). Here is a quick example:
use fenwick_tree::*;
let mut tree = FenwickTree::<i32>::with_len(5);
for i in 0..5 {
tree.add(i, i as i32)?;
}
assert_eq!(tree.sum(..)?, 0 + 1 + 2 + 3 + 4);
assert_eq!(tree.sum(1..)?, 1 + 2 + 3 + 4);
assert_eq!(tree.sum(2..5)?, 2 + 3 + 4);
assert_eq!(tree.sum(3..=4)?, 3 + 4);
Panics
Both add
and sum
methods return Result
and are not expected to panic.
However, with_len
constructs the backing vector by using vec![I::default(); len]
, and it actually may panic as in regular Rust code.
Learn more
For more details see documentation.
License
The package is licensed under the MIT license.
Contributing
There are no strict rules for contributing. Feel free to open an issue or submit a pull request.