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

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 recreate all of the data in the node.

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