C++で部分行列クエリのXORを効率的に計算する方法

この問題では、N×N の行列と複数のクエリが与えられます。各クエリには、元の行列から切り出す部分行列の左上と右下の座標が含まれており、その部分行列に含まれるすべての要素のXOR（排他的論理和）を求めることが課題です。

具体例を使って問題を確認しましょう。

入力

arr[][] = {{1, 2, 3}
{4, 5, 6}
{7, 8, 9}}
クエリ: {0,0, 2,2}, {1, 2, 2, 2}

出力

1 15

解説

クエリ 1 : 1^2^3^4^5^6^7^8^9 = 1
クエリ 2 : 6^9 = 15

解法のアプローチ：累積XOR（プレフィックスXOR）行列

この問題を効率的に解くには、あらかじめ累積XOR（プレフィックスXOR）行列を構築しておくのが有効です。位置 (R, C) に格納する値は、左上 (0, 0) から右下 (R, C) までの部分行列全体のXORを表します。

構築手順は以下の通りです。

1. まず、行列の各行について行方向の累積XORを順番に計算します。
2. 次に、各列について列方向の累積XORを順番に計算します。

こうして作成した累積XOR行列を使えば、(r1, c1) から (r2, c2) までの部分行列のXORは、次の式で求められます。

prefixXor[r2][c2] ^ prefixXor[r1-1][c2] ^ prefixXor[r2][c1-1] ^ prefixXor[r1-1][c1-1]

r1 や c1 が 0 の場合は範囲外参照を避けるため、該当する項を除外します。この手法では、前処理に O(N²)、各クエリへの回答はわずか O(1) で済むため、クエリ数が多い場合でも高速に処理できるのが大きな利点です。

実装例

#include <iostream>
using namespace std;
#define n 3

// 累積XOR行列を構築する
void preXOR(int arr[][n], int prefix_xor[][n]) {
    // 行方向の累積XOR
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            if (j == 0)
                prefix_xor[i][j] = arr[i][j];
            else
                prefix_xor[i][j]
                    = (prefix_xor[i][j - 1] ^ arr[i][j]);
        }
    // 列方向の累積XOR
    for (int i = 0; i < n; i++)
        for (int j = 1; j < n; j++)
            prefix_xor[j][i]
                = (prefix_xor[j - 1][i] ^ prefix_xor[j][i]);
}

// クエリ (r1, c1) ～ (r2, c2) の部分行列XORを返す
int XORSubMatrix(int prefix_xor[][n], int querry[4]) {
    int xor_1 = 0, xor_2 = 0, xor_3 = 0;
    if (querry[0] != 0)
        xor_1 = prefix_xor[querry[0] - 1][querry[3]];
    if (querry[1] != 0)
        xor_2 = prefix_xor[querry[2]][querry[1] - 1];
    if (querry[0] != 0 and querry[1] != 0)
        xor_3 = prefix_xor[querry[0] - 1][querry[1] - 1];
    return ((prefix_xor[querry[2]][querry[3]] ^ xor_1) ^ (xor_2 ^ xor_3));
}

int main() {
    int arr[][n] = { { 1, 2, 3 },
                     { 4, 5, 6 },
                     { 7, 8, 9 } };
    int prefix_xor[n][n];
    preXOR(arr, prefix_xor);

    int querry1[] = {0, 0, 2, 2};
    int querry2[] = {1, 2, 2, 2};

    cout<<"クエリによる部分行列のXOR :\n";
    cout<<"クエリ 1 : "<<XORSubMatrix(prefix_xor, querry1)<<endl;
    cout<<"クエリ 2 : "<<XORSubMatrix(prefix_xor, querry2)<<endl;
    return 0;
}

出力

クエリ 1 : 1
クエリ 2 : 15

このように、累積XOR行列を一度構築しておけば、以降の任意の部分行列XORクエリを定数時間で答えられるため、多次元配列に対する範囲集計クエリ全般に応用できる強力なテクニックです。