Struct FenwickTree 

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

Fenwick Tree (Binary Indexed Tree).

T is the numeric type stored in the tree. It must be Copy, Default (the additive identity, typically 0), and support += and -.

Implementations

impl<T> FenwickTree<T>

where T: Copy + Default + AddAssign + Sub<Output = T>,

pub fn new(nums: &[T]) -> Self

Build a Fenwick Tree from an initial slice of values.

Runs in O(n log n). For an O(n) build, build an empty tree and call Self::update for each element.

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

Add delta to the element at index.

Panics if index >= self.size.

pub fn pref(&self, index: usize) -> T

Compute the prefix sum of elements [0, index] (inclusive).

Panics if index >= self.size.

pub fn sum_range(&self, left: usize, right: usize) -> T

Compute the sum of elements in the half-open range [left, right].

Panics if right < left or right >= self.size.

Trait Implementations

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

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

Returns a duplicate 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.