在给定范围内出现偶数次的数字的 XOR · GeeksForGeeks 中文系列教程

# 在给定范围内出现偶数次的数字的 XOR > 原文： [https://www.geeksforgeeks.org/xor-numbers-appeared-even-number-times-given-range/](https://www.geeksforgeeks.org/xor-numbers-appeared-even-number-times-given-range/) 给定一个大小为`N`和`Q`的数字数组。每个查询或范围可以由`L`（`LeftIndex`）和`R`（`RightIndex`）表示。查找在给定范围内出现偶数次的数字的 XOR 和。 **前提**： [查询给定范围内不同数字的数量。](https://www.geeksforgeeks.org/queries-number-distinct-elements-subarray/) | [用于范围查询的分段树](https://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/) 例子： ``` Input : arr[] = { 1, 2, 1, 3, 3, 2, 3 } Q = 5 L = 3, R = 6 L = 3, R = 4 L = 0, R = 2 L = 0, R = 6 L = 0, R = 4 Output : 0 3 1 3 2 ``` **上面示例的说明**：在查询 1 中，没有数字出现偶数次。因此 XOR 和为 0。在查询 2 中，`{3}`出现偶数次。 XOR 和为 3。在查询 3 中，`{1}`出现偶数次。 XOR 和为 1。在查询 4 中，`{1, 2}`出现偶数次。 XOR 和为`1 xor 2 = 3`。在查询 5 中，`{1, 3}`出现偶数次。 XOR 和是`1 xor 3 = 2`。 [段树](https://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/)或[二叉索引树](https://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/)可用于有效解决此问题。 **方法**：首先，很容易注意到查询的答案是查询范围内所有元素的 XOR 和，与查询范围内的**不同**元素的 XOR 和的 XOR（因为将元素与其自身进行 XOR 运算得出空值）。使用前缀 XOR 和求出查询范围内所有数字的 XOR 和。 **查找范围内不同元素的 XOR 和**： [给定范围](https://www.geeksforgeeks.org/queries-number-distinct-elements-subarray/)的子数组中不同元素的数量。现在，回到我们的主要问题，只需将赋值`BIT[i] = 1`更改为`BIT[i] = arr[i]`并计算 XOR 和而不是总和。 **以下是在 CPP** 中使用**二叉索引树**的实现 ``` // CPP Program to Find the XOR-sum // of elements that appeared even // number of times within a range #include <bits/stdc++.h> using namespace std; /* structure to store queries L --> Left Bound of Query R --> Right Bound of Query idx --> Query Number */ struct que { int L, R, idx; }; // cmp function to sort queries // according to R bool cmp(que a, que b) { if (a.R != b.R) return a.R < b.R; else return a.L < b.L; } /* N --> Number of elements present in input array. BIT[0..N] --> Array that represents Binary Indexed Tree*/ // Returns XOR-sum of arr[0..index]. This // function assumes that the array is // preprocessed and partial sums of array // elements are stored in BIT[]. int getSum(int BIT[], int index) { // Iniialize result int xorSum = 0; // index in BITree[] is 1 more than // the index in arr[] index = index + 1; // Traverse ancestors of BIT[index] while (index > 0) { // Take XOR of current element // of BIT to xorSum xorSum ^= BIT[index]; // Move index to parent node // in getSum View index -= index & (-index); } return xorSum; } // Updates a node in Binary Index Tree // (BIT) at given index in BIT. The // given value 'val' is xored to BIT[i] // and all of its ancestors in tree. void updateBIT(int BIT[], int N, int index, int val) { // index in BITree[] is 1 more than // the index in arr[] index = index + 1; // Traverse all ancestors and // take xor with 'val' while (index <= N) { // Take xor with 'val' to // current node of BIT BIT[index] ^= val; // Update index to that of // parent in update View index += index & (-index); } } // Constructs and returns a Binary Indexed // Tree for given array of size N. int* constructBITree(int arr[], int N) { // Create and initialize BITree[] as 0 int* BIT = new int[N + 1]; for (int i = 1; i <= N; i++) BIT[i] = 0; return BIT; } // Function to answer the Queries void answeringQueries(int arr[], int N, que queries[], int Q, int BIT[]) { // Creating an array to calculate // prefix XOR sums int* prefixXOR = new int[N + 1]; // map for coordinate compression // as numbers can be very large but we // have limited space map<int, int> mp; for (int i = 0; i < N; i++) { // If A[i] has not appeared yet if (!mp[arr[i]]) mp[arr[i]] = i; // calculate prefixXOR sums if (i == 0) prefixXOR[i] = arr[i]; else prefixXOR[i] = prefixXOR[i - 1] ^ arr[i]; } // Creating an array to store the // last occurrence of arr[i] int lastOcc[1000001]; memset(lastOcc, -1, sizeof(lastOcc)); // sort the queries according to comparator sort(queries, queries + Q, cmp); // answer for each query int res[Q]; // Query Counter int j = 0; for (int i = 0; i < Q; i++) { while (j <= queries[i].R) { // If last visit is not -1 update // arr[j] to set null by taking // xor with itself at the idx // equal lastOcc[mp[arr[j]]] if (lastOcc[mp[arr[j]]] != -1) updateBIT(BIT, N, lastOcc[mp[arr[j]]], arr[j]); // Setting lastOcc[mp[arr[j]]] as j and // updating the BIT array accordingly updateBIT(BIT, N, j, arr[j]); lastOcc[mp[arr[j]]] = j; j++; } // get the XOR-sum of all elements within // range using precomputed prefix XORsums int allXOR = prefixXOR[queries[i].R] ^ prefixXOR[queries[i].L - 1]; // get the XOR-sum of distinct elements // within range using BIT query function int distinctXOR = getSum(BIT, queries[i].R) ^ getSum(BIT, queries[i].L - 1); // store the final answer at the numbered query res[queries[i].idx] = allXOR ^ distinctXOR; } // Output the result for (int i = 0; i < Q; i++) cout << res[i] << endl; } // Driver program to test above functions int main() { int arr[] = { 1, 2, 1, 3, 3, 2, 3 }; int N = sizeof(arr) / sizeof(arr[0]); int* BIT = constructBITree(arr, N); // structure of array for queries que queries[5]; // Intializing values (L, R, idx) to queries queries[0].L = 3; queries[0].R = 6, queries[0].idx = 0; queries[1].L = 3; queries[1].R = 4, queries[1].idx = 1; queries[2].L = 0; queries[2].R = 2, queries[2].idx = 2; queries[3].L = 0; queries[3].R = 6, queries[3].idx = 3; queries[4].L = 0; queries[4].R = 4, queries[4].idx = 4; int Q = sizeof(queries) / sizeof(queries[0]); // answer Queries answeringQueries(arr, N, queries, Q, BIT); return 0; } ``` **输出**： ``` 0 3 1 3 2 ``` **时间复杂度**： `O(Q * Log(N))`，其中`N`是数组的大小，`Q`是查询的总数。 * * * * * *