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
This type corresponds to the type of the information to create the node with Node::initialize.
Required Methods
fn initialize(value: &Self::Value) -> Self
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.
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).