## no-std fenwick

Fenwick tree: data structure that efficiently calculates prefix sums in a changing array of numbers

### 7 releases(3 stable)

 2.0.1 Sep 15, 2022 Sep 14, 2022 Feb 23, 2020 Apr 7, 2018 Apr 6, 2018

#494 in Algorithms

Used in 6 crates (3 directly)

15KB
173 lines

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
}
``````