library_checker/data_structure/
point_add_range_sum.rs

1use competitive::prelude::*;
2#[doc(no_inline)]
3pub use competitive::{
4    algebra::AdditiveOperation,
5    data_structure::{BinaryIndexedTree, SegmentTree},
6};
7
8competitive::define_enum_scan! {
9    enum Query: usize {
10        0 => Add { p: usize, x: i64 }
11        1 => Sum { l: usize, r: usize }
12    }
13}
14
15#[verify::library_checker("point_add_range_sum")]
16pub fn point_add_range_sum_binary_indexed_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, a: [i64]);
20    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(n);
21    for (i, a) in a.take(n).enumerate() {
22        bit.update(i, a);
23    }
24    for _ in 0..q {
25        scan!(scanner, query: Query);
26        match query {
27            Query::Add { p, x } => {
28                bit.update(p, x);
29            }
30            Query::Sum { l, r } => {
31                writeln!(writer, "{}", bit.fold(l, r)).ok();
32            }
33        }
34    }
35}
36
37#[verify::library_checker("point_add_range_sum")]
38pub fn point_add_range_sum_segment_tree(reader: impl Read, mut writer: impl Write) {
39    let s = read_all_unchecked(reader);
40    let mut scanner = Scanner::new(&s);
41    scan!(scanner, n, q, a: [i64; n]);
42    let mut seg = SegmentTree::<AdditiveOperation<_>>::from_vec(a);
43    for _ in 0..q {
44        scan!(scanner, query: Query);
45        match query {
46            Query::Add { p, x } => {
47                seg.update(p, x);
48            }
49            Query::Sum { l, r } => {
50                writeln!(writer, "{}", seg.fold(l..r)).ok();
51            }
52        }
53    }
54}
library_checker/data_structure/point_add_range_sum.rs

library_checker/data_structure/
point_add_range_sum.rs
