二次元累積和
説明
点add, 矩形sumの $2$ 次元の累積和。前計算として事前に累積させておけば, 累積和を $O(1)$ で求めることが出来る。
使い方
- set(x, y, z): 要素 $(x, y)$ に値 $z$ を加える
- build(): 累積和を構築する
- query(sx, sy, gx, gy): 左上 $[sx, sy]$, 右下 $(gx, gy)$ の矩形内の和を求める(半開区間)
計算量
- build: $O(WH)$
- add, query: $O(1)$
実装例
点add, 矩形sumの $2$ 次元の累積和。前計算として事前に累積させておけば, 累積和を $O(1)$ で求めることが出来る。