异或是可以用前缀和来维护的,因为异或有一个重要的性质x ^ x = 0
设preXor[i] = a[0] ^ a[1] ^ a[2] ^ a[3] ^ a[4] ^ ..... ^ a[i]
那么给定一个[l, r]范围的区间求a[l,r]的异或和,我们就可以利用前缀异或和来求解
preXor(l, r) = preXor(0, r) ^ preXor(0, l - 1) = preXor[r] ^ preXor[l - 1] = (a[0] ^ a[1] ^ a[2] ^ a[l - 1] ^ a[l] ^ a[l + 1] ^ .......... ^ a[r]) ^ (a[0] ^ a[1] ^ a[2] ^ .......... ^ a[l - 1]) = a[l] ^ a[l + 1] ^ ........ ^ a[r]
1310.子数组异或查询
解题思路
- 利用异或的性质,构建一个异或前缀和数组,来实现快速查询区间的异或和
代码实现
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* xorQueries(int* arr, int arrSize, int** queries, int queriesSize, int* queriesColSize, int* returnSize) {
int preXor[30005] = {0};
for (int i = 0; i < arrSize; i ++) {
preXor[i + 1] = arr[i] ^ preXor[i];
}
int* ans = (int*)malloc(sizeof(int) * queriesSize);
for (int i = 0; i < queriesSize; i ++) {
ans[i] = preXor[queries[i][0]] ^ preXor[queries[i][1] + 1];//前缀和下标从1开始数所以要加一
}
*returnSize = queriesSize;
return ans;
}
标签:preXor,queriesSize,前缀,int,异或,ans From: https://www.cnblogs.com/lwj1239/p/18108336