C ++中子数组的XOR

在此问题中，我们给了arr []和一些查询，查询范围在数组中的L到R之间。我们的任务是打印L到R之间的子数组的XOR。

让我们举个例子来了解这个问题，

输入-数组= {1，4，5，7，2，9} L = 1，R = 5

输出-

说明-4 ^ 5 ^ 7 ^ 2 ^ 9

• 为了解决这个问题，我们将基于以下观察结果创建一个数组，

• 我们将对多个位进行XOR，如果奇数个数为1，则结果将为1，否则结果为0。

现在，我们将创建一个二维数组计数，该计数将存储1s的计数。值count [i] [j]是位置ij的1的数目的计数，它是位i位置的子数组arr [0..j]中存在的1的数目。使用计数数组可以找到子数组arr [L..R]所有位的1。查找arr [L ... R] = count [i] [R]-count [i] [L-1]的公式。如果1的数目为奇数，则结果中将设置第i位。假设设置位为第i位，则可以通过将与第i位相对应的2的幂进行求和来获得最终结果。

显示我们解决方案实施情况的程序，

示例

#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