Struct ftree::FenwickTree

pub struct FenwickTree<T> { /* private fields */ }

Implementations

impl<T> FenwickTree<T>

pub const fn new() -> Self

Creates an empty(useless) fenwick tree.

You might be looking for the method from_iter instead, which is the only way to create a useful fenwick tree.

pub fn is_empty(&self) -> bool

pub fn len(&self) -> usize

impl<T> FenwickTree<T>

pub fn prefix_sum(&self, index: usize, sum: T) -> Twhere T: Copy + AddAssign,

Computes the prefix sum up until the desired index.

The prefix sum up until the zeroth element is 0, since there is nothing before it.

The prefix sum up until an index larger than the length is undefined, since every element after the length - 1 is undefined, therefore it will panic.

Examples

use ftree::FenwickTree;

let lengths = [1, 6, 3, 9, 2];
let fenwick_array = FenwickTree::from_iter(lengths);

let cases: Vec<(usize, usize)> =
 vec![(0, 0), (1, 1), (2, 7), (3, 10), (4, 19), (5, 21)];

cases
  .into_iter()
  .for_each(|(idx, expected_sum)| assert_eq!(fenwick_array.prefix_sum(idx, 0), expected_sum))

pub fn add_at(&mut self, index: usize, diff: T)where T: Copy + AddAssign,

Increments a given index with a difference.

Examples

use ftree::FenwickTree;

let lengths = [1, 6, 3, 9, 2];
let mut fenwick_array = FenwickTree::from_iter(lengths);

let cases: Vec<(usize, usize)> = vec![(0, 0), (1, 2), (2, 8), (3, 11), (4, 20), (5, 22)];

fenwick_array.add_at(0, 1);

cases
  .into_iter()
  .for_each(|(idx, expected_sum)| assert_eq!(fenwick_array.prefix_sum(idx, 0), expected_sum))

pub fn sub_at(&mut self, index: usize, diff: T)where T: Copy + SubAssign,

Subtracts a difference from a given index.

Examples

use ftree::FenwickTree;

let lengths = [1, 6, 3, 9, 2];
let mut fenwick_array = FenwickTree::from_iter(lengths);

let cases: Vec<(usize, usize)> = vec![(0, 0), (1, 0), (2, 6), (3, 9), (4, 18), (5, 20)];

fenwick_array.sub_at(0, 1);

cases
  .into_iter()
  .for_each(|(idx, expected_sum)| assert_eq!(fenwick_array.prefix_sum(idx, 0), expected_sum))

pub fn index_of(&self, prefix_sum: T) -> usizewhere T: Copy + Ord + SubAssign,

Given a sum, finds the slot in which in which it would be “contained” within the original array.

Examples

use ftree::FenwickTree;

let lengths = [1, 6, 3, 9, 2];
let mut fenwick_array = FenwickTree::from_iter(lengths);

let cases: Vec<(usize, usize)> = vec![(0, 0), (6, 1), (9, 2), (18, 3), (20, 4)];

cases
  .into_iter()
  .for_each(|(prefix_sum, idx)| assert_eq!(fenwick_array.index_of(prefix_sum), idx))

Trait Implementations

impl<T: Clone> Clone for FenwickTree<T>

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

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T: Debug> Debug for FenwickTree<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<const N: usize> From<[usize; N]> for FenwickTree<usize>

fn from(value: [usize; N]) -> Self

Converts to this type from the input type.

impl<T> FromIterator<T> for FenwickTree<T>where T: Copy + AddAssign,

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

Creates a new fenwick tree.

Examples

use ftree::FenwickTree;

let lengths: [usize; 5] = [1, 6, 3, 9, 2];
// This is how lengths fenwick tree will look like internally
let fenwick_tree: Vec<usize> = vec![1, 7, 3, 19, 2];
// And this is how it can be constructed
let initialized_fenwick_tree = FenwickTree::from_iter(lengths);

impl<T: PartialEq> PartialEq<FenwickTree<T>> for FenwickTree<T>

fn eq(&self, other: &FenwickTree<T>) -> bool

This method tests for self and other values to be equal, and is used by ==.

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

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

impl<T> StructuralPartialEq for FenwickTree<T>