C++で実装する変更可能な2次元範囲合計クエリ（Range Sum Query 2D – Mutable）

問題概要

2次元の行列 matrix が与えられ、左上隅と右下隅で定義される矩形領域内に含まれる要素の合計を計算するのがこの問題です。さらに重要なポイントとして、行列の要素を後から更新（mutable）できることも求められています。

例として、次のような入力を考えてみましょう。

ここで、以下のようにメソッドを呼び出すケースを想定します。

• sumRegion(2, 1, 4, 3)
• update(3, 2, 2)
• sumRegion(2, 1, 4, 3)

このとき出力は 8 と 10 になります。最初の呼び出しでは、上の表の緑色で示した部分、つまり (2,1) と (4,3) で定義される矩形領域の合計が 8 となるためです。続く update(3, 2, 2) により3行目・2列目の値が 2 に更新されるため、同じ領域に対する合計は 10 に変わります。

アプローチ：2次元 Binary Indexed Tree（フェニック木）

素朴な方法として、sumRegion が呼ばれるたびに領域内を全走査することもできますが、これは1回あたり O(n·m) の時間がかかり、更新やクエリが大量にある場合には非効率です。そこで本記事では、2次元 Binary Indexed Tree（BIT／フェニック木）を用いた効率的な解法を紹介します。

全体の流れは以下の通りです。

• BIT本体となる2次元配列 tree と、現在のセルの値を保持する2次元配列 value をメンバーとして定義する
• コンストラクタで行列を受け取り、n := 行数、m := 列数 とする
• value は n×m サイズ、tree は (n+1)×(m+1) サイズで確保する
• すべての要素について update(i, j, matrix[i][j]) を呼び出して木を構築する

update(row, col, val)

指定したセルの値を更新するメソッドです。

• n == 0 または m == 0 の場合は何もせずに返す
• delta := val − value[row][col] を計算し、value[row][col] := val と更新する
• i := row+1 から i <= n まで「i := i + (i & −i)」、j := col+1 から j <= m まで「j := j + (j & −j)」という二重ループで、tree[i][j] に delta を加算していく

sum(row, col)

(0,0) から (row, col) までの累積和を求める内部メソッドです。

• ret := 0 で初期化する
• i := row から i > 0 まで「i := i − (i & −i)」、j := col から j > 0 まで「j := j − (j & −j)」という二重ループで ret += tree[i][j] を行う
• ret を返す

sumRegion(row1, col1, row2, col2)

矩形領域の合計を返すメソッドです。

• m == 0 または n == 0 の場合は 0 を返す
• インデックスを1始まりに合わせるため、row1・col1・row2・col2 をそれぞれ +1 する
• sum(row2, col2) + sum(row1−1, col1−1) − sum(row1−1, col2) − sum(row2, col1−1) を返す（包除原理による計算）

計算量

BITを利用することで、update と sumRegion はどちらも O(log n · log m) で実行できます。初期構築には O(n · m · log n · log m) のコストがかかりますが、以降の繰り返しクエリでは大幅な高速化が期待できます。

C++での実装例

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

#include <bits/stdc++.h>
using namespace std;
class NumMatrix {
public:
    int n, m;
    vector<vector<int>> tree;
    vector<vector<int>> value;
    NumMatrix(vector<vector<int>> &matrix) {
        n = matrix.size();
        m = !n ? 0 : matrix[0].size();
        value = vector<vector<int>>(n, vector<int>(m));
        tree = vector<vector<int>>(n + 1, vector<int>(m + 1));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                update(i, j, matrix[i][j]);
            }
        }
    }
    void update(int row, int col, int val) {
        if (n == 0 || m == 0)
            return;
        int delta = val - value[row][col];
        value[row][col] = val;
        for (int i = row + 1; i <= n; i += i & (-i)) {
            for (int j = col + 1; j <= m; j += j & (-j)) {
                tree[i][j] += delta;
            }
        }
    }
    int sum(int row, int col) {
        int ret = 0;
        for (int i = row; i > 0; i -= i & (-i)) {
            for (int j = col; j > 0; j -= j & (-j)) {
                ret += tree[i][j];
            }
        }
        return ret;
    }
    int sumRegion(int row1, int col1, int row2, int col2) {
        if (m == 0 || n == 0)
            return 0;
        row2++;
        row1++;
        col1++;
        col2++;
        return sum(row2, col2) + sum(row1 - 1, col1 - 1) - sum(row1 - 1, col2) - sum(row2, col1 - 1);
    }
};
int main() {
    vector<vector<int>> v = {
        {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(v);
    cout << (ob.sumRegion(2, 1, 4, 3)) << endl;
    ob.update(3, 2, 2);
    cout << (ob.sumRegion(2, 1, 4, 3)) << endl;
}

入力

vector<vector<int>> v = {
   {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(v);
cout << (ob.sumRegion(2, 1, 4, 3)) << endl;
ob.update(3, 2, 2);
cout << (ob.sumRegion(2, 1, 4, 3)) << endl;

出力

8
10

まとめ

このように、2次元 Binary Indexed Tree を使うことで、要素の更新と矩形領域の合計取得をどちらも高速に行えるようになります。特に更新処理と範囲クエリが混在する場面では、毎回全走査を行う O(n·m) のアプローチと比べて圧倒的な性能差が出るため、競技プログラミングや実務のデータ処理でも非常に有用なテクニックです。