Struct FenwickTree

pub struct FenwickTree<I>(/* private fields */);

A Fenwick tree specialized for primitive integers and addition.

Allowing only primitive integers enables the sum and set operations along with a O(log n) update implementation.

See also: GenericFenwickTree.

Example

use rust_dsa::FenwickTree;

// First, we create an empty tree.
let mut tree = FenwickTree::new();

// 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 sums.
assert_eq!(tree.sum_to(2), 5);
assert_eq!(tree.sum(1..3), 7);
assert_eq!(tree.total(), 6);

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

// We can create trees from iterators.
let mut digits: FenwickTree<u64> = (0..=9).collect();

// And update/set values.
digits.update(2, 4);
digits.set(6, 0);

assert_eq!(digits[2], 6);
assert_eq!(digits[6], 0);

// We can also create trees from arrays.
let more_digits = FenwickTree::from([0, 1, 6, 3, 4, 5, 0, 7, 8, 9]);

assert!(digits == more_digits);

Runtime complexity

Operation	Runtime Complexity
FenwickTree::from_iter	O(n)
FenwickTree::push	O(log n)
FenwickTree::sum_to	O(log n)
FenwickTree::sum	O(log n)
FenwickTree::update	O(log n)
FenwickTree::set	O(log n)
FenwickTree::get	O(1)
FenwickTree::pop	O(1)

Implementations

impl<I: PrimInt> FenwickTree<I>

pub fn new() -> Self

where I: WrappingAdd,

Creates a Fenwick tree.

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

Pushes a value onto the end of the tree.

Example

use rust_dsa::FenwickTree;

let mut tree = FenwickTree::new();
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<I>

Returns the value at position index if one exists.

Example

use rust_dsa::FenwickTree;

let tree = FenwickTree::from([8, 4, 2]);

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

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

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

Example

use rust_dsa::FenwickTree;

let mut tree = FenwickTree::from([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<I>

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

Example

use rust_dsa::FenwickTree;

let tree = FenwickTree::from([8, 4, 2]);

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

let empty: FenwickTree<u8> = FenwickTree::new();

assert_eq!(empty.last(), None);

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

Returns the sum of 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::FenwickTree;

let tree = FenwickTree::from([1, 2, 3, 4, 5]);

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

pub fn sum<R: RangeBounds<usize>>(&self, range: R) -> I

where I: WrappingSub,

Returns the sum of the values with indices in range.

Panics

Panics if the starting point is greater than the end point or if the end point is greater than the number of values in the tree.

Example

use rust_dsa::FenwickTree;

let tree: FenwickTree<_> = (2..12).collect();

assert_eq!(tree.sum(4..8), 30);
assert_eq!(tree.sum(..=3), 14);
assert_eq!(tree.sum(5..), 45);
assert_eq!(tree.sum(..), 65);

pub fn total(&self) -> I

Returns sum of all values in the tree.

Example

use rust_dsa::FenwickTree;

let tree = FenwickTree::from([1, 2, 3, 4, 5]);

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

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

Updates the value at index.

Panics

Panics if index is out of bounds.

Example

use rust_dsa::FenwickTree;

let mut tree = FenwickTree::from([1, 2, 3, 4, 5]);

tree.update(1, 4);
tree.update(2, -1);

assert_eq!(tree[1], 6);
assert_eq!(tree[2], 2);
assert_eq!(tree.total(), 18);

pub fn set(&mut self, index: usize, new_value: I)

where I: WrappingSub,

Sets the value at index.

Panics

Panics if index is out of bounds.

Example

use rust_dsa::FenwickTree;

let mut tree = FenwickTree::from([1_usize, 4, 8, 16]);

tree.set(1, 6);
tree.set(2, 2);

assert_eq!(tree[1], 6);
assert_eq!(tree[2], 2);
assert_eq!(tree.total(), 25);

pub fn len(&self) -> usize

Returns the number of values in the tree.

Example

use rust_dsa::FenwickTree;

let mut tree = FenwickTree::from([1, 2, 3, 4, 5]);

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

tree.pop();

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

pub fn is_empty(&self) -> bool

Returns true if the tree is empty.

Example

use rust_dsa::FenwickTree;

let mut tree = FenwickTree::from([1, 2, 3, 4, 5]);

assert!(!tree.is_empty());

tree.clear();

assert!(tree.is_empty());

pub fn clear(&mut self)

Empties the tree.

Example

use rust_dsa::FenwickTree;

let mut tree = FenwickTree::from([1, 2, 3, 4, 5]);

assert!(!tree.is_empty());

tree.clear();

assert!(tree.is_empty());

Trait Implementations

impl<I: Clone> Clone for FenwickTree<I>

fn clone(&self) -> FenwickTree<I>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<I: PrimInt + WrappingAdd> Default for FenwickTree<I>

fn default() -> Self

Returns the “default value” for a type.

impl<I: PrimInt + WrappingAdd, const N: usize> From<[I; N]> for FenwickTree<I>

fn from(array: [I; N]) -> Self

Converts to this type from the input type.

impl<I: PrimInt + WrappingAdd> FromIterator<I> for FenwickTree<I>

fn from_iter<T: IntoIterator<Item = I>>(iter: T) -> Self

Creates a value from an iterator.

impl<I> Index<usize> for FenwickTree<I>

type Output = I

The returned type after indexing.

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

Performs the indexing (container[index]) operation.

impl<'a, I: Copy> IntoIterator for &'a FenwickTree<I>

type Item = I

The type of the elements being iterated over.

type IntoIter = IntIter<'a, I>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<I> IntoIterator for FenwickTree<I>

type Item = I

The type of the elements being iterated over.

type IntoIter = IntoIter<I>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<I: PrimInt> PartialEq for FenwickTree<I>

fn eq(&self, other: &Self) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<I: PrimInt> Eq for FenwickTree<I>