Struct HeavyLightPathFold 

pub struct HeavyLightPathFold<'a, M: Monoid> {
    tree: &'a HeavyLightDecomposition,
    nodes: Vec<PathFoldNode<M::T>>,
}

Fields

tree: &'a HeavyLightDecomposition

nodes: Vec<PathFoldNode<M::T>>

Implementations

impl<M: Monoid> HeavyLightPathFold<'_, M>

fn pull(&mut self, i: usize)

Examples found in repository

crates/competitive/src/tree/heavy_light_decomposition.rs (line 424)

    pub fn build_fold<M: Monoid>(&self, values: &[M::T]) -> HeavyLightPathFold<'_, M> {
        assert_eq!(values.len(), self.len());
        let mut fold = HeavyLightPathFold {
            tree: self,
            nodes: self
                .order
                .iter()
                .map(|&v| PathFoldNode {
                    parent: u32::MAX,
                    children: [u32::MAX; 2],
                    priority: 0,
                    value: values[v].clone(),
                    aggregate: [values[v].clone(), values[v].clone()],
                    prefix: [values[v].clone(), values[v].clone()],
                })
                .collect(),
        };
        let mut start = 0;
        let mut priorities = Vec::new();
        let mut stack = Vec::new();
        while start < self.len() {
            let mut end = start + 1;
            while end < self.len() && self.nodes[self.order[end]].head as usize == start {
                end += 1;
            }
            priorities.clear();
            let mut sum = 0usize;
            for i in start..end {
                let weight = self.subtree_size(self.order[i])
                    - if i + 1 < end {
                        self.subtree_size(self.order[i + 1])
                    } else {
                        0
                    };
                let priority = (sum ^ (sum + weight)).ilog2();
                sum += weight;
                fold.nodes[i].priority = priority;
                priorities.push(std::cmp::Reverse(priority));
            }
            let cartesian = CartesianTree::new(&priorities);
            for i in start..end {
                let parent = cartesian.parents[i - start];
                fold.nodes[i].parent = if parent == usize::MAX {
                    u32::MAX
                } else {
                    (parent + start) as u32
                };
                fold.nodes[i].children = cartesian.children[i - start].map(|v| {
                    if v == usize::MAX {
                        u32::MAX
                    } else {
                        (v + start) as u32
                    }
                });
            }
            stack.clear();
            stack.push(cartesian.root + start);
            let mut i = 0;
            while i < stack.len() {
                stack.extend(
                    fold.nodes[stack[i]]
                        .children
                        .into_iter()
                        .filter(|&v| v != u32::MAX)
                        .map(|v| v as usize),
                );
                i += 1;
            }
            for &i in stack.iter().rev() {
                fold.pull(i);
            }
            start = end;
        }
        fold
    }
}

impl<M: Monoid> HeavyLightPathFold<'_, M> {
    #[inline(always)]
    fn pull(&mut self, i: usize) {
        let [l, r] = self.nodes[i].children.map(|v| {
            if v == u32::MAX {
                usize::MAX
            } else {
                v as usize
            }
        });
        self.nodes[i].prefix = if l == usize::MAX {
            [self.nodes[i].value.clone(), self.nodes[i].value.clone()]
        } else {
            [
                M::operate(&self.nodes[l].aggregate[0], &self.nodes[i].value),
                M::operate(&self.nodes[i].value, &self.nodes[l].aggregate[1]),
            ]
        };
        self.nodes[i].aggregate = if r == usize::MAX {
            self.nodes[i].prefix.clone()
        } else {
            [
                M::operate(&self.nodes[i].prefix[0], &self.nodes[r].aggregate[0]),
                M::operate(&self.nodes[r].aggregate[1], &self.nodes[i].prefix[1]),
            ]
        };
    }

    pub fn set(&mut self, vertex: usize, value: M::T) {
        let mut i = self.tree.index(vertex);
        self.nodes[i].value = value;
        while i != usize::MAX {
            self.pull(i);
            i = if self.nodes[i].parent == u32::MAX {
                usize::MAX
            } else {
                self.nodes[i].parent as usize
            };
        }
    }

pub fn set(&mut self, vertex: usize, value: M::T)

Examples found in repository

crates/library_checker/src/tree/vertex_set_path_composite.rs (line 23)

pub fn vertex_set_path_composite(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, ab: [(M, M); n], (graph, _): @TreeGraphScanner::<usize, ()>::new(n));
    let hld = graph.hld(0);
    let mut fold = hld.build_fold::<LinearOperation<_>>(&ab);
    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::Set { p, cd } => {
                fold.set(p, cd);
            }
            Query::Apply { u, v, x } => {
                let (a, b) = fold.fold_vertices(u, v);
                pp!(a * x + b);
            }
        }
    }
}

fn fold_prefix<const REVERSE: bool>(&self, k: usize) -> M::T

Examples found in repository

crates/competitive/src/tree/heavy_light_decomposition.rs (line 537)

    pub fn fold_vertices(&self, mut u: usize, mut v: usize) -> M::T {
        let (mut left, mut right) = (M::unit(), M::unit());
        while self.tree.nodes[u].head != self.tree.nodes[v].head {
            if self.tree.index(u) > self.tree.index(v) {
                left = M::operate(&left, &self.fold_prefix::<true>(self.tree.index(u)));
                u = self.tree.nodes[u].parent as usize;
            } else {
                right = M::operate(&self.fold_prefix::<false>(self.tree.index(v)), &right);
                v = self.tree.nodes[v].parent as usize;
            }
        }
        let middle = if self.tree.index(u) > self.tree.index(v) {
            self.fold_range::<true>(self.tree.index(v), self.tree.index(u))
        } else {
            self.fold_range::<false>(self.tree.index(u), self.tree.index(v))
        };
        M::operate(&M::operate(&left, &middle), &right)
    }

fn fold_range<const REVERSE: bool>(&self, l: usize, r: usize) -> M::T

Examples found in repository

crates/competitive/src/tree/heavy_light_decomposition.rs (line 545)

    pub fn fold_vertices(&self, mut u: usize, mut v: usize) -> M::T {
        let (mut left, mut right) = (M::unit(), M::unit());
        while self.tree.nodes[u].head != self.tree.nodes[v].head {
            if self.tree.index(u) > self.tree.index(v) {
                left = M::operate(&left, &self.fold_prefix::<true>(self.tree.index(u)));
                u = self.tree.nodes[u].parent as usize;
            } else {
                right = M::operate(&self.fold_prefix::<false>(self.tree.index(v)), &right);
                v = self.tree.nodes[v].parent as usize;
            }
        }
        let middle = if self.tree.index(u) > self.tree.index(v) {
            self.fold_range::<true>(self.tree.index(v), self.tree.index(u))
        } else {
            self.fold_range::<false>(self.tree.index(u), self.tree.index(v))
        };
        M::operate(&M::operate(&left, &middle), &right)
    }

pub fn fold_vertices(&self, u: usize, v: usize) -> M::T

Folds the vertex values in u-to-v order.

Examples found in repository

crates/library_checker/src/tree/vertex_set_path_composite.rs (line 26)

pub fn vertex_set_path_composite(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, ab: [(M, M); n], (graph, _): @TreeGraphScanner::<usize, ()>::new(n));
    let hld = graph.hld(0);
    let mut fold = hld.build_fold::<LinearOperation<_>>(&ab);
    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::Set { p, cd } => {
                fold.set(p, cd);
            }
            Query::Apply { u, v, x } => {
                let (a, b) = fold.fold_vertices(u, v);
                pp!(a * x + b);
            }
        }
    }
}