C ++中子数组的XOR查询
假设我们有正整数的数组arr和查询[i]=[Li，Ri]的数组查询，对于每个查询，i都会计算从Li到Ri的元素的XOR（即arr[Li]XORarr[Li+1]xor...xorarr[Ri]）。我们必须找到包含给定查询结果的数组。因此，如果输入类似于-[[1,3,4,8]，而查询类似于[[0,1]，[1,2]，[0,3]，[3,3]]，则结果将为[2,7,14,8]。这是因为数组中元素的二进制表示形式为−1=0001、3=0011、4=0100和8=1000。则查询的XOR值为−[0,1]=1xor3=2[1,2]=3xor4=7，[0,3]=1xor3xor4xor8=14和[3,3]=8
为了解决这个问题，我们将遵循以下步骤-
n：=arr的大小
定义一个大小为n+1的称为pre的数组，然后填充pre，使得pre[i]：=pre[i–1]XORarr[i–1]
定义另一个数组
对于0到查询数量范围内的i–1
l：=查询[i，0]，r：=查询[i，1]
将l和r增加1
将pre[r]XORpre[1-1]插入ans
返回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]