Module fenwick::index

Iterators yielding index sequences for traversing Fenwick trees.

• down(i) yields indices of nodes which can be summed together to obtain prefix sum up to i.
• up(i, limit) yields indices of nodes that should be updated when updating element i.

Traditionally Fenwick trees are implemented using one-based arrays for both tree and value arrays. While this simplifies the definition of index sequences, an offset is required for it to work in languages (such as rust) that has zero-based array indexing. Alternatively, the algorithms can be simplified to directly work with zero-based indices.

This module implements both zero-based and one-based index sequences.

Examples

An ad-hoc 3D Fenwick tree over a 3D array may be implemented as follows:

use fenwick::index::zero_based::{down, up};

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) {
                array3d_add_assign(ii, jj, kk, 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) {
                sum += array3d_get(ii, jj, kk);
            }
        }
    }
    sum
}

Modules

one_based
zero_based