Struct XorLinkedRootedTreeScanner 

pub struct XorLinkedRootedTreeScanner<U, T = (), P = NoParent, D = NoDfsPreorder, H = NoDepth, PE = NoParentEdge, EC = NoEdgeChild, X = NoXorBottomUpOrder, B = NoXorBottomUpOrder, E = NoEIndexed>
where
    U: Scan<Output = usize>,
    T: Scan,
{
    n: usize,
    root: usize,
    _marker: PhantomData<fn() -> ((U, T), (P, D, H), (PE, EC), (X, B, E))>,
}

Fields

n: usize

root: usize

_marker: PhantomData<fn() -> ((U, T), (P, D, H), (PE, EC), (X, B, E))>

Implementations

impl<U, T> XorLinkedRootedTreeScanner<U, T>

where U: Scan<Output = usize>, T: Scan,

pub fn new(n: usize, root: usize) -> Self

Examples found in repository

crates/library_checker/src/tree/vertex_add_path_sum.rs (line 19)

pub fn vertex_add_path_sum(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, mut a: [i64; n],
        (tree, _): @XorLinkedRootedTreeScanner::<usize, ()>::new(n, 0)
            .with_parent().with_dfs_preorder());
    let lca = LowestCommonAncestor::from_dfs_preorder(tree.parents(), tree.dfs_order());
    let mut values = vec![0; n + 1];
    for (u, &x) in a.iter().enumerate() {
        let range = tree.subtree_range(u);
        values[range.start] += x;
        values[range.end] -= x;
    }
    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::from_slice(&values);
    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::Add { p, x } => {
                a[p] += x;
                let range = tree.subtree_range(p);
                bit.update(range.start, x);
                bit.update(range.end, -x);
            }
            Query::Sum { u, v } => {
                let p = lca.lca(u, v);
                pp!(
                    a[p] + bit.accumulate(tree.dfs_index(u)) + bit.accumulate(tree.dfs_index(v))
                        - 2 * bit.accumulate(tree.dfs_index(p))
                );
            }
        }
    }
}

impl<U, T, P, D, H, PE, EC, X, B, E> XorLinkedRootedTreeScanner<U, T, P, D, H, PE, EC, X, B, E>

where U: Scan<Output = usize>, T: Scan,

pub fn with_parent( self, ) -> XorLinkedRootedTreeScanner<U, T, RecordParent, D, H, PE, EC, X, B, E>

Examples found in repository

crates/library_checker/src/tree/vertex_add_path_sum.rs (line 20)

pub fn vertex_add_path_sum(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, mut a: [i64; n],
        (tree, _): @XorLinkedRootedTreeScanner::<usize, ()>::new(n, 0)
            .with_parent().with_dfs_preorder());
    let lca = LowestCommonAncestor::from_dfs_preorder(tree.parents(), tree.dfs_order());
    let mut values = vec![0; n + 1];
    for (u, &x) in a.iter().enumerate() {
        let range = tree.subtree_range(u);
        values[range.start] += x;
        values[range.end] -= x;
    }
    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::from_slice(&values);
    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::Add { p, x } => {
                a[p] += x;
                let range = tree.subtree_range(p);
                bit.update(range.start, x);
                bit.update(range.end, -x);
            }
            Query::Sum { u, v } => {
                let p = lca.lca(u, v);
                pp!(
                    a[p] + bit.accumulate(tree.dfs_index(u)) + bit.accumulate(tree.dfs_index(v))
                        - 2 * bit.accumulate(tree.dfs_index(p))
                );
            }
        }
    }
}

pub fn with_dfs_preorder( self, ) -> XorLinkedRootedTreeScanner<U, T, P, RecordDfsPreorder, H, PE, EC, X, RecordXorBottomUpOrder, E>

Examples found in repository

crates/library_checker/src/tree/vertex_add_path_sum.rs (line 20)

pub fn vertex_add_path_sum(reader: impl Read, writer: impl Write) {
    prepare_io!(reader, writer);
    sc!(n, q, mut a: [i64; n],
        (tree, _): @XorLinkedRootedTreeScanner::<usize, ()>::new(n, 0)
            .with_parent().with_dfs_preorder());
    let lca = LowestCommonAncestor::from_dfs_preorder(tree.parents(), tree.dfs_order());
    let mut values = vec![0; n + 1];
    for (u, &x) in a.iter().enumerate() {
        let range = tree.subtree_range(u);
        values[range.start] += x;
        values[range.end] -= x;
    }
    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::from_slice(&values);
    for _ in 0..q {
        sc!(query: Query);
        match query {
            Query::Add { p, x } => {
                a[p] += x;
                let range = tree.subtree_range(p);
                bit.update(range.start, x);
                bit.update(range.end, -x);
            }
            Query::Sum { u, v } => {
                let p = lca.lca(u, v);
                pp!(
                    a[p] + bit.accumulate(tree.dfs_index(u)) + bit.accumulate(tree.dfs_index(v))
                        - 2 * bit.accumulate(tree.dfs_index(p))
                );
            }
        }
    }
}

pub fn with_depth( self, ) -> XorLinkedRootedTreeScanner<U, T, P, D, RecordDepth, PE, EC, X, RecordXorBottomUpOrder, E>

pub fn with_xor_bottom_up_order( self, ) -> XorLinkedRootedTreeScanner<U, T, P, D, H, PE, EC, RecordXorBottomUpOrder, RecordXorBottomUpOrder, E>

impl<U, T, P, D, H, X, B> XorLinkedRootedTreeScanner<U, T, P, D, H, NoParentEdge, NoEdgeChild, X, B, NoEIndexed>

where U: Scan<Output = usize>, T: Scan,

pub fn with_eindexed( self, ) -> XorLinkedRootedTreeScanner<U, T, P, D, H, NoParentEdge, NoEdgeChild, X, B, EIndexed>

impl<U, T, P, D, H, PE, EC, X, B> XorLinkedRootedTreeScanner<U, T, P, D, H, PE, EC, X, B, EIndexed>

where U: Scan<Output = usize>, T: Scan,

pub fn with_parent_edge( self, ) -> XorLinkedRootedTreeScanner<U, T, P, D, H, RecordParentEdge, EC, X, B, EIndexed>

pub fn with_edge_child( self, ) -> XorLinkedRootedTreeScanner<U, T, P, D, H, PE, RecordEdgeChild, X, B, EIndexed>

Trait Implementations

impl<U, T, P, D, H, X, B> MarkedScan for XorLinkedRootedTreeScanner<U, T, P, D, H, NoParentEdge, NoEdgeChild, X, B, NoEIndexed>

where U: Scan<Output = usize>, T: Scan, P: ParentComponent, D: DfsPreorderComponent, H: DepthComponent, X: BuildXorBottomUpOrder<B>, B: XorBottomUpOrderBuffer,

type Output = (XorLinkedRootedTree<P, D, H, NoParentEdge, NoEdgeChild, X>, Vec<<T as Scan>::Output>)

fn mscan<I: ScanSource>(self, iter: &mut I) -> Option<Self::Output>

impl<U, T, P, D, H, PE, EC, X, B> MarkedScan for XorLinkedRootedTreeScanner<U, T, P, D, H, PE, EC, X, B, EIndexed>

where U: Scan<Output = usize>, T: Scan, P: ParentComponent, D: DfsPreorderComponent, H: DepthComponent, PE: ParentEdgeComponent, EC: EdgeChildComponent, X: BuildXorBottomUpOrder<B>, B: XorBottomUpOrderBuffer,

type Output = (XorLinkedRootedTree<P, D, H, PE, EC, X>, Vec<<T as Scan>::Output>)

fn mscan<I: ScanSource>(self, iter: &mut I) -> Option<Self::Output>