Skip to content

fenwick: rust implementation of Fenwick trees (aka. binary/bit indexed trees)

License

Notifications You must be signed in to change notification settings

summivox/fenwick.rs

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

12 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

A Fenwick tree or binary indexed tree/bit indexed tree is a data structure that supports the following two operations efficiently over an array of numbers a[0..n]:

  • Calculate a prefix sum: a[0] + a[1] + ... + a[i]
  • Update one element: a[i] += delta

With a naïve implementation, only one of the operations can be made to have constant time complexity while the other one has to be linear. With Fenwick tree, both take only O(log(N)).

This crate is no_std and has no (non-dev) dependencies.

Examples

Use the array module for operations on a 1D Fenwick tree:

use fenwick::array::{update, prefix_sum};

let fw = &mut [0i32; 10]; // backing array of Fenwick tree (NOT original array!)
assert_eq!(prefix_sum(fw, 0), 0);
assert_eq!(prefix_sum(fw, 9), 0);
update(fw, 0, 3); // original array: [3, 0, 0, 0, 0, 0, 0, 0, 0, 0]
assert_eq!(prefix_sum(fw, 0), 3);
assert_eq!(prefix_sum(fw, 9), 3);
update(fw, 5, 9); // original array: [3, 0, 0, 0, 0, 9, 0, 0, 0, 0]
assert_eq!(prefix_sum(fw, 4), 3);
assert_eq!(prefix_sum(fw, 5), 12);
assert_eq!(prefix_sum(fw, 6), 12);
update(fw, 4, -5); // original array: [3, 0, 0, 0, -5, 9, 0, 0, 0, 0]
assert_eq!(prefix_sum(fw, 4), -2);
assert_eq!(prefix_sum(fw, 5), 7);
update(fw, 0, -2); // original array: [1, 0, 0, 0, -5, 9, 0, 0, 0, 0]
assert_eq!(prefix_sum(fw, 4), -4);
assert_eq!(prefix_sum(fw, 5), 5);

Use the index module to implement multidimensional Fenwick trees:

use fenwick::index::zero_based::{down, up};
const MAX: usize = 1000;

fn update(i: usize, j: usize, k: usize, delta: i32) {
    for ii in up(i, MAX) {
        for jj in up(j, MAX) {
            for kk in up(k, MAX) {
                /* increment 3D array at [ii, jj, kk] by delta */
            }
        }
    }
}

fn prefix_sum(i: usize, j: usize, k: usize) -> i32 {
    let mut sum = 0i32;
    for ii in down(i) {
        for jj in down(j) {
            for kk in down(k) {
                /* increment sum by 3D array at [ii, jj, kk] */
            }
        }
    }
    sum
}

References

About

fenwick: rust implementation of Fenwick trees (aka. binary/bit indexed trees)

Topics

Resources

License

Stars

Watchers

Forks

Packages

No packages published

Languages