Struct BinaryIndexedTree2D

Source

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

Fields§

§h: usize§w: usize§bit: 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 70)

69    pub fn accumulate(&self, i: usize, j: usize) -> M::T {
70        self.accumulate0(i + 1, j + 1)
71    }
72    #[inline]
73    pub fn update(&mut self, i: usize, j: usize, x: M::T) {
74        assert!(i < self.h && j < self.w);
75        let mut a = i + 1;
76        let stride = self.w + 1;
77        while a <= self.h {
78            let mut b = j + 1;
79            while b <= self.w {
80                // SAFETY: the method validates the leaf, and Fenwick ancestors stay within the
81                // allocated table.
82                M::operate_assign(unsafe { self.bit.get_unchecked_mut(a * stride + b) }, &x);
83                b += b & (!b + 1);
84            }
85            a += a & (!a + 1);
86        }
87    }
88}
89
90impl<G> BinaryIndexedTree2D<G>
91where
92    G: Group,
93{
94    #[inline]
95    /// 0-indexed [i1, i2) x [j1, j2)
96    pub fn fold(&self, i1: usize, j1: usize, i2: usize, j2: usize) -> G::T {
97        let mut res = self.accumulate0(i1, j1);
98        G::rinv_operate_assign(&mut res, &self.accumulate0(i1, j2));
99        G::rinv_operate_assign(&mut res, &self.accumulate0(i2, j1));
100        G::operate_assign(&mut res, &self.accumulate0(i2, j2));
101        res
102    }

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

108    pub fn set(&mut self, i: usize, j: usize, x: G::T) {
109        let y = G::inverse(&self.get(i, j));
110        let z = G::operate(&y, &x);
111        self.update(i, j, z);
112    }

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

104    pub fn get(&self, i: usize, j: usize) -> G::T {
105        self.fold(i, j, i + 1, j + 1)
106    }

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

108    pub fn set(&mut self, i: usize, j: usize, x: G::T) {
109        let y = G::inverse(&self.get(i, j));
110        let z = G::operate(&y, &x);
111        self.update(i, j, z);
112    }