PrefixSum2D
クラス · 二次元累積和
template <class T = std::int64_t, bool RangeAdd = false>
struct PrefixSum2D;
概要
二次元累積和
テンプレートパラメータ
| 名前 | 説明 |
|---|---|
T |
値の型 |
RangeAdd |
true なら矩形加算（差分配列）、false なら点更新として構築する。 |
構築・破棄
| 名前 | 説明 | 計算量 |
|---|---|---|
(constructor) |
(1) 空の二次元累積和を構築する (2) n行m列の0初期化された表を構築する (3) 二次元配列から累積和を構築する |
(1) $O(1)$ (2) $O(nm)$ (3) 行数を $n$、列数を $m$ として $O(nm)$ |
メンバ関数
| 名前 | 説明 | 計算量 |
|---|---|---|
set |
v[x][y] = val（build 前のみ有効） | $O(1)$ |
add |
(1) v[x][y] += val（build 前のみ有効） (2) 半開矩形 $[x_1,x_2)\times[y_1,y_2)$ へ val を加算する（build 前のみ有効） |
$O(1)$ |
build |
build前の値から二次元累積和を構築する | $O(nm)$ |
get |
v[x][y]を返す | $O(1)$ |
sum |
(1) 接頭辞矩形 $[0,x)\times[0,y)$ の総和を返す (2) 半開矩形 $[x_1,x_2)\times[y_1,y_2)$ の総和を返す |
$O(1)$ |
メンバの詳細
(constructor)
// (1)
PrefixSum2D();
// (2)
PrefixSum2D(int _n, int _m);
// (3)
template <class U>
PrefixSum2D(const std::vector<std::vector<U>> &v);
(1) 空の二次元累積和を構築する
- 計算量: $O(1)$
(2) n行m列の0初期化された表を構築する
- 計算量: $O(nm)$
(3) 二次元配列から累積和を構築する
- 計算量: 行数を $n$、列数を $m$ として $O(nm)$
add
// (1)
void add(int x, int y, T val);
// (2)
void add(int x1, int y1, int x2, int y2, T val) requires RangeAdd;
(1) v[x][y] += val（build 前のみ有効）
- 計算量: $O(1)$
(2) 半開矩形 $[x_1,x_2)\times[y_1,y_2)$ へ val を加算する（build 前のみ有効）
- 計算量: $O(1)$
sum
// (1)
T sum(int x, int y) const;
// (2)
T sum(int x1, int y1, int x2, int y2) const;
(1) 接頭辞矩形 $[0,x)\times[0,y)$ の総和を返す
- 計算量: $O(1)$
(2) 半開矩形 $[x_1,x_2)\times[y_1,y_2)$ の総和を返す
- 計算量: $O(1)$