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.