Struct Segtree2D

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

二次元のセグメント木

Implementations

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

where M::Element: Clone,

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

Time complexity $O(wh)$

Space complexity $O(wh)$

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

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

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

Time complexity $O(1)$

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

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

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

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