Struct Segtree2D

pub struct Segtree2D<M: Monoid + Commutative> { /* private fields */ }

二次元のセグメント木

Implementations

impl<M: Monoid + Commutative + Clone> Segtree2D<M>

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

Time complexity $O(wh)$

Space complexity $O(wh)$

pub fn fold_2d(&self, _: Range<usize>, _: Range<usize>) -> M

Time complexity $O(\log w \log h)$

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

Time complexity $O(1)$

pub fn assign(&mut self, i: usize, j: usize, value: M)

Time complexity $O(\log w \log h)$

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

Time complexity $O(\log w \log h)$