Struct SumAugmentation 

pub struct SumAugmentation;

Augmentation that tracks the sum of all values in each subtree.

Useful for range-sum queries: after locating the range boundaries, access the subtree statistics to get aggregate sums.

The value type V must implement core::ops::Add, Copy, and provide a zero element via Default.

Examples

use augmented_rbtree::{AugmentedRBTree, augmentations::SumAugmentation};

let mut tree = AugmentedRBTree::<i32, i64, SumAugmentation>::new();
tree.insert(1, 10);
tree.insert(2, 20);
tree.insert(3, 30);

// Root stats holds the sum of all values
assert_eq!(tree.root_stats(), Some(&60));

Trait Implementations

impl<K, V> Augment<K, V> for SumAugmentation

where V: Add<Output = V> + Copy + Default,

type Stats = V

The type of data that will be stored in the augmented tree.

fn compute( _key: &K, value: &V, left: Option<(&K, &V, &V)>, right: Option<(&K, &V, &V)>, ) -> V

Computes the augmented data for a node given its key, value, and the augmented data of its left and right children.

impl Debug for SumAugmentation

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

Formats the value using the given formatter.