This documentation is automatically generated by online-judge-tools/verification-helper
#include "dp/cumulative-sum-2d.hpp"
$2$ 次元の累積和. 前計算として事前に累積和をとることで, 矩形和を $O(1)$ で求めることが出来る.
add(x, y, z)
: 要素 $(x, y)$ に値 z
を加える.build()
: 累積和を構築する.query(sx, sy, gx, gy)
: 左下 $(sx, sy)$, 右上 $(gx, gy)$ の矩形和を求める(半開区間で与えることに注意すること. 具体的には列 $gx$ と行 $gy$ は含まない).add(x, y, z)
: $O(1)$build()
: $O(WH)$query(sx, sy, gx, gy)
: $O(1)$template <class T>
struct CumulativeSum2D {
vector<vector<T> > data;
CumulativeSum2D(int W, int H) : data(W + 1, vector<T>(H + 1, 0)) {}
void add(int x, int y, T z) {
++x, ++y;
if (x >= data.size() || y >= data[0].size()) return;
data[x][y] += z;
}
void build() {
for (int i = 1; i < data.size(); i++) {
for (int j = 1; j < data[i].size(); j++) {
data[i][j] += data[i][j - 1] + data[i - 1][j] - data[i - 1][j - 1];
}
}
}
T query(int sx, int sy, int gx, int gy) const {
return (data[gx][gy] - data[sx][gy] - data[gx][sy] + data[sx][sy]);
}
};
#line 1 "dp/cumulative-sum-2d.hpp"
template <class T>
struct CumulativeSum2D {
vector<vector<T> > data;
CumulativeSum2D(int W, int H) : data(W + 1, vector<T>(H + 1, 0)) {}
void add(int x, int y, T z) {
++x, ++y;
if (x >= data.size() || y >= data[0].size()) return;
data[x][y] += z;
}
void build() {
for (int i = 1; i < data.size(); i++) {
for (int j = 1; j < data[i].size(); j++) {
data[i][j] += data[i][j - 1] + data[i - 1][j] - data[i - 1][j - 1];
}
}
}
T query(int sx, int sy, int gx, int gy) const {
return (data[gx][gy] - data[sx][gy] - data[gx][sy] + data[sx][sy]);
}
};