C++で部分配列（サブアレイ）のXORを求める方法【前処理で高速化】

問題概要

この問題では、整数配列 arr[] と、配列上の範囲 L から R を指定するクエリが与えられます。目的は、L から R までの部分配列（サブアレイ）のXORを計算して出力することです。

具体例で問題を確認してみましょう。

入力: array = {1, 4, 5, 7, 2, 9}、L = 1、R = 5

出力: 13

説明: 求める値は 4 ^ 5 ^ 7 ^ 2 ^ 9 の計算結果である 13 です。

解決のための考え方

この問題を効率的に解くには、次のXORの性質を利用します。

• 同じビット位置の複数のビットをXORするとき、1 の個数が奇数であれば結果は 1、偶数であれば結果は 0 になる。

この性質をもとに、1 の出現回数を記録する二次元配列 count を作成します。count[i][j] は、「先頭から j 番目までの部分配列 arr[0..j] における、i ビット目の 1 の個数」を表します。

この count 配列を使えば、部分配列 arr[L..R] の各ビット位置における 1 の個数は、次の式で求められます。

count[i][R] − count[i][L−1]

あるビット位置 i における 1 の個数が奇数であれば、答えの i ビット目は 1 にセットされます。最終的なXORの結果は、セットされた各ビット i に対応する 2 の累乗（1 << i）をすべて加算することで得られます。

この前処理を行っておけば、各クエリに対して最大32ビット分の判定だけでXORを求められるため、クエリのたびに範囲内を逐次計算する方法に比べて大幅に高速化できます。

実装例（C++プログラム）

#include <bits/stdc++.h>
using namespace std;
void preProcessArray(int arr[], int n, vector<vector<int> >& cnt) {
    int i, j;
    for (i = 0; i < 32; i++) {
        cnt[i][0] = 0;
        for (j = 0; j < n; j++) {
            if (j > 0) {
                cnt[i][j] = cnt[i][j - 1];
            }
            if (arr[j] & (1 << i))
                cnt[i][j]++;
        }
    }
}
int findXORofSubArray(int L, int R, const vector<vector<int> > count) {
    int result = 0;
    int noOfOnes;
    int i, j;
    for (i = 0; i < 32; i++) {
        noOfOnes = count[i][R] - ((L > 0) ? count[i][L - 1] : 0);
        if (noOfOnes & 1) {
            result+=(1 << i);
        }
    }
    return result;
}
int main(){
    int arr[] = { 1, 4, 5, 7, 2, 9 };
    int n = sizeof(arr) / sizeof(arr[0]);
    vector<vector<int> > count(32, vector<int>(n));
    preProcessArray(arr, n, count);
    int L = 1;
    int R = 5;
    cout<<"The XOR of SubArray: "<<findXORofSubArray(L, R, count);
    return 0;
}

実行結果

The XOR of SubArray: 13