1310.子数组异或查询
https://leetcode-cn.com/problems/xor-queries-of-a-subarray/
难度：中等
题目：
有一个正整数数组arr，现给你一个对应的查询数组queries，其中queries[i] = [Li,Ri]。
对于每个查询i，请你计算从Li到Ri的XOR值（即arr[Li] xor arr[Li+1] xor ... xor arr[Ri]）作为本次查询的结果。
并返回一个包含给定查询queries所有结果的数组。
提示：
- 1 <= arr.length <= 3 *10^4
- 1 <= arr[i] <= 10^9
- 1 <= queries.length <= 3 * 10^4
- queries[i].length == 2
- 0 <= queries[i][0] <= queries[i][1] < arr.length
示例：
示例 1：
输入：arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]
输出：[2,7,14,8]
解释：
数组中元素的二进制表示形式是：
1 = 0001
3 = 0011
4 = 0100
8 = 1000
查询的 XOR 值为：
[0,1] = 1 xor 3 = 2
[1,2] = 3 xor 4 = 7
[0,3] = 1 xor 3 xor 4 xor 8 = 14
[3,3] = 8
示例 2：
输入：arr = [4,8,2,10], queries = [[2,3],[1,3],[0,0],[0,3]]
输出：[8,0,4,4]
分析
根据题目要求，我们每次需要计算queries区间内arr数组的XOR值。
这种重复的累加，第一时间需要考虑前缀和的思想，这样就将原本O(n) ** 2的复杂度降低为O(n)。
我们首先循环计算一次arr数组的XOR前缀和值
然后开始判断，如果left是从0开始的那么我们直接计算arr[right],
当left不等于零时，我们需要进行相减操作，这里需要注意，要减去的是left-1，因为left已经包含在计算内了。
解题：
class Solution:
def xorQueries(self, arr, queries):
ret = []
for i in range(1, len(arr)):
arr[i] ^= arr[i - 1]
for querie in queries:
left , right = querie
if left==0:
ret.append(arr[right])
else:
ret.append(arr[right] ^ arr[left- 1])
return ret
欢迎关注我的公众号: 清风Python，带你每日学习Python算法刷题的同时，了解更多python小知识。
我的个人博客：https://qingfengpython.cn
