给定一个由n个整数组成的数组arr[]和一些查询。每个查询的形式为（L，R），其中L和R是数组的索引。查找子数组arr[L…R]的异或值，即当范围[L，R]中的所有元素都是异或时获得的值。假设基于0的索引，每个数组元素都是32位无符号整数。 例如：
null
Input : arr[] = {2, 5, 1, 6, 1, 2, 5} L = 1, R = 4Output : 3The XOR value of arr[1...4] is 3.Input : arr[] = {2, 5, 1, 6, 1, 2, 5} L = 0, R = 6Output : 6The XOR value of arr[0...6] is 6.
方法： A. 易于理解的 解决方案是为每个查询从索引L遍历给定数组到索引R。这导致处理每个查询的时间复杂度为O（n）。如果有q查询，那么所需的总时间将是O（q*n）。对于大量查询和大型数组，此解决方案不是最优的。 一 有效率的 解决方案是首先对数组进行预处理。两个观察结果将很有帮助：
- 问题陈述中提到，每个数组元素都是32位无符号数。因此，结果也将是一个32位无符号数。
- 当对多个位进行异或运算时，如果有奇数个1，则结果为1，否则结果为0。
使用观察1，创建一个大小为32*n的二维阵列cnt。该阵列将用于存储1s的计数。元素cnt[i][j]表示索引j之前第i位的1s数的计数，即在第i位位置的子阵列arr[0..j]中存在多少1s。 根据观察结果2，为了获得异或值，需要找到子阵列arr[L…R]中所有32位位置的1数。这可以在cnt阵列的帮助下完成。子阵列arr[L…R]中第i位位置的位数为cnt[i][R]–cnt[i][L-1]。如果第i位的1s数为奇数，则将在结果中设置第i位。然后，如果设置了第i位，则可通过将第i位对应的2的幂相加来获得结果。 根据该算法处理每个查询将需要O（32），即恒定时间。创建cnt阵列的预处理阶段需要O（n）个时间。因此，对于q查询，该解决方案的总时间复杂度为O（n+q）。 实施：
C++
#include <bits/stdc++.h> using namespace std; // Function to preprocess the array and find count of // number of ones upto jth index for ith bit. void preprocess( int arr[], int n, vector<vector< int > >& cnt) { int i, j; // Run a loop for each bit position from // 0 to 32. for (i = 0; i < 32; i++) { cnt[i][0] = 0; for (j = 0; j < n; j++) { if (j > 0) { // store previous count of 1s // for ith bit position. cnt[i][j] = cnt[i][j - 1]; } // Check if ith bit for jth element // of array is set or not. If it is // set then increase count of 1 for // ith bit by 1. if (arr[j] & (1 << i)) cnt[i][j]++; } } } // Function to find XOR value for a range of array elements. int findXOR( int L, int R, const vector<vector< int > > cnt) { // variable to store final answer. int ans = 0; // variable to store number of 1s for ith bit // in the range L to R. int noOfOnes; int i, j; // Find number of 1s for each bit position from 0 // to 32. for (i = 0; i < 32; i++) { noOfOnes = cnt[i][R] - ((L > 0) ? cnt[i][L - 1] : 0); // If number of 1s are odd then in the result // ith bit will be set, i.e., 2^i will be present in // the result. Add 2^i in ans variable. if (noOfOnes & 1) { ans += (1 << i); } } return ans; } int main() { int arr[] = { 2, 5, 1, 6, 1, 2, 5 }; int n = sizeof (arr) / sizeof (arr[0]); vector<vector< int > > cnt(32, vector< int >(n)); preprocess(arr, n, cnt); int L = 1; int R = 4; cout << findXOR(L, R, cnt); return 0; } |
JAVA
class GFG { // Function to preprocess the array and find count of // number of ones upto jth index for ith bit. static void preprocess( int arr[], int n, int [][] cnt) { int i, j; // Run a loop for each bit position from // 0 to 32. for (i = 0 ; i < 32 ; i++) { cnt[i][ 0 ] = 0 ; for (j = 0 ; j < n; j++) { if (j > 0 ) { // store previous count of 1s // for ith bit position. cnt[i][j] = cnt[i][j - 1 ]; } // Check if ith bit for jth element // of array is set or not. If it is // set then increase count of 1 for // ith bit by 1. if ((arr[j] & ( 1 << i)) >= 1 ) cnt[i][j]++; } } } // Function to find XOR value for a range of array elements. static int findXOR( int L, int R, int [][] cnt) { // variable to store final answer. int ans = 0 ; // variable to store number of 1s for ith bit // in the range L to R. int noOfOnes; int i, j; // Find number of 1s for each bit position from 0 // to 32. for (i = 0 ; i < 32 ; i++) { noOfOnes = cnt[i][R] - ((L > 0 ) ? cnt[i][L - 1 ] : 0 ); // If number of 1s are odd then in the result // ith bit will be set, i.e., 2^i will be present in // the result. Add 2^i in ans variable. if (noOfOnes % 2 == 1 ) { ans += ( 1 << i); } } return ans; } // Driver code public static void main(String[] args) { int arr[] = { 2 , 5 , 1 , 6 , 1 , 2 , 5 }; int n = arr.length; int [][] cnt = new int [ 32 ][n]; preprocess(arr, n, cnt); int L = 1 ; int R = 4 ; System.out.print(findXOR(L, R, cnt)); } } // This code is contributed by Rajput-Ji |
Python3
# Function to preprocess the array and # find count of number of ones upto # jth index for ith bit. def preprocess(arr, n, cnt): # Run a loop for each bit position # from 0 to 32. for i in range ( 32 ): cnt[i][ 0 ] = 0 for j in range (n): if (j > 0 ): # store previous count of 1s # for ith bit position. cnt[i][j] = cnt[i][j - 1 ] # Check if ith bit for jth element # of array is set or not. If it is # set then increase count of 1 for # ith bit by 1. if (arr[j] & ( 1 << i)): cnt[i][j] + = 1 # Function to find XOR value # for a range of array elements. def findXOR(L, R, cnt): # variable to store final answer. ans = 0 # variable to store number of 1s # for ith bit in the range L to R. noOfOnes = 0 # Find number of 1s for each # bit position from 0 to 32. for i in range ( 32 ): if L > 0 : noOfOnes = cnt[i][R] - cnt[i][L - 1 ] else : noOfOnes = cnt[i][R] # If number of 1s are odd then in the result # ith bit will be set, i.e., 2^i will be # present in the result. Add 2^i in ans variable. if (noOfOnes & 1 ): ans + = ( 1 << i) return ans # Driver Code arr = [ 2 , 5 , 1 , 6 , 1 , 2 , 5 ] n = len (arr) cnt = [[ 0 for i in range (n)] for i in range ( 32 )] preprocess(arr, n, cnt) L = 1 R = 4 print (findXOR(L, R, cnt)) # This code is contributed by Mohit Kumar |
C#
using System; class GFG { // Function to preprocess the array and find count of // number of ones upto jth index for ith bit. static void preprocess( int []arr, int n, int [,] cnt) { int i, j; // Run a loop for each bit position from // 0 to 32. for (i = 0; i < 32; i++) { cnt[i, 0] = 0; for (j = 0; j < n; j++) { if (j > 0) { // store previous count of 1s // for ith bit position. cnt[i, j] = cnt[i, j - 1]; } // Check if ith bit for jth element // of array is set or not. If it is // set then increase count of 1 for // ith bit by 1. if ((arr[j] & (1 << i)) >= 1) cnt[i, j]++; } } } // Function to find XOR value for a range of array elements. static int findXOR( int L, int R, int [,] cnt) { // variable to store readonly answer. int ans = 0; // variable to store number of 1s for ith bit // in the range L to R. int noOfOnes; int i; // Find number of 1s for each bit position from 0 // to 32. for (i = 0; i < 32; i++) { noOfOnes = cnt[i, R] - ((L > 0) ? cnt[i, L - 1] : 0); // If number of 1s are odd then in the result // ith bit will be set, i.e., 2^i will be present in // the result. Add 2^i in ans variable. if (noOfOnes % 2 == 1) { ans += (1 << i); } } return ans; } // Driver code public static void Main(String[] args) { int []arr = { 2, 5, 1, 6, 1, 2, 5 }; int n = arr.Length; int [,] cnt = new int [32, n]; preprocess(arr, n, cnt); int L = 1; int R = 4; Console.Write(findXOR(L, R, cnt)); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // Function to preprocess the array and find count of // number of ones upto jth index for ith bit. function preprocess(arr, n, cnt) { var i, j; // Run a loop for each bit position from // 0 to 32. for (i = 0; i < 32; i++) { cnt[i][0] = 0; for (j = 0; j < n; j++) { if (j > 0) { // store previous count of 1s // for ith bit position. cnt[i][j] = cnt[i][j - 1]; } // Check if ith bit for jth element // of array is set or not. If it is // set then increase count of 1 for // ith bit by 1. if (arr[j] & (1 << i)) cnt[i][j]++; } } } // Function to find XOR value for a range of array elements. function findXOR(L, R, cnt) { // variable to store final answer. var ans = 0; // variable to store number of 1s for ith bit // in the range L to R. var noOfOnes; var i, j; // Find number of 1s for each bit position from 0 // to 32. for (i = 0; i < 32; i++) { noOfOnes = cnt[i][R] - ((L > 0) ? cnt[i][L - 1] : 0); // If number of 1s are odd then in the result // ith bit will be set, i.e., 2^i will be present in // the result. Add 2^i in ans variable. if (noOfOnes & 1) { ans += (1 << i); } } return ans; } var arr = [ 2, 5, 1, 6, 1, 2, 5 ]; var n = arr.length; var cnt = Array.from( Array(32), () => Array(n)); preprocess(arr, n, cnt); var L = 1; var R = 4; document.write( findXOR(L, R, cnt)); // This code is contributed by itsok. </script> |
输出：
3
时间复杂性： O（n+q） 辅助空间： O（n）
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
