Struct BinaryIndexedTree2D

Source

pub struct BinaryIndexedTree2D<M>where
    M: Monoid,
{ /* private fields */ }

Implementations§

Source §

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

Source

pub fn new(h: usize, w: usize) -> Self

Source

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

fold [0, i) x [0, j)

Examples found in repository ?

crates/competitive/src/data_structure/binary_indexed_tree_2d.rs (line 67)

66    pub fn accumulate(&self, i: usize, j: usize) -> M::T {
67        self.accumulate0(i + 1, j + 1)
68    }
69    #[inline]
70    pub fn update(&mut self, i: usize, j: usize, x: M::T) {
71        let mut a = i + 1;
72        while a <= self.h {
73            let mut b = j + 1;
74            while b <= self.w {
75                self.bit[a][b] = M::operate(&self.bit[a][b], &x);
76                b += b & (!b + 1);
77            }
78            a += a & (!a + 1);
79        }
80    }
81}
82
83impl<G> BinaryIndexedTree2D<G>
84where
85    G: Group,
86{
87    #[inline]
88    /// 0-indexed [i1, i2) x [j1, j2)
89    pub fn fold(&self, i1: usize, j1: usize, i2: usize, j2: usize) -> G::T {
90        let mut res = G::unit();
91        res = G::operate(&res, &self.accumulate0(i1, j1));
92        res = G::rinv_operate(&res, &self.accumulate0(i1, j2));
93        res = G::rinv_operate(&res, &self.accumulate0(i2, j1));
94        res = G::operate(&res, &self.accumulate0(i2, j2));
95        res
96    }

Source

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

fold [0, i] x [0, j]

Source

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

Examples found in repository ?

crates/competitive/src/data_structure/binary_indexed_tree_2d.rs (line 105)

102    pub fn set(&mut self, i: usize, j: usize, x: G::T) {
103        let y = G::inverse(&self.get(i, j));
104        let z = G::operate(&y, &x);
105        self.update(i, j, z);
106    }

Source §

impl<G> BinaryIndexedTree2D<G>
where G: Group,

Source

pub fn fold(&self, i1: usize, j1: usize, i2: usize, j2: usize) -> G::T

0-indexed [i1, i2) x [j1, j2)

Examples found in repository ?

crates/competitive/src/data_structure/binary_indexed_tree_2d.rs (line 99)

98    pub fn get(&self, i: usize, j: usize) -> G::T {
99        self.fold(i, j, i + 1, j + 1)
100    }

Source

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

Examples found in repository ?

crates/competitive/src/data_structure/binary_indexed_tree_2d.rs (line 103)

102    pub fn set(&mut self, i: usize, j: usize, x: G::T) {
103        let y = G::inverse(&self.get(i, j));
104        let z = G::operate(&y, &x);
105        self.update(i, j, z);
106    }