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