在給定范圍內出現偶數次的數字的 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`是查詢的總數。 * * * * * *