Module fenwick::array

Operations on an 1D Fenwick tree stored in a zero-based slice.

Examples

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

Functions

prefix_sum

Calculates the prefix sum up to and including i in the Fenwick tree stored in a borrowed slice (zero-based).

update

Updates one element in the Fenwick tree stored in a borrowed slice (zero-based).