Struct BinaryIndexedTree2D

Source

pub struct BinaryIndexedTree2D<M>where
    M: Monoid,{
    h: usize,
    w: usize,
    bit: Vec<Vec<M::T>>,
}

Fields§

§h: usize§w: usize§bit: Vec<Vec<M::T>>

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 66)

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

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 104)

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

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 98)

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

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 102)

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