#tree #fenwick #binary #structure #data #indexed #log

fenwick-tree

An implementation of a binary indexed tree (Fenwick tree) data structure in Rust

3 unstable releases

0.1.0 May 29, 2021
0.0.2 May 13, 2021
0.0.1 May 11, 2021

#1561 in Data structures

34 downloads per month

MIT license

18KB
233 lines

fenwick-tree

crates.io Build

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.

No runtime deps