Module fenwick::array
[−]
[src]
Operations on a 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 |
update |
Updates one element in the Fenwick tree stored in a borrowed slice (zero-based). |