library_checker/datastructure/
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
8#[verify::library_checker("point_add_range_sum")]
9pub fn point_add_range_sum_binary_indexed_tree(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]);
13    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(n);
14    for (i, a) in a.take(n).enumerate() {
15        bit.update(i, a);
16    }
17    for _ in 0..q {
18        match scanner.scan::<usize>() {
19            0 => {
20                scan!(scanner, p, x: i64);
21                bit.update(p, x);
22            }
23            1 => {
24                scan!(scanner, l, r);
25                writeln!(writer, "{}", bit.fold(l, r)).ok();
26            }
27            _ => panic!("unknown query"),
28        }
29    }
30}
31
32#[verify::library_checker("point_add_range_sum")]
33pub fn point_add_range_sum_segment_tree(reader: impl Read, mut writer: impl Write) {
34    let s = read_all_unchecked(reader);
35    let mut scanner = Scanner::new(&s);
36    scan!(scanner, n, q, a: [i64; n]);
37    let mut seg = SegmentTree::<AdditiveOperation<_>>::from_vec(a);
38    for _ in 0..q {
39        match scanner.scan::<usize>() {
40            0 => {
41                scan!(scanner, p, x: i64);
42                seg.update(p, x);
43            }
44            1 => {
45                scan!(scanner, l, r);
46                writeln!(writer, "{}", seg.fold(l..r)).ok();
47            }
48            _ => panic!("unknown query"),
49        }
50    }
51}
library_checker/datastructure/point_add_range_sum.rs

library_checker/datastructure/
point_add_range_sum.rs
