二次元累積和

二次元累積和とは

このような配列を考える。これを配列Aとする。

配列Aの中の任意の長方形の区間の総和を求めたいとする。
例

図の水色のマスの合計は、1+5+2+6+3+9+3+8=37である。
これは、A[1][2]からA[2][5]までの総和といえる。
これをΣ([1][2],[2][5])と書くことにする。
次の関係式が成り立つ。
Σ([1][2],[2][5])=Σ([0][0],[2][5])-Σ([0][0],[0][5])-Σ([0][0],[2][1])+Σ([0][0],[0][1])

一般化すると次のようになる。
Σ([a][b],[c][d])=Σ([0][0],[c][d])-Σ([0][0],[a-1][d])-Σ([0][0],[c][b-1])+Σ([0][0],[a-1][b-1])

Σ([0][0],[i][j])=S[i][j]とする。(これが二次元累積和)
そうすると
Σ([a][b],[c][d])=S[c][d]-S[a-1][d]-S[c][b-1]+S[a-1][b-1]
となり、Sを前計算で作っておけばO(1)で長方形の区間が求まる。

二次元累積和の作り方

S[i][j]=S[i-1][j]+S[i][j-1]-S[i-1][j-1]+A[i][j]
という漸化式が成り立つ。(図を見ながら確認すればわかる。)
よってインデックスが小さいほうから埋めていけばO(HW)で作成できる。
i=0またはj=0の時は配列外参照になるため別の処理が必要である。
(i)i=0かつj=0の時
S[i][j]=A[i][j]
(ii)i=0かつj≠0の時
S[i][j]=S[i][j-1]+A[i][j]
(iii)i≠0かつj=0の時
S[i][j]=S[i-1][j]+A[i][j]

コード例

図の水色の部分の総和を求める。(答えは37)

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<sstream>
#include<iterator>
#include<list>

using namespace std;

#define INF LLONG_MAX / 5
#define int long long
#define rep(i, n) for (int i = 0; i < n; i++)
#define sort(v) sort((v).begin(), (v).end())
#define reverse(v) reverse((v).begin(), (v).end())
#define upper(v,hoge) upper_bound(v.begin(),v.end(),hoge)
#define lower(v,hoge) lower_bound(v.begin(),v.end(),hoge)
#define enld endl

signed main() {
	vector<vector<int>>A;
	A = {
		{1,5,8,4,7,4,2},
		{4,7,1,5,2,6,4},
		{8,2,3,9,3,8,1},
		{3,5,6,1,7,9,2}
	};
	int H = 4, W = 7;

	//二次元累積和の作成
	vector<vector<int>>S(H, vector<int>(W));
	rep(i, H) {
		rep(j, W) {
			if (i == 0 && j == 0) {
				S[i][j] = A[i][j];
			}
			else if (i == 0 && j != 0) {
				S[i][j] = S[i][j - 1] + A[i][j];
			}
			else if (i != 0 && j == 0) {
				S[i][j] = S[i - 1][j] + A[i][j];
			}
			else {
				S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + A[i][j];
			}
		}
	}

	int a = 1, b = 2, c = 2, d = 5;
	//Σ([a][b],[c][d])を出力
	//Σ([a][b],[c][d])=S[c][d]-S[a-1][d]-S[c][d-1]+S[a-1][b-1]
	cout << S[c][d] - S[a - 1][d] - S[c][b - 1] + S[a - 1][b - 1];
}

37が出力された。

コーナーケース

Σ([a][b],[c][d])=S[c][d]-S[a-1][d]-S[c][b-1]+S[a-1][b-1]
なのでa=0またはb=0の時は配列外参照になる。
この時は特別な処理が必要である。
(i)a=0かつb=0の時
Σ([a][b],[c][d])=S[c][d]
(ii)a=0かつb≠0の時
Σ([a][b],[c][d])=S[c][d]-S[c][b-1]
(iii)a≠0かつb=0の時
Σ([a][b],[c][d])=S[c][d]-S[a-1][d]

となる。

問題

1行目にH Wが空白区切りで与えられる。
2行目以降に二次元配列が与えられる。
次に整数Qが与えられる。
その次のQ行でa b c dが与えられる。(0-index)
それぞれについてΣ([a][b],[c][d])を求めよ。

入力
H W
A[0][0]　・・・　A[0][W-1]
・
・
・
A[H-1][0]　・・・　A[H-1][W-1]
Q
a_1 b_1 c_1 d_1
・
・
・
a_Q b_Q c_Q d_Q

入力例
4 7
1 5 8 4 7 4 2
4 7 1 5 2 6 4
8 2 3 9 3 8 1
3 5 6 1 7 9 2
5
1 2 2 5
1 6 1 6
0 0 0 3
0 1 1 2
3 0 3 5

出力例
37
4
18
21
31

正解コード

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<sstream>
#include<iterator>
#include<list>

using namespace std;

#define INF LLONG_MAX / 5
#define int long long
#define rep(i, n) for (int i = 0; i < n; i++)
#define sort(v) sort((v).begin(), (v).end())
#define reverse(v) reverse((v).begin(), (v).end())
#define upper(v,hoge) upper_bound(v.begin(),v.end(),hoge)
#define lower(v,hoge) lower_bound(v.begin(),v.end(),hoge)
#define enld endl

signed main() {
	int H, W;
	cin >> H >> W;
	vector<vector<int>>A(H, vector<int>(W));
	rep(i, H) {
		rep(j, W) {
			cin >> A[i][j];
		}
	}
	//二次元累積和の作成
	vector<vector<int>>S(H, vector<int>(W));
	rep(i, H) {
		rep(j, W) {
			if (i == 0 && j == 0) {
				S[i][j] = A[i][j];
			}
			else if (i == 0 && j != 0) {
				S[i][j] = S[i][j - 1] + A[i][j];
			}
			else if (i != 0 && j == 0) {
				S[i][j] = S[i - 1][j] + A[i][j];
			}
			else {
				S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + A[i][j];
			}
		}
	}
	int Q;
	cin >> Q;
	int a, b, c, d;
	rep(_, Q) {
		cin >> a >> b >> c >> d;
		if (a == 0 && b == 0) {
			cout << S[c][d] << endl;
		}
		else if (a == 0 && b != 0) {
			cout << S[c][d] - S[c][b - 1] << endl;
		}
		else if (a != 0 && b == 0) {
			cout << S[c][d] - S[a - 1][d] << endl;
		}
		else {
			cout << S[c][d] - S[a - 1][d] - S[c][b - 1] + S[a - 1][b - 1] << endl;
		}
	}
}