Struct seg_tree::utils::Sum

pub struct Sum<T> where
    T: Add<Output = T> + Clone,  { /* private fields */ }

Implementation of range sum for generic type T, it implements Node and LazyNode, as such it can be used as a node in every segment tree type.

Trait Implementations

impl<T: Clone> Clone for Sum<T> where
    T: Add<Output = T> + Clone, 

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

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug> Debug for Sum<T> where
    T: Add<Output = T> + Clone, 

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T> LazyNode for Sum<T> where
    T: Add<Output = T> + Mul<usize, Output = T> + Clone, 

Implementation for sum range query node, the update adds the value to each item in the range. It assumes that a*n, where a: T and n: usize is well defined and a*n = a+...+a with ‘n’ a. For non-commutative operations, two things will be true lazy_value = lazy_value + new_value.

fn lazy_update(&mut self, i: usize, j: usize)

The following invariant must be met while implementing this method, if lazy_value is called immediately after this function then it must return None. (See Option::take)

fn update_lazy_value(&mut self, new_value: &<Self as Node>::Value)

The following invariant must be met while implementing this method, if lazy_value is called immediately after this function then it must return Some(&value).

fn lazy_value(&self) -> Option<&<Self as Node>::Value>

Must return a reference to the current lazy value only if it exists.

impl<T> Node for Sum<T> where
    T: Add<Output = T> + Clone, 

fn initialize(v: &Self::Value) -> Self

The node is initialized with the value given.

fn combine(a: &Self, b: &Self) -> Self

As this is a range sum node, the operation which is used to ‘merge’ two nodes is +.

type Value = T

This type corresponds to the type of the information to create the node with Node::initialize.

fn value(&self) -> &Self::Value

Method which returns a reference to the current saved value.