Struct fenwick_tree::FenwickTree [−][src]
Expand description
An implementation of the binary indexed tree (Fenwick tree) data structure.
The tree is backed by a simple vec of the fixed size where each item is responsible for storing cumulative sum of some range, allowing to perform queries and updates in O(log n) time.
Implementations
impl<I> FenwickTree<I> where
I: Default + Copy + AddAssign + SubAssign,
[src]
impl<I> FenwickTree<I> where
I: Default + Copy + AddAssign + SubAssign,
[src]pub fn with_len(len: usize) -> Self
[src]
pub fn with_len(len: usize) -> Self
[src]Constructs a new Fenwick tree with the specified len
with each element set as
I::default()
.
The vector is initialized with vec![I::default(); len]
.
Panics
Vector initialization may panic if len
is too big.
pub fn sum(&self, bounds: impl RangeBounds<usize>) -> Result<I, SumError>
[src]
pub fn sum(&self, bounds: impl RangeBounds<usize>) -> Result<I, SumError>
[src]A partial sum of the specified bounds
.
Complexity: O(log n).
Note that sum
for empty range (a range (i..j)
where i >= j
) is 0
.
Also, bounds
are converted into a pair (start, end)
that represents [start, end)
range. This means that boundary case tree.sum(i..=usize::MAX)
fallbacks to tree.sum(0..usize::MAX)
.
However, in practice, it’s not possible to construct such a big tree (Vec
panics with
capacity overflow
).
Auto Trait Implementations
impl<I> RefUnwindSafe for FenwickTree<I> where
I: RefUnwindSafe,
I: RefUnwindSafe,
impl<I> Send for FenwickTree<I> where
I: Send,
I: Send,
impl<I> Sync for FenwickTree<I> where
I: Sync,
I: Sync,
impl<I> Unpin for FenwickTree<I> where
I: Unpin,
I: Unpin,
impl<I> UnwindSafe for FenwickTree<I> where
I: UnwindSafe,
I: UnwindSafe,