Trait seg_tree::nodes::Node

source · [−]

pub trait Node {
    type Value;

    fn initialize(value: &Self::Value) -> Self;
    fn combine(a: &Self, b: &Self) -> Self;
    fn value(&self) -> &Self::Value;
}

Expand description

Base trait required by nodes of segment trees. A type which implements this trait is essentially a “compressed” representation of a non-empty segment of values.

Required Associated Types

source

type Value

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

Required Methods

source

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

Function to create nodes from saved value, it is assumed that even if there’s more data saved in the node, value should have enough data to create all of the data of a node of a segment segment of exactly one element.

source

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

Function which will combine nodes a and b, where each corresponds to segments [i,j] and [j+1,k] respectively, into a node which corresponds to the segment [i,k]. This function must be associative (taking * as a symbol for combine, we have that a*(b*c)==(a*b)*c is true), but need not be commutative (it’s not necessarily true that a*b==b*a).

source