Struct fenwick_tree::FenwickTree

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

Fenwick Tree (Binary Indexed Tree) http://hos.ac/slides/20140319_bit.pdf

Examples

use fenwick_tree::FenwickTree;
let mut ft = FenwickTree::new(5, 0);
ft.add(0, 1);
ft.add(2, 10);
ft.add(4, 100);
// [1, 0, 10, 0, 100]
assert_eq!(ft.sum(0..1), 1);
assert_eq!(ft.sum(0..2), 1);
assert_eq!(ft.sum(0..3), 11);
assert_eq!(ft.sum(2..4), 10);
assert_eq!(ft.sum(2..5), 110);
assert_eq!(ft.sum(0..5), 111);

Implementations

impl<T> FenwickTree<T>where T: Copy + AddAssign + SubAssign,

pub fn new(n: usize, e: T) -> Self

pub fn add(&mut self, k: usize, x: T)

pub fn sum(&self, range: impl RangeBounds<usize>) -> T

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.