Skip to main content

BinaryIndexedTree

competitive::data_structure

Struct BinaryIndexedTree 

Source 
pub struct BinaryIndexedTree<M>
where
    M: Monoid,
{
    n: usize,
    bit: Vec<M::T>,
}

Fields§

§n: usize§bit: Vec<M::T>

Implementations§

Source§

impl<M> BinaryIndexedTree<M>
where M: Monoid,

Source

pub fn new(n: usize) -> Self

Examples found in repository?
crates/competitive/src/data_structure/range_frequency.rs (line 240)
238    fn new(size: usize) -> Self {
239        Self {
240            bit: BinaryIndexedTree::new(size.div_ceil(64)),
241            data: vec![0; size.div_ceil(64)],
242        }
243    }
More examples
Hide additional examples
crates/library_checker/src/data_structure/point_add_range_sum.rs (line 18)
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}
crates/aizu_online_judge/src/grl/grl_5_d.rs (line 24)
15pub fn grl_5_d(reader: impl Read, writer: impl Write) {
16    prepare_io!(reader, writer);
17    sc!(n, c: [SizedCollect<usize>; iter n]);
18    let edges = c
19        .enumerate()
20        .flat_map(|(u, it)| it.into_iter().map(move |v| (u, v)))
21        .collect();
22    let graph = UndirectedSparseGraph::from_edges(n, edges);
23    let et = graph.path_euler_tour_builder(0).build();
24    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(et.size);
25
26    sc!(q);
27    for _ in 0..q {
28        sc!(query: Query);
29        match query {
30            Query::Add { v, w } => {
31                et.update(v, w, -w, |k, x| bit.update(k, x));
32            }
33            Query::Get { u } => {
34                let ans = et.fold(u, |k| bit.accumulate(k));
35                pp!(ans);
36            }
37        }
38    }
39}
crates/library_checker/src/tree/vertex_get_range_contour_add_on_tree.rs (line 20)
14pub fn vertex_get_range_contour_add_on_tree(reader: impl Read, writer: impl Write) {
15    prepare_io!(reader, writer);
16    sc!(n, q, mut a: [i64; n], (graph, _): @TreeGraphScanner::<usize, ()>::new(n));
17    let cq = graph.contour_query_range();
18    let mut bits: Vec<BinaryIndexedTree<AdditiveOperation<_>>> = cq
19        .component_sizes()
20        .map(|n| BinaryIndexedTree::new(n + 1))
21        .collect();
22
23    for _ in 0..q {
24        sc!(query: Query);
25        match query {
26            Query::Add { v, l, r, x } => {
27                cq.for_each_contour_range(v, l, r, |c, start, end| {
28                    bits[c].update(start, x);
29                    bits[c].update(end, -x);
30                });
31                if l == 0 && 0 < r {
32                    a[v] += x;
33                }
34            }
35            Query::Get { v } => {
36                let mut ans = a[v];
37                cq.for_each_index(v, |c, i| ans += bits[c].accumulate(i));
38                pp!(ans);
39            }
40        }
41    }
42}
crates/competitive/src/data_structure/range_fold_with_upper_bound.rs (line 51)
34    pub fn execute(self) -> Vec<M::T> {
35        let mut values: Vec<_> = self
36            .keys
37            .iter()
38            .copied()
39            .enumerate()
40            .map(|(index, key)| (key, index))
41            .collect();
42        values.radix_sort_by_key(|&(key, _)| key);
43        let mut order: Vec<_> = self
44            .queries
45            .iter()
46            .enumerate()
47            .map(|(index, (_, upper_bound))| (*upper_bound, index))
48            .collect();
49        order.radix_sort_by_key(|&(upper_bound, _)| upper_bound);
50
51        let mut bit: BinaryIndexedTree<M> = BinaryIndexedTree::new(values.len());
52        let mut answers = vec![M::unit(); self.queries.len()];
53        let mut inserted = 0;
54        for (upper_bound, index) in order {
55            while inserted < values.len() && values[inserted].0 <= upper_bound {
56                let position = values[inserted].1;
57                bit.update(position, self.weights[position].clone());
58                inserted += 1;
59            }
60            let range = &self.queries[index].0;
61            answers[index] = bit.fold(range.start, range.end);
62        }
63        answers
64    }
crates/library_checker/src/data_structure/static_rectangle_add_rectangle_sum.rs (line 51)
10pub fn static_rectangle_add_rectangle_sum(reader: impl Read, writer: impl Write) {
11    prepare_io!(buffered; reader, writer);
12    sc!(n, q, rectangles: [(u32, u32, u32, u32, M); n], queries: [(u32, u32, u32, u32); q]);
13    let mut ys: Vec<_> = rectangles
14        .iter()
15        .flat_map(|&(_, d, _, u, _)| [d, u])
16        .collect();
17    ys.radix_sort_by_key(|&y| y);
18    ys.dedup();
19    let search = StaticSearch::from_sorted(&ys);
20    let endpoints: Vec<_> = rectangles
21        .iter()
22        .flat_map(|&(_, d, _, u, _)| [d, u])
23        .chain(queries.iter().flat_map(|&(_, d, _, u)| [d, u]))
24        .collect();
25    let mut positions = vec![0; endpoints.len()];
26    search.lower_bound_batch(&endpoints, &mut positions);
27    let mut points: Vec<_> = rectangles
28        .into_iter()
29        .zip(positions[..2 * n].as_chunks().0)
30        .flat_map(|((l, _, r, _, w), &[d, u])| {
31            let d = d as u32;
32            let u = u as u32;
33            [(l, d, w), (l, u, -w), (r, d, -w), (r, u, w)]
34        })
35        .collect();
36    points.radix_sort_by_key(|&(x, ..)| x);
37    let mut events: Vec<_> = queries
38        .into_iter()
39        .zip(positions[2 * n..].as_chunks().0)
40        .enumerate()
41        .flat_map(|(i, ((l, d, r, u), &[di, ui]))| {
42            let di = di as u32;
43            let ui = ui as u32;
44            [
45                (l, d, u, di, ui, i as u32, false),
46                (r, d, u, di, ui, i as u32, true),
47            ]
48        })
49        .collect();
50    events.radix_sort_by_key(|&(x, ..)| x);
51    let mut bit = BinaryIndexedTree::<ArrayOperation<AdditiveOperation<M>, 4>>::new(ys.len());
52    let mut points = points.into_iter().peekable();
53    let mut ans = vec![M::zero(); q];
54    for (x, d, u, di, ui, i, add) in events {
55        while points.peek().is_some_and(|&(px, ..)| px < x) {
56            let (px, py, w) = points.next().unwrap();
57            let wx = w * M::from(px);
58            let wy = w * M::from(ys[py as usize]);
59            bit.update(py as usize, [w, wx, wy, wx * M::from(ys[py as usize])]);
60        }
61        for (y, yi, add) in [(d, di, !add), (u, ui, add)] {
62            let [w, wx, wy, wxy] = bit.accumulate0(yi as usize);
63            let value = (w * M::from(x) - wx) * M::from(y) - wy * M::from(x) + wxy;
64            if add {
65                ans[i as usize] += value;
66            } else {
67                ans[i as usize] -= value;
68            }
69        }
70    }
71    pp!(@lf @it ans);
72}
Source

pub fn from_slice(slice: &[M::T]) -> Self

Examples found in repository?
crates/competitive/src/data_structure/wavelet_matrix.rs (line 1465)
1456    pub fn build_point_add<M>(&self, weights: &[M::T]) -> WaveletMatrixPointAdd<'_, T, M>
1457    where
1458        M: AbelianGroup,
1459    {
1460        assert_eq!(weights.len(), self.len);
1461        let mut current = weights.to_vec();
1462        let mut bits = Vec::with_capacity(self.bit_length);
1463        for level in 0..self.bit_length {
1464            current = self.reorder(level, current);
1465            bits.push(BinaryIndexedTree::from_slice(&current[..self.zeros[level]]));
1466        }
1467        WaveletMatrixPointAdd {
1468            wavelet_matrix: self,
1469            bits,
1470        }
1471    }
More examples
Hide additional examples
crates/library_checker/src/tree/vertex_add_range_contour_sum_on_tree.rs (line 24)
14pub fn vertex_add_range_contour_sum_on_tree(reader: impl Read, writer: impl Write) {
15    prepare_io!(reader, writer);
16    sc!(n, q, mut a: [i64; n], (graph, _): @TreeGraphScanner::<usize, ()>::new(n));
17    let cq = graph.contour_query_range();
18    let mut raw: Vec<_> = cq.component_sizes().map(|n| vec![0; n]).collect();
19    for (v, &x) in a.iter().enumerate() {
20        cq.for_each_index(v, |c, i| raw[c][i] += x);
21    }
22    let mut bits: Vec<BinaryIndexedTree<AdditiveOperation<_>>> = raw
23        .into_iter()
24        .map(|values| BinaryIndexedTree::from_slice(&values))
25        .collect();
26    for _ in 0..q {
27        sc!(query: Query);
28        match query {
29            Query::Add { p, x } => {
30                a[p] += x;
31                cq.for_each_index(p, |c, i| bits[c].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, |c, start, end| {
36                    ans += bits[c].fold_abelian(start, end);
37                });
38                pp!(ans);
39            }
40        }
41    }
42}
crates/library_checker/src/tree/vertex_add_path_sum.rs (line 28)
16pub fn vertex_add_path_sum(reader: impl Read, writer: impl Write) {
17    prepare_io!(reader, writer);
18    sc!(n, q, mut a: [i64; n],
19        (tree, _): @XorLinkedRootedTreeScanner::<usize, ()>::new(n, 0)
20            .with_parent().with_dfs_preorder());
21    let lca = LowestCommonAncestor::from_dfs_preorder(tree.parents(), tree.dfs_order());
22    let mut values = vec![0; n + 1];
23    for (u, &x) in a.iter().enumerate() {
24        let range = tree.subtree_range(u);
25        values[range.start] += x;
26        values[range.end] -= x;
27    }
28    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::from_slice(&values);
29    for _ in 0..q {
30        sc!(query: Query);
31        match query {
32            Query::Add { p, x } => {
33                a[p] += x;
34                let range = tree.subtree_range(p);
35                bit.update(range.start, x);
36                bit.update(range.end, -x);
37            }
38            Query::Sum { u, v } => {
39                let p = lca.lca(u, v);
40                pp!(
41                    a[p] + bit.accumulate(tree.dfs_index(u)) + bit.accumulate(tree.dfs_index(v))
42                        - 2 * bit.accumulate(tree.dfs_index(p))
43                );
44            }
45        }
46    }
47}
Source

pub fn accumulate0(&self, k: usize) -> M::T

fold [0, k)

Examples found in repository?
crates/competitive/src/data_structure/binary_indexed_tree.rs (line 73)
72    pub fn accumulate(&self, k: usize) -> M::T {
73        self.accumulate0(k + 1)
74    }
75    #[inline]
76    pub fn update(&mut self, k: usize, x: M::T) {
77        debug_assert!(k < self.n);
78        let mut k = k + 1;
79        while k <= self.n {
80            self.bit[k] = M::operate(&self.bit[k], &x);
81            k += k & (!k + 1);
82        }
83    }
84    #[inline]
85    pub fn partition_point_acc<P>(&self, mut pred: P) -> usize
86    where
87        P: FnMut(&M::T) -> bool,
88    {
89        let n = self.n;
90        let mut acc = M::unit();
91        let mut pos = 0;
92        let mut k = n.next_power_of_two();
93        while k > 0 {
94            if k + pos <= n {
95                let nacc = M::operate(&acc, &self.bit[k + pos]);
96                if pred(&nacc) {
97                    pos += k;
98                    acc = nacc;
99                }
100            }
101            k >>= 1;
102        }
103        pos
104    }
105}
106
107impl<G: Group> BinaryIndexedTree<G> {
108    #[inline]
109    pub fn fold(&self, l: usize, r: usize) -> G::T {
110        debug_assert!(l <= self.n && r <= self.n);
111        G::operate(&G::inverse(&self.accumulate0(l)), &self.accumulate0(r))
112    }
More examples
Hide additional examples
crates/library_checker/src/data_structure/static_rectangle_add_rectangle_sum.rs (line 62)
10pub fn static_rectangle_add_rectangle_sum(reader: impl Read, writer: impl Write) {
11    prepare_io!(buffered; reader, writer);
12    sc!(n, q, rectangles: [(u32, u32, u32, u32, M); n], queries: [(u32, u32, u32, u32); q]);
13    let mut ys: Vec<_> = rectangles
14        .iter()
15        .flat_map(|&(_, d, _, u, _)| [d, u])
16        .collect();
17    ys.radix_sort_by_key(|&y| y);
18    ys.dedup();
19    let search = StaticSearch::from_sorted(&ys);
20    let endpoints: Vec<_> = rectangles
21        .iter()
22        .flat_map(|&(_, d, _, u, _)| [d, u])
23        .chain(queries.iter().flat_map(|&(_, d, _, u)| [d, u]))
24        .collect();
25    let mut positions = vec![0; endpoints.len()];
26    search.lower_bound_batch(&endpoints, &mut positions);
27    let mut points: Vec<_> = rectangles
28        .into_iter()
29        .zip(positions[..2 * n].as_chunks().0)
30        .flat_map(|((l, _, r, _, w), &[d, u])| {
31            let d = d as u32;
32            let u = u as u32;
33            [(l, d, w), (l, u, -w), (r, d, -w), (r, u, w)]
34        })
35        .collect();
36    points.radix_sort_by_key(|&(x, ..)| x);
37    let mut events: Vec<_> = queries
38        .into_iter()
39        .zip(positions[2 * n..].as_chunks().0)
40        .enumerate()
41        .flat_map(|(i, ((l, d, r, u), &[di, ui]))| {
42            let di = di as u32;
43            let ui = ui as u32;
44            [
45                (l, d, u, di, ui, i as u32, false),
46                (r, d, u, di, ui, i as u32, true),
47            ]
48        })
49        .collect();
50    events.radix_sort_by_key(|&(x, ..)| x);
51    let mut bit = BinaryIndexedTree::<ArrayOperation<AdditiveOperation<M>, 4>>::new(ys.len());
52    let mut points = points.into_iter().peekable();
53    let mut ans = vec![M::zero(); q];
54    for (x, d, u, di, ui, i, add) in events {
55        while points.peek().is_some_and(|&(px, ..)| px < x) {
56            let (px, py, w) = points.next().unwrap();
57            let wx = w * M::from(px);
58            let wy = w * M::from(ys[py as usize]);
59            bit.update(py as usize, [w, wx, wy, wx * M::from(ys[py as usize])]);
60        }
61        for (y, yi, add) in [(d, di, !add), (u, ui, add)] {
62            let [w, wx, wy, wxy] = bit.accumulate0(yi as usize);
63            let value = (w * M::from(x) - wx) * M::from(y) - wy * M::from(x) + wxy;
64            if add {
65                ans[i as usize] += value;
66            } else {
67                ans[i as usize] -= value;
68            }
69        }
70    }
71    pp!(@lf @it ans);
72}
Source

pub fn accumulate(&self, k: usize) -> M::T

fold [0, k]

Examples found in repository?
crates/aizu_online_judge/src/grl/grl_5_d.rs (line 34)
15pub fn grl_5_d(reader: impl Read, writer: impl Write) {
16    prepare_io!(reader, writer);
17    sc!(n, c: [SizedCollect<usize>; iter n]);
18    let edges = c
19        .enumerate()
20        .flat_map(|(u, it)| it.into_iter().map(move |v| (u, v)))
21        .collect();
22    let graph = UndirectedSparseGraph::from_edges(n, edges);
23    let et = graph.path_euler_tour_builder(0).build();
24    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(et.size);
25
26    sc!(q);
27    for _ in 0..q {
28        sc!(query: Query);
29        match query {
30            Query::Add { v, w } => {
31                et.update(v, w, -w, |k, x| bit.update(k, x));
32            }
33            Query::Get { u } => {
34                let ans = et.fold(u, |k| bit.accumulate(k));
35                pp!(ans);
36            }
37        }
38    }
39}
More examples
Hide additional examples
crates/library_checker/src/tree/vertex_get_range_contour_add_on_tree.rs (line 37)
14pub fn vertex_get_range_contour_add_on_tree(reader: impl Read, writer: impl Write) {
15    prepare_io!(reader, writer);
16    sc!(n, q, mut a: [i64; n], (graph, _): @TreeGraphScanner::<usize, ()>::new(n));
17    let cq = graph.contour_query_range();
18    let mut bits: Vec<BinaryIndexedTree<AdditiveOperation<_>>> = cq
19        .component_sizes()
20        .map(|n| BinaryIndexedTree::new(n + 1))
21        .collect();
22
23    for _ in 0..q {
24        sc!(query: Query);
25        match query {
26            Query::Add { v, l, r, x } => {
27                cq.for_each_contour_range(v, l, r, |c, start, end| {
28                    bits[c].update(start, x);
29                    bits[c].update(end, -x);
30                });
31                if l == 0 && 0 < r {
32                    a[v] += x;
33                }
34            }
35            Query::Get { v } => {
36                let mut ans = a[v];
37                cq.for_each_index(v, |c, i| ans += bits[c].accumulate(i));
38                pp!(ans);
39            }
40        }
41    }
42}
crates/library_checker/src/tree/vertex_add_path_sum.rs (line 41)
16pub fn vertex_add_path_sum(reader: impl Read, writer: impl Write) {
17    prepare_io!(reader, writer);
18    sc!(n, q, mut a: [i64; n],
19        (tree, _): @XorLinkedRootedTreeScanner::<usize, ()>::new(n, 0)
20            .with_parent().with_dfs_preorder());
21    let lca = LowestCommonAncestor::from_dfs_preorder(tree.parents(), tree.dfs_order());
22    let mut values = vec![0; n + 1];
23    for (u, &x) in a.iter().enumerate() {
24        let range = tree.subtree_range(u);
25        values[range.start] += x;
26        values[range.end] -= x;
27    }
28    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::from_slice(&values);
29    for _ in 0..q {
30        sc!(query: Query);
31        match query {
32            Query::Add { p, x } => {
33                a[p] += x;
34                let range = tree.subtree_range(p);
35                bit.update(range.start, x);
36                bit.update(range.end, -x);
37            }
38            Query::Sum { u, v } => {
39                let p = lca.lca(u, v);
40                pp!(
41                    a[p] + bit.accumulate(tree.dfs_index(u)) + bit.accumulate(tree.dfs_index(v))
42                        - 2 * bit.accumulate(tree.dfs_index(p))
43                );
44            }
45        }
46    }
47}
Source

pub fn update(&mut self, k: usize, x: M::T)

Examples found in repository?
crates/competitive/src/data_structure/binary_indexed_tree.rs (line 142)
141    pub fn set(&mut self, k: usize, x: G::T) {
142        self.update(k, G::operate(&G::inverse(&self.get(k)), &x));
143    }
More examples
Hide additional examples
crates/competitive/src/data_structure/range_frequency.rs (line 250)
245    fn add(&mut self, index: u32) {
246        let index = index as usize;
247        let (block, bit) = (index / 64, index % 64);
248        assert!(self.data[block] & (1 << bit) == 0);
249        self.data[block] |= 1 << bit;
250        self.bit.update(block, 1);
251    }
252
253    fn remove(&mut self, index: u32) {
254        let index = index as usize;
255        let (i, j) = (index / 64, index % 64);
256        assert!(self.data[i] & (1 << j) != 0);
257        self.data[i] &= !(1 << j);
258        self.bit.update(i, -1);
259    }
crates/library_checker/src/data_structure/point_add_range_sum.rs (line 20)
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}
crates/competitive/src/data_structure/wavelet_matrix.rs (line 1497)
1488    pub fn update(&mut self, mut index: usize, value: M::T) {
1489        debug_assert!(index < self.wavelet_matrix.len);
1490        for d in (0..self.wavelet_matrix.bit_length).rev() {
1491            let level = self.wavelet_matrix.level(d);
1492            let (bit, rank1) = self.wavelet_matrix.bit_vectors[level].access_rank1(index);
1493            if bit {
1494                index = self.wavelet_matrix.zeros[level] + rank1;
1495            } else {
1496                index -= rank1;
1497                self.bits[level].update(index, value.clone());
1498            }
1499        }
1500    }
crates/aizu_online_judge/src/grl/grl_5_d.rs (line 31)
15pub fn grl_5_d(reader: impl Read, writer: impl Write) {
16    prepare_io!(reader, writer);
17    sc!(n, c: [SizedCollect<usize>; iter n]);
18    let edges = c
19        .enumerate()
20        .flat_map(|(u, it)| it.into_iter().map(move |v| (u, v)))
21        .collect();
22    let graph = UndirectedSparseGraph::from_edges(n, edges);
23    let et = graph.path_euler_tour_builder(0).build();
24    let mut bit = BinaryIndexedTree::<AdditiveOperation<_>>::new(et.size);
25
26    sc!(q);
27    for _ in 0..q {
28        sc!(query: Query);
29        match query {
30            Query::Add { v, w } => {
31                et.update(v, w, -w, |k, x| bit.update(k, x));
32            }
33            Query::Get { u } => {
34                let ans = et.fold(u, |k| bit.accumulate(k));
35                pp!(ans);
36            }
37        }
38    }
39}
crates/library_checker/src/tree/vertex_get_range_contour_add_on_tree.rs (line 28)
14pub fn vertex_get_range_contour_add_on_tree(reader: impl Read, writer: impl Write) {
15    prepare_io!(reader, writer);
16    sc!(n, q, mut a: [i64; n], (graph, _): @TreeGraphScanner::<usize, ()>::new(n));
17    let cq = graph.contour_query_range();
18    let mut bits: Vec<BinaryIndexedTree<AdditiveOperation<_>>> = cq
19        .component_sizes()
20        .map(|n| BinaryIndexedTree::new(n + 1))
21        .collect();
22
23    for _ in 0..q {
24        sc!(query: Query);
25        match query {
26            Query::Add { v, l, r, x } => {
27                cq.for_each_contour_range(v, l, r, |c, start, end| {
28                    bits[c].update(start, x);
29                    bits[c].update(end, -x);
30                });
31                if l == 0 && 0 < r {
32                    a[v] += x;
33                }
34            }
35            Query::Get { v } => {
36                let mut ans = a[v];
37                cq.for_each_index(v, |c, i| ans += bits[c].accumulate(i));
38                pp!(ans);
39            }
40        }
41    }
42}
Additional examples can be found in:
Source

pub fn partition_point_acc<P>(&self, pred: P) -> usize
where P: FnMut(&M::T) -> bool,

Source§

impl<G: Group> BinaryIndexedTree<G>

Source

pub fn fold(&self, l: usize, r: usize) -> G::T

Examples found in repository?
crates/competitive/src/data_structure/binary_indexed_tree.rs (line 138)
137    pub fn get(&self, k: usize) -> G::T {
138        self.fold(k, k + 1)
139    }
More examples
Hide additional examples
crates/library_checker/src/data_structure/point_add_range_sum.rs (line 29)
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}
crates/competitive/src/data_structure/range_frequency.rs (line 272)
261    fn query(&self, left: u32, right: u32) -> usize {
262        if left >= right {
263            return 0;
264        }
265        let (left, right) = (left as usize, right as usize - 1);
266        let (li, lj) = (left / 64, left % 64);
267        let (ri, rj) = (right / 64, right % 64);
268        let rj_r = 63 - rj;
269        if li == ri {
270            (self.data[li] << rj_r >> (lj + rj_r)).count_ones() as usize
271        } else {
272            let mut ans = self.bit.fold(li + 1, ri) as usize;
273            ans += (self.data[li] >> lj).count_ones() as usize;
274            ans += (self.data[ri] << rj_r).count_ones() as usize;
275            ans
276        }
277    }
crates/competitive/src/data_structure/range_fold_with_upper_bound.rs (line 61)
34    pub fn execute(self) -> Vec<M::T> {
35        let mut values: Vec<_> = self
36            .keys
37            .iter()
38            .copied()
39            .enumerate()
40            .map(|(index, key)| (key, index))
41            .collect();
42        values.radix_sort_by_key(|&(key, _)| key);
43        let mut order: Vec<_> = self
44            .queries
45            .iter()
46            .enumerate()
47            .map(|(index, (_, upper_bound))| (*upper_bound, index))
48            .collect();
49        order.radix_sort_by_key(|&(upper_bound, _)| upper_bound);
50
51        let mut bit: BinaryIndexedTree<M> = BinaryIndexedTree::new(values.len());
52        let mut answers = vec![M::unit(); self.queries.len()];
53        let mut inserted = 0;
54        for (upper_bound, index) in order {
55            while inserted < values.len() && values[inserted].0 <= upper_bound {
56                let position = values[inserted].1;
57                bit.update(position, self.weights[position].clone());
58                inserted += 1;
59            }
60            let range = &self.queries[index].0;
61            answers[index] = bit.fold(range.start, range.end);
62        }
63        answers
64    }
Source

pub fn fold_abelian(&self, l: usize, r: usize) -> G::T
where G: AbelianGroup,

Examples found in repository?
crates/competitive/src/data_structure/wavelet_matrix.rs (line 1508)
1502    pub fn fold_lessthan(&self, value: T, range: Range<usize>) -> M::T {
1503        let mut result = M::unit();
1504        self.wavelet_matrix
1505            .query_less_than(value, range, |d, range| {
1506                M::operate_assign(
1507                    &mut result,
1508                    &self.bits[self.wavelet_matrix.level(d)].fold_abelian(range.start, range.end),
1509                );
1510            });
1511        result
1512    }
1513
1514    pub fn fold_range(&self, values: Range<T>, range: Range<usize>) -> M::T {
1515        let lower = self
1516            .wavelet_matrix
1517            .compress
1518            .index_lower_bound(&values.start);
1519        let upper = self.wavelet_matrix.compress.index_lower_bound(&values.end);
1520        if lower >= upper {
1521            return M::unit();
1522        }
1523        let mut range = range;
1524        for d in (0..self.wavelet_matrix.bit_length).rev() {
1525            let level = self.wavelet_matrix.level(d);
1526            let start1 = self.wavelet_matrix.bit_vectors[level].rank1(range.start);
1527            let end1 = self.wavelet_matrix.bit_vectors[level].rank1(range.end);
1528            let start0 = range.start - start1;
1529            let end0 = range.end - end1;
1530            if ((lower >> d) & 1) == ((upper >> d) & 1) {
1531                if ((lower >> d) & 1) == 0 {
1532                    range = start0..end0;
1533                } else {
1534                    range = self.wavelet_matrix.zeros[level] + start1
1535                        ..self.wavelet_matrix.zeros[level] + end1;
1536                }
1537                continue;
1538            }
1539            let zero_range = start0..end0;
1540            let one_range =
1541                self.wavelet_matrix.zeros[level] + start1..self.wavelet_matrix.zeros[level] + end1;
1542            let lower_sum = self.fold_lessthan_index(lower, zero_range.clone(), d);
1543            let upper_sum = self.fold_lessthan_index(upper, one_range, d);
1544            let zero_sum = self.bits[level].fold_abelian(zero_range.start, zero_range.end);
1545            let mut result = M::rinv_operate(&zero_sum, &lower_sum);
1546            M::operate_assign(&mut result, &upper_sum);
1547            return result;
1548        }
1549        M::unit()
1550    }
1551
1552    fn fold_lessthan_index(&self, idx: usize, mut range: Range<usize>, bits: usize) -> M::T {
1553        let mut result = M::unit();
1554        for d in (idx.trailing_zeros() as usize..bits).rev() {
1555            let level = self.wavelet_matrix.level(d);
1556            let start1 = self.wavelet_matrix.bit_vectors[level].rank1(range.start);
1557            let end1 = self.wavelet_matrix.bit_vectors[level].rank1(range.end);
1558            let start0 = range.start - start1;
1559            let end0 = range.end - end1;
1560            if ((idx >> d) & 1) != 0 {
1561                M::operate_assign(&mut result, &self.bits[level].fold_abelian(start0, end0));
1562                range.start = self.wavelet_matrix.zeros[level] + start1;
1563                range.end = self.wavelet_matrix.zeros[level] + end1;
1564            } else {
1565                range.start = start0;
1566                range.end = end0;
1567            }
1568        }
1569        result
1570    }
More examples
Hide additional examples
crates/library_checker/src/tree/vertex_add_range_contour_sum_on_tree.rs (line 36)
14pub fn vertex_add_range_contour_sum_on_tree(reader: impl Read, writer: impl Write) {
15    prepare_io!(reader, writer);
16    sc!(n, q, mut a: [i64; n], (graph, _): @TreeGraphScanner::<usize, ()>::new(n));
17    let cq = graph.contour_query_range();
18    let mut raw: Vec<_> = cq.component_sizes().map(|n| vec![0; n]).collect();
19    for (v, &x) in a.iter().enumerate() {
20        cq.for_each_index(v, |c, i| raw[c][i] += x);
21    }
22    let mut bits: Vec<BinaryIndexedTree<AdditiveOperation<_>>> = raw
23        .into_iter()
24        .map(|values| BinaryIndexedTree::from_slice(&values))
25        .collect();
26    for _ in 0..q {
27        sc!(query: Query);
28        match query {
29            Query::Add { p, x } => {
30                a[p] += x;
31                cq.for_each_index(p, |c, i| bits[c].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, |c, start, end| {
36                    ans += bits[c].fold_abelian(start, end);
37                });
38                pp!(ans);
39            }
40        }
41    }
42}
Source

pub fn get(&self, k: usize) -> G::T

Examples found in repository?
crates/competitive/src/data_structure/binary_indexed_tree.rs (line 142)
141    pub fn set(&mut self, k: usize, x: G::T) {
142        self.update(k, G::operate(&G::inverse(&self.get(k)), &x));
143    }
Source

pub fn set(&mut self, k: usize, x: G::T)

Trait Implementations§

Source§

impl<M> Clone for BinaryIndexedTree<M>
where M: Monoid,

Source§

fn clone(&self) -> Self

Returns a duplicate of the value. Read more
1.0.0 (const: unstable) · Source§

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source. Read more
Source§

impl<M> Debug for BinaryIndexedTree<M>
where M: Monoid<T: Debug>,

Source§

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter. Read more

Auto Trait Implementations§

§

impl<M> Freeze for BinaryIndexedTree<M>
where Vec<<M as Magma>::T>: Freeze,

§

impl<M> RefUnwindSafe for BinaryIndexedTree<M>
where Vec<<M as Magma>::T>: RefUnwindSafe,

§

impl<M> Send for BinaryIndexedTree<M>
where Vec<<M as Magma>::T>: Send,

§

impl<M> Sync for BinaryIndexedTree<M>
where Vec<<M as Magma>::T>: Sync,

§

impl<M> Unpin for BinaryIndexedTree<M>
where Vec<<M as Magma>::T>: Unpin,

§

impl<M> UnsafeUnpin for BinaryIndexedTree<M>
where Vec<<M as Magma>::T>: UnsafeUnpin,

§

impl<M> UnwindSafe for BinaryIndexedTree<M>
where Vec<<M as Magma>::T>: UnwindSafe,

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> CloneToUninit for T
where T: Clone,

Source§

unsafe fn clone_to_uninit(&self, dest: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dest. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> ToArrayVecScalar for T

Source§

fn to_array_vec_scalar(self) -> ArrayVecScalar<T>

Source§

impl<T> ToOwned for T
where T: Clone,

Source§

type Owned = T

The resulting type after obtaining ownership.
Source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
Source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = !

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, !>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.