【C++】2次元範囲和クエリ（不変）の解き方：累積和で長方形領域の合計を高速に求める

2次元行列 matrix が与えられたとき、左上隅を (row1, col1)、右下隅を (row2, col2) として定義される長方形領域内の要素の合計を求める問題を考えます。

問題の例

例えば、次のような行列があるとします。

上の表で青色に塗られた長方形は (2,1) と (4,3) によって定義されており、この領域内の要素の合計は 8 になります。

したがって、sumRegion(2, 1, 4, 3)、sumRegion(1, 1, 2, 2)、sumRegion(1, 2, 2, 4) というクエリを実行すると、それぞれ 8、11、12 が返されます。

解法のアプローチ：2次元累積和（DP）

この問題は、あらかじめ2次元の累積和テーブルを構築しておくことで効率的に解けます。前処理に O(n×m)、各クエリへの応答は O(1) で済むため、同じ行列に対して何度も範囲和を問い合わせるケースに最適です。手順は以下の通りです。

• dp という名前の2次元配列を定義します。

• コンストラクタで次のように初期化を行います。

• n := 行数。n が 0 の場合はそのまま返します。

• m := 列数。

• dp := n × m サイズの新しい2次元配列を作成します。

• i を 0 から n 未満まで繰り返します。

  • j を 0 から m 未満まで繰り返します。

    • j − 1 < 0 のときは dp[i][j] = matrix[i][j] とし、それ以外は dp[i][j] = dp[i][j−1] + matrix[i][j] とします（各行ごとの横方向の累積和）。

• 続けて i を 1 から n 未満まで繰り返します。

  • j を 0 から m 未満まで繰り返します。

    • dp[i][j] += dp[i−1][j] として縦方向にも累積させます。これにより dp[i][j] は左上 (0,0) から (i,j) までの長方形領域の総和を表すようになります。

• クエリメソッド sumRegion(row1, col1, row2, col2) では、包除原理を使って目的の領域の合計を取り出します。

• ret := dp[row2][col2]（(0,0) から (row2,col2) までの全体の和）

• sub1 := row1 − 1 < 0 なら 0、それ以外は dp[row1−1][col2]（上側の余分な領域）

• sub2 := col1 − 1 < 0 なら 0、それ以外は dp[row2][col1−1]（左側の余分な領域）

• row1 − 1 < 0 または col1 − 1 < 0 の場合は add := 0、それ以外は add := dp[row1−1][col1−1]（二重に引かれた部分を戻す）

• ret − sub1 − sub2 + add を返します。

C++による実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class NumMatrix {
    public:
    vector<vector<int>> dp;
    NumMatrix(vector<vector<int>>& matrix) {
        int n = matrix.size();
        if(!n) return;
        int m = matrix[0].size();
        dp = vector<vector<int>>(n, vector<int>(m));
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                dp[i][j] = j - 1 < 0 ? matrix[i][j] : dp[i][j - 1] + matrix[i][j];
            }
        }
        for(int i = 1; i < n; i++){
            for(int j = 0; j < m; j++){
                dp[i][j] += dp[i - 1][j];
            }
        }
    }
    int sumRegion(int row1, int col1, int row2, int col2) {
        int ret = dp[row2][col2];
        int sub1 = row1 - 1 < 0 ? 0 : dp[row1 - 1][col2];
        int sub2 = col1 - 1 < 0 ? 0 : dp[row2][col1 - 1];
        int add = row1 - 1 < 0 || col1 - 1 < 0 ? 0 : dp[row1 - 1][col1 - 1];
        return ret - sub1 - sub2 + add;
    }
};
main(){
    vector<vector<int>> mat = {{3,0,1,4,2},{5,6,3,2,1},{1,2,0,1,5},{4,1,0,1,7},{1,0,3,0,5}};
    NumMatrix ob(mat);
    cout << ob.sumRegion(2,1,4,3) << endl;
    cout << ob.sumRegion(1,1,2,2) << endl;
    cout << ob.sumRegion(1,2,2,4) << endl;
}

入力

[[3,0,1,4,2],
[5,6,3,2,1],
[1,2,0,1,5],
[4,1,0,1,7],
[1,0,3,0,5]]
sumRegion(2,1,4,3)
sumRegion(1,1,2,2)
sumRegion(1,2,2,4)

出力

8
11
12

まとめ

この手法のポイントは、行列が不変（イミュータブル）であることを前提に、構築時に累積和テーブルを作成してしまうことです。これにより、範囲和のクエリごとに領域をなめて計算する O(n×m) の素朴な方法と比べ、クエリあたり定数時間で答えを得られます。境界（row1 や col1 が 0 の場合）の扱いに注意しながら包除原理を適用するのが実装上のコツです。