library_checker/tree/
vertex_add_range_contour_sum_on_tree.rs

1use competitive::prelude::*;
2#[doc(no_inline)]
3pub use competitive::{
4    algebra::AdditiveOperation, data_structure::BinaryIndexedTree, graph::TreeGraphScanner,
5    tree::ContourQueryRange,
6};
7
8competitive::define_enum_scan! {
9    enum Query: usize {
10        0 => Add { p: usize, x: i64 }
11        1 => Sum { v: usize, l: usize, r: usize }
12    }
13}
14
15#[verify::library_checker("vertex_add_range_contour_sum_on_tree")]
16pub fn vertex_add_range_contour_sum_on_tree(reader: impl Read, mut writer: impl Write) {
17    let s = read_all_unchecked(reader);
18    let mut scanner = Scanner::new(&s);
19    scan!(scanner, n, q, mut a: [i64; n], (graph, _): @TreeGraphScanner::<usize, ()>::new(n));
20    let cq = graph.contour_query_range();
21    let mut raw = vec![0; cq.len()];
22    for (v, &x) in a.iter().enumerate() {
23        cq.for_each_index(v, |i| raw[i] += x);
24    }
25    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::from_slice(&raw);
26    for _ in 0..q {
27        scan!(scanner, query: Query);
28        match query {
29            Query::Add { p, x } => {
30                a[p] += x;
31                cq.for_each_index(p, |i| bit.update(i, x));
32            }
33            Query::Sum { v, l, r } => {
34                let mut ans = if l == 0 && 0 < r { a[v] } else { 0 };
35                cq.for_each_contour_range(v, l, r, |start, end| {
36                    ans += bit.fold(start, end);
37                });
38                writeln!(writer, "{ans}").ok();
39            }
40        }
41    }
42}

library_checker/tree/vertex_add_range_contour_sum_on_tree.rs

library_checker/tree/
vertex_add_range_contour_sum_on_tree.rs