library_checker/data_structure/
point_add_range_sum.rs

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

library_checker/data_structure/
point_add_range_sum.rs
