積分画像（インテグラル画像）

概要

累積和を使うことで、矩形上の値の和を高速に計算可能

2次元

code:cpp

// 入力: H × W のグリッド

int H, W; cin >> H >> W;

vector<vector<int> > a(H, vector<int>(W));

// 累積和を計算

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";

}