Struct competitive_programming_rs::data_structure::fenwick_tree::fenwick_tree::FenwickTree

pub struct FenwickTree<T, F> { /* fields omitted */ }

FenwickTree is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers. https://en.wikipedia.org/wiki/Fenwick_tree

Implementations

impl<T, F> FenwickTree<T, F> where
    T: Copy + AddAssign + Sub<Output = T>,
    F: Fn() -> T, 

pub fn new(size: usize, initialize: F) -> FenwickTree<T, F>

Constructs a new FenwickTree. The size of FenwickTree should be specified by size.

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

pub fn sum(&self, l: usize, r: usize) -> T

Returns a sum of range [l, r)

pub fn sum_one(&self, k: usize) -> T

Returns a sum of range [0, k)