2 次元の累積和
| 項目 | データ |
|---|---|
| 計算量 | 構築 $O(WH)$ クエリ $O(1)$ |
| CumulativeSum(sz) | |
|---|---|
| 機能 | サイズ $W \times H$ で初期化 |
| 引数 | $W, H$: 大きさ |
| void add(x, y, z) | |
|---|---|
| 機能 | $(x, y)$ 番目の要素に $z$ を足す |
| 引数 | $x, y$: 要素位置(0 - indexed) |
| $z$: 値 |
| void build() | |
|---|---|
| 機能 | 構築 |
| int query(sx, sy, gx, gy) | |
|---|---|
| 機能 | $[sx, sy]-(gx, gy)$ の和を求める(半開区間) |
| 戻り値 | 和 |