Struct GenericFenwickTree

pub struct GenericFenwickTree<T, F> { /* private fields */ }

A Fenwick tree that is generic over any type T and associative function F.

A Fenwick tree behaves more or less like a Vec<T>. Values can be pushed, popped and indexed as usual. But Fenwick trees are equipped with an addition operation that calculates prefix sums in O(log n) time. Note that “sum” is used in the documentation because addition is the most common operation, but any associative operation with an identity (any monoid) works.

For all values a, b and c, f and id should obey the following properties:

f(f(a, b), c) == f(a, f(b, c))
f(id, a) == a == f(a, id)

See also: FenwickTree.

Example

use rust_dsa::GenericFenwickTree;

// First, we create a new tree.
let mut tree = GenericFenwickTree::new(0, |&a, &b| a + b);

// Then we push some values.
tree.push(1);
tree.push(4);
tree.push(3);
tree.push(-2);

// We can index into the tree.
assert_eq!(tree[1], 4);
assert_eq!(tree.get(2), Some(&3));
assert_eq!(tree.get(4), None);

// And we can calculate prefix sums.
assert_eq!(tree.sum_to(2), 5);
assert_eq!(tree.sum_to(3), 8);
assert_eq!(tree.total(), 6);

// We can also pop values.
assert_eq!(tree.pop(), Some(-2));
assert_eq!(tree.pop(), Some(3));

// Fenwick trees work with any associative function.
let mut strings = GenericFenwickTree::new(
    String::new(),
    |a, b| format!("{a}{b}"),
);
strings.push("foo".into());
strings.push("bar".into());
strings.push("baz".into());

assert_eq!(strings.sum_to(2), "foobar");

// We can also create them direcly from arrays.
let prod = GenericFenwickTree::from_array(
    1,
    |&a, &b| a * b,
    [1, 2, 3, 4, 5, 6],
);

assert_eq!(prod.sum_to(4), 24);
assert_eq!(prod.total(), 720);

Runtime complexity

Operation	Runtime Complexity
GenericFenwickTree::from_array	O(n)
GenericFenwickTree::push	O(log n)
GenericFenwickTree::sum_to	O(log n)
GenericFenwickTree::update	O(log2 n)
GenericFenwickTree::get	O(1)
GenericFenwickTree::pop	O(1)

Implementations

impl<T, F> GenericFenwickTree<T, F>

where F: Fn(&T, &T) -> T,

pub fn new(id: T, f: F) -> Self

Creates a Fenwick tree.

pub fn from_array<const N: usize>(id: T, f: F, array: [T; N]) -> Self

Creates a Fenwick tree from an array in linear time.

Example

use rust_dsa::GenericFenwickTree;

let tree = GenericFenwickTree::from_array(
    String::new(),
    |a, b| format!("{a}{b}"),
    [
        "foo".into(),
        "bar".into(),
        "b".into(),
        "az".into(),
        "!".into(),
    ],
);

assert_eq!(tree.total(), "foobarbaz!");
assert_eq!(tree.sum_to(2), "foobar");

pub fn push(&mut self, value: T)

Pushes a value onto the end of the tree.

Example

use rust_dsa::GenericFenwickTree;

let mut tree = GenericFenwickTree::new(0, |&a, &b| a + b);
tree.push(1);
tree.push(4);
tree.push(3);
tree.push(-1);

assert_eq!(tree.len(), 4);
assert_eq!(tree.get(1), Some(&4));
assert_eq!(tree.total(), 7);

pub fn get(&self, index: usize) -> Option<&T>

Returns a reference to the value at position index if one exists.

Example

use rust_dsa::GenericFenwickTree;

let tree = GenericFenwickTree::from_array(
    0,
    |&a, &b| a + b,
    [8, 4, 2],
);

assert_eq!(tree.get(1), Some(&4));
assert_eq!(tree.get(6), None);

pub fn pop(&mut self) -> Option<T>

Removes and returns the last value in the tree, or None if the tree is empty.

Example

use rust_dsa::GenericFenwickTree;

let mut tree = GenericFenwickTree::from_array(
    0,
    |&a, &b| a + b,
    [8, 4, 2],
);

assert_eq!(tree.pop(), Some(2));
assert_eq!(tree.pop(), Some(4));
assert_eq!(tree.pop(), Some(8));
assert_eq!(tree.pop(), None);

pub fn last(&self) -> Option<&T>

Returns a reference to the last value in the tree, or None if the tree is empty.

Example

use rust_dsa::GenericFenwickTree;

let tree = GenericFenwickTree::from_array(
    0,
    |&a, &b| a + b,
    [8, 4, 2],
);

assert_eq!(tree.last(), Some(&2));

pub fn sum_to(&self, end: usize) -> T

Returns the associative operation f applied to the values with indices in the range [0, end).

Panics

Panics if end is larger than the number of values in the tree.

Example

use rust_dsa::GenericFenwickTree;

let tree = GenericFenwickTree::from_array(
    1,
    |&a, &b| a * b,
    [1, 2, 3, 4, 5],
);

assert_eq!(tree.sum_to(0), 1);
assert_eq!(tree.sum_to(3), 6);
assert_eq!(tree.sum_to(5), 120);

pub fn total(&self) -> T

Returns the associative operation f applied to all values in the tree.

Example

use rust_dsa::GenericFenwickTree;

let tree = GenericFenwickTree::from_array(
    Vec::new(),
    |a, b| [a.clone(), b.clone()].concat(),
    [
        vec![1, 2, 3],
        vec![-2, -1],
        vec![8],
    ],
);

assert_eq!(tree.total(), vec![1, 2, 3, -2, -1, 8]);

pub fn update(&mut self, index: usize, delta: &T)

Updates the value at index.

Panics

Panics if index is out of bounds.

Example

use rust_dsa::GenericFenwickTree;

let mut tree = GenericFenwickTree::new(
    0,
    |&a, &b| a + b
);
tree.push(1);
tree.push(4);
tree.push(2);

assert_eq!(tree.total(), 7);

tree.update(0, &2);
tree.update(1, &-1);

assert_eq!(tree[0], 3);
assert_eq!(tree[1], 3);
assert_eq!(tree.total(), 8);

pub fn len(&self) -> usize

Returns the number of values in the tree.

Example

use rust_dsa::GenericFenwickTree;

let mut tree = GenericFenwickTree::new(0.0, |&a, &b| a + b);

assert_eq!(tree.len(), 0);

tree.push(1.5);

assert_eq!(tree.len(), 1);

pub fn is_empty(&self) -> bool

Returns true if the tree is empty.

Example

use rust_dsa::GenericFenwickTree;

let mut tree = GenericFenwickTree::new(0.0, |&a, &b| a + b);

assert!(tree.is_empty());

tree.push(4.2);

assert!(!tree.is_empty());

pub fn clear(&mut self)

Empties the tree.

Example

use rust_dsa::GenericFenwickTree;

let mut tree = GenericFenwickTree::from_array(
    1,
    |&a, &b| a * b,
    [1, 2, 3, 4, 5],
);

assert!(!tree.is_empty());

tree.clear();

assert!(tree.is_empty());

Trait Implementations

impl<T: Clone, F: Clone> Clone for GenericFenwickTree<T, F>

fn clone(&self) -> GenericFenwickTree<T, F>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T, F> Index<usize> for GenericFenwickTree<T, F>

type Output = T

The returned type after indexing.

fn index(&self, index: usize) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<'a, T, F> IntoIterator for &'a GenericFenwickTree<T, F>

type Item = &'a T

The type of the elements being iterated over.

type IntoIter = Iter<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T, F> IntoIterator for GenericFenwickTree<T, F>

type Item = T

The type of the elements being iterated over.

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.