C++で部分配列のXORクエリを高速に処理する方法

正整数からなる配列 arr と、queries[i] = [Li, Ri] の形式で与えられるクエリ配列があるとします。各クエリ i に対して、Li から Ri までの要素のXOR（arr[Li] XOR arr[Li+1] XOR ... XOR arr[Ri]）を計算し、すべての結果を格納した配列を返す必要があります。

例えば、入力が [1,3,4,8]、クエリが [[0,1],[1,2],[0,3],[3,3]] の場合、出力は [2,7,14,8] となります。これは、配列内の各要素を2進数で表すと、1 = 0001、3 = 0011、4 = 0100、8 = 1000 となるためです。各クエリに対するXORの計算結果は以下の通りです。

• [0,1]: 1 XOR 3 = 2
• [1,2]: 3 XOR 4 = 7
• [0,3]: 1 XOR 3 XOR 4 XOR 8 = 14
• [3,3]: 8

解法のポイント：累積XOR（プレフィックスXOR）

この問題を効率的に解く鍵となるのが「累積XOR」です。各クエリのたびに範囲内の要素を順にXORしていては、クエリ数が増えた場合に計算コストが膨大になります。そこで、事前に累積XOR配列を作成しておくことで、各クエリをO(1)で処理できるようになります。

XORには「同じ値を2回XORすると打ち消される（a XOR a = 0）」という重要な性質があります。これを利用すると、区間 [l, r] のXORは pre[r] XOR pre[l-1] という簡単な式で求められます。

アルゴリズムの手順

1. n を配列 arr のサイズとする
2. サイズ n + 1 の累積XOR配列 pre を定義し、pre[i] := pre[i - 1] XOR arr[i - 1] で埋める
3. 結果を格納する配列 ans を定義する
4. i を 0 からクエリ数 - 1 まで繰り返す
   • l := queries[i][0]、r := queries[i][1] とする
   • l と r をそれぞれ 1 増やす
   • pre[r] XOR pre[l - 1] を ans に追加する
5. ans を返す

C++による実装例

以下の実装を見ると、仕組みがより理解しやすくなります。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
public:
   vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {
      int n = arr.size();
      vector <int> pre(n + 1);
      for(int i = 1; i <=n; i++){
         pre[i] = pre[i - 1] ^ arr[i - 1];
      }
      vector <int> ans;
      for(int i = 0; i < queries.size(); i++){
         int l = queries[i][0];
         int r = queries[i][1];
         l++;
         r++;
         ans.push_back(pre[r] ^ pre[l - 1]);
      }
      return ans;
   }
};
main(){
   vector<int> v = {1,3,4,8};
   vector<vector<int>> v1 = {{0,1},{1,2},{0,3},{3,3}};
   Solution ob;
   print_vector(ob.xorQueries(v, v1));
}

入力

[1,3,4,8]
[[0,1],[1,2],[0,3],[3,3]]

出力

[2,7,14,8]

計算量の評価

前処理（累積XOR配列の構築）にO(n)、各クエリの処理にO(1)しかかからないため、全体の計算量はO(n + q)となります（n は配列の長さ、q はクエリの数）。各クエリで毎回範囲を走査する素朴なアプローチでは最悪O(n × q)かかるため、この手法により大幅な高速化が実現できます。