積分画像(インテグラル画像)
概要
累積和を使うことで、矩形上の値の和を高速に計算可能
2次元
$ s_0 = 0, s_1=a_0, s_2=a_0+a_1, ... という定義
code:cpp
// 入力: H × W のグリッド
int H, W; cin >> H >> W;
vector<vector<int> > a(H, vector<int>(W));
for (int i = 0; i < H; ++i) for (int j = 0; j < W; ++j) cin >> aij; // 累積和を計算
vector<vector<int> > s(H+1, vector<int>(W+1, 0));
for (int i = 0; i < H; ++i)
for (int j = 0; j < W; ++j)
// クエリ [x1, x2) × [y1, y2) の長方形区域の和
int Q; cin >> Q;
for (int q = 0; q < Q; ++q) {
int x1, x2, y1, y2;
cin >> x1 >> x2 >> y1 >> y2;
}
3次元
コード例 (上記解説から引用してコメント付与)
code:cpp
// 3次元画像
vector a(n, vector(n, vector(n, 0)));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
for (int k = 0; k < n; ++k) {
}
}
}
// 累積和を計算
// indexは1-basedになっているので注意
vector sum(n + 1, vector(n + 1, vector(n + 1, 0LL)));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
for (int k = 0; k < n; ++k) {
}
}
}
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
int lx, rx, ly, ry, lz, rz;
// ここでlx, rxらは1-basedになっているのに注意
cin >> lx >> rx >> ly >> ry >> lz >> rz;
lx--, ly--, lz--;
<< "\n";
}