Struct bio::data_structures::bit_tree::FenwickTree
source · pub struct FenwickTree<T: Default + Ord, Op: PrefixOp<T>> { /* private fields */ }
Expand description
In a max bit tree or Fenwick Tree, get(i) will return the largest element e that has been added
to the bit tree with set(j, e), where j <= i. Initially all positions have
the value T::default(). Note that a set cannot be ‘undone’ by inserting
a smaller element at the same index.
Time Complexity: O(n) to build a new tree or O(log n) for get() and set() operations,
where n = tree.len()
.
Implementations§
Trait Implementations§
source§impl<T: Clone + Default + Ord, Op: Clone + PrefixOp<T>> Clone for FenwickTree<T, Op>
impl<T: Clone + Default + Ord, Op: Clone + PrefixOp<T>> Clone for FenwickTree<T, Op>
source§fn clone(&self) -> FenwickTree<T, Op>
fn clone(&self) -> FenwickTree<T, Op>
Returns a copy of the value. Read more
1.0.0 · source§fn clone_from(&mut self, source: &Self)
fn clone_from(&mut self, source: &Self)
Performs copy-assignment from
source
. Read moresource§impl<T: Default + Default + Ord, Op: Default + PrefixOp<T>> Default for FenwickTree<T, Op>
impl<T: Default + Default + Ord, Op: Default + PrefixOp<T>> Default for FenwickTree<T, Op>
source§fn default() -> FenwickTree<T, Op>
fn default() -> FenwickTree<T, Op>
Returns the “default value” for a type. Read more
source§impl<'de, T, Op: PrefixOp<T>> Deserialize<'de> for FenwickTree<T, Op>where
T: Deserialize<'de> + Default + Ord,
impl<'de, T, Op: PrefixOp<T>> Deserialize<'de> for FenwickTree<T, Op>where T: Deserialize<'de> + Default + Ord,
source§fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>where
__D: Deserializer<'de>,
fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>where __D: Deserializer<'de>,
Deserialize this value from the given Serde deserializer. Read more
source§impl<T: Ord + Default + Ord, Op: Ord + PrefixOp<T>> Ord for FenwickTree<T, Op>
impl<T: Ord + Default + Ord, Op: Ord + PrefixOp<T>> Ord for FenwickTree<T, Op>
source§fn cmp(&self, other: &FenwickTree<T, Op>) -> Ordering
fn cmp(&self, other: &FenwickTree<T, Op>) -> Ordering
1.21.0 · source§fn max(self, other: Self) -> Selfwhere
Self: Sized,
fn max(self, other: Self) -> Selfwhere Self: Sized,
Compares and returns the maximum of two values. Read more
source§impl<T: PartialEq + Default + Ord, Op: PartialEq + PrefixOp<T>> PartialEq<FenwickTree<T, Op>> for FenwickTree<T, Op>
impl<T: PartialEq + Default + Ord, Op: PartialEq + PrefixOp<T>> PartialEq<FenwickTree<T, Op>> for FenwickTree<T, Op>
source§fn eq(&self, other: &FenwickTree<T, Op>) -> bool
fn eq(&self, other: &FenwickTree<T, Op>) -> bool
This method tests for
self
and other
values to be equal, and is used
by ==
.source§impl<T: PartialOrd + Default + Ord, Op: PartialOrd + PrefixOp<T>> PartialOrd<FenwickTree<T, Op>> for FenwickTree<T, Op>
impl<T: PartialOrd + Default + Ord, Op: PartialOrd + PrefixOp<T>> PartialOrd<FenwickTree<T, Op>> for FenwickTree<T, Op>
source§fn partial_cmp(&self, other: &FenwickTree<T, Op>) -> Option<Ordering>
fn partial_cmp(&self, other: &FenwickTree<T, Op>) -> Option<Ordering>
1.0.0 · source§fn le(&self, other: &Rhs) -> bool
fn le(&self, other: &Rhs) -> bool
This method tests less than or equal to (for
self
and other
) and is used by the <=
operator. Read moreimpl<T: Eq + Default + Ord, Op: Eq + PrefixOp<T>> Eq for FenwickTree<T, Op>
impl<T: Default + Ord, Op: PrefixOp<T>> StructuralEq for FenwickTree<T, Op>
impl<T: Default + Ord, Op: PrefixOp<T>> StructuralPartialEq for FenwickTree<T, Op>
Auto Trait Implementations§
impl<T, Op> RefUnwindSafe for FenwickTree<T, Op>where Op: RefUnwindSafe, T: RefUnwindSafe,
impl<T, Op> Send for FenwickTree<T, Op>where Op: Send, T: Send,
impl<T, Op> Sync for FenwickTree<T, Op>where Op: Sync, T: Sync,
impl<T, Op> Unpin for FenwickTree<T, Op>where Op: Unpin, T: Unpin,
impl<T, Op> UnwindSafe for FenwickTree<T, Op>where Op: UnwindSafe, T: UnwindSafe,
Blanket Implementations§
source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere T: ?Sized,
source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
Mutably borrows from an owned value. Read more
source§impl<Q, K> Equivalent<K> for Qwhere
Q: Eq + ?Sized,
K: Borrow<Q> + ?Sized,
impl<Q, K> Equivalent<K> for Qwhere Q: Eq + ?Sized, K: Borrow<Q> + ?Sized,
source§fn equivalent(&self, key: &K) -> bool
fn equivalent(&self, key: &K) -> bool
Compare self to
key
and return true
if they are equal.§impl<SS, SP> SupersetOf<SS> for SPwhere
SS: SubsetOf<SP>,
impl<SS, SP> SupersetOf<SS> for SPwhere SS: SubsetOf<SP>,
§fn to_subset(&self) -> Option<SS>
fn to_subset(&self) -> Option<SS>
The inverse inclusion map: attempts to construct
self
from the equivalent element of its
superset. Read more§fn is_in_subset(&self) -> bool
fn is_in_subset(&self) -> bool
Checks if
self
is actually part of its subset T
(and can be converted to it).§fn to_subset_unchecked(&self) -> SS
fn to_subset_unchecked(&self) -> SS
Use with care! Same as
self.to_subset
but without any property checks. Always succeeds.§fn from_subset(element: &SS) -> SP
fn from_subset(element: &SS) -> SP
The inclusion map: converts
self
to the equivalent element of its superset.