An implementation of the binary indexed tree (or Fenwick tree) data structure in Rust.

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);

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.

For more details see documentation.

The package is licensed under the MIT license.

There are no strict rules for contributing. Feel free to open an issue or submit a pull request.