Struct SubtreeSum 

struct SubtreeSum;

Implementations

impl SubtreeSum

fn apply(data: &mut SubtreeSumData, action: u64)

Examples found in repository

crates/library_checker/src/tree/dynamic_tree_subtree_add_subtree_sum.rs (line 66)

    fn top_down(data: &mut Self::Data, children: [Option<&mut Self::Data>; 2]) {
        let action = std::mem::replace(&mut data.lazy, 0);
        for child in children.into_iter().flatten() {
            Self::apply(child, action);
        }
    }

    fn bottom_up(data: &mut Self::Data, children: [Option<&Self::Data>; 2]) {
        data.sum = data.value
            + data.virtual_sum
            + children
                .into_iter()
                .flatten()
                .map(|child| child.sum)
                .sum::<u64>();
        data.size = 1
            + data.virtual_size
            + children
                .into_iter()
                .flatten()
                .map(|child| child.size)
                .sum::<u64>();
    }

    fn reverse(_data: &mut Self::Data) {}

    fn attach_virtual(parent: &mut Self::Data, child: &mut Self::Data) {
        child.path_parent_lazy = parent.virtual_lazy;
        parent.virtual_sum += child.sum;
        parent.virtual_size += child.size;
    }

    fn detach_virtual(parent: &mut Self::Data, child: &mut Self::Data) {
        Self::apply(child, parent.virtual_lazy - child.path_parent_lazy);
        parent.virtual_sum -= child.sum;
        parent.virtual_size -= child.size;
    }

    fn transfer_path_parent(old_root: &mut Self::Data, new_root: &mut Self::Data) {
        new_root.path_parent_lazy = std::mem::replace(&mut old_root.path_parent_lazy, 0);
    }
}

impl LinkCutTreeSubtreeFold for SubtreeSum {
    type Subtree = u64;

    fn fold_subtree(data: &Self::Data) -> Self::Subtree {
        data.sum
    }
}

impl LinkCutTreeSubtreeUpdate for SubtreeSum {
    type SubtreeAction = u64;

    fn update_subtree(data: &mut Self::Data, action: &Self::SubtreeAction) {
        Self::apply(data, *action);
    }

Trait Implementations

impl LinkCutTreeSpec for SubtreeSum

const ROOT_TO_NODE_TOP_DOWN: bool = false

Whether splay must propagate from the auxiliary root before rotations.

type Value = u64

type Data = SubtreeSumData

fn new(value: Self::Value) -> Self::Data

fn value(data: &Self::Data) -> &Self::Value

fn value_mut(data: &mut Self::Data) -> &mut Self::Value

fn top_down(data: &mut Self::Data, children: [Option<&mut Self::Data>; 2])

fn bottom_up(data: &mut Self::Data, children: [Option<&Self::Data>; 2])

fn reverse(_data: &mut Self::Data)

fn attach_virtual(parent: &mut Self::Data, child: &mut Self::Data)

fn detach_virtual(parent: &mut Self::Data, child: &mut Self::Data)

fn transfer_path_parent(old_root: &mut Self::Data, new_root: &mut Self::Data)

Moves state associated with the same path-parent edge after a splay.

const MODIFY_REQUIRES_ACCESS: bool = true

Whether modify must expose the node to update virtual subtree state.

impl LinkCutTreeSubtreeFold for SubtreeSum

type Subtree = u64

fn fold_subtree(data: &Self::Data) -> Self::Subtree

impl LinkCutTreeSubtreeUpdate for SubtreeSum

type SubtreeAction = u64

fn update_subtree(data: &mut Self::Data, action: &Self::SubtreeAction)