library_checker/datastructure/
vertex_add_path_sum.rs

1use competitive::prelude::*;
2#[doc(no_inline)]
3pub use competitive::{
4    algebra::AdditiveOperation, data_structure::BinaryIndexedTree, graph::TreeGraphScanner,
5    tree::HeavyLightDecomposition,
6};
7
8#[verify::library_checker("vertex_add_path_sum")]
9pub fn vertex_add_path_sum(reader: impl Read, mut writer: impl Write) {
10    let s = read_all_unchecked(reader);
11    let mut scanner = Scanner::new(&s);
12    scan!(scanner, n, q, a: [i64; n], (mut graph, _): @TreeGraphScanner::<usize, ()>::new(n));
13    let hld = HeavyLightDecomposition::new(0, &mut graph);
14    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(n);
15    for (i, a) in a.iter().cloned().enumerate() {
16        bit.update(hld.vidx[i], a);
17    }
18    for _ in 0..q {
19        match scanner.scan::<usize>() {
20            0 => {
21                scan!(scanner, p, x: i64);
22                bit.update(hld.vidx[p], x);
23            }
24            1 => {
25                scan!(scanner, u, v);
26                writeln!(
27                    writer,
28                    "{}",
29                    hld.query::<AdditiveOperation<_>, _>(u, v, false, |l, r| bit.fold(l, r))
30                )
31                .ok();
32            }
33            _ => panic!("unknown query"),
34        }
35    }
36}