Struct DualSegmentTree2D 

pub struct DualSegmentTree2D<T, F> { /* private fields */ }

矩形更新・一点取得を行う2次元双対セグメント木です。

行区間 [upper, lower) と列区間 [left, right) はともに 0-indexed の半開区間です。 compose は結合的な演算で、identity はその単位元である必要があります。また、 2 次元の更新ノードを走査する順序に依存しないよう、演算は可換である必要があります。 更新・取得は O(log H log W)、メモリは O(HW) です。

Implementations

impl<T: Copy, F: Fn(T, T) -> T> DualSegmentTree2D<T, F>

pub fn new(height: usize, width: usize, compose: F, identity: T) -> Self

height × width の木を作り、すべての点の初期値を identity にします。 添字は行・列とも 0 始まりです。compose は結合的かつ可換で、identity を 単位元とする必要があります。メモリ量は O(HW) です。

pub fn apply( &mut self, upper: usize, lower: usize, left: usize, right: usize, value: T, )

矩形 [upper, lower) × [left, right) の各点に value を適用します。

行・列区間は 0 始まりの半開区間です。各区間が対応する次元の範囲内でない場合や、 左端が右端を超える場合は panic します。空の行区間または列区間なら何もしません。 計算量は O(log H log W) です。

pub fn get(&self, row: usize, column: usize) -> T

点 (row, column) の値を返します。行・列は 0 始まりで、範囲外なら panic します。 計算量は O(log H log W) です。

pub fn at(&self, row: usize, column: usize) -> T

点 (row, column) の値を返します。行・列は 0 始まりです。

get と同じで、範囲外なら panic します。計算量は O(log H log W) です。

Trait Implementations

impl<T: Clone, F: Clone> Clone for DualSegmentTree2D<T, F>

fn clone(&self) -> DualSegmentTree2D<T, F>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.