JZX轻语：简
LeetCode 1310 - 子数组异或查询
发表于2024年07月25日
前缀异或满足查分的特性，记pre_xor[i]为数组前i个元素的异或值，即对于i > j，我们有pre_xor[i] ^ pre_xor[j] = (pre_xor[j] ^ arr[j+1] ^ ... ^ arr[i]) ^ pre_xor[j] = arr[j+1] ^ ... ^ arr[i]。我们可以采取类似于前缀和的方法，预处理出前缀异或数组pre_xor，然后对于每个查询[left, right]，pre_xor[right+1] ^ pre_xor[left - 1]即为所求。
class Solution:
def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
prefix = [0] * len(arr)
for i, num in enumerate(arr):
prefix[i] = (prefix[i - 1] if i > 0 else 0) ^ num
ans = []
for l, r in queries:
ans.append(prefix[r] ^ (prefix[l - 1] if l > 0 else 0))
return ans类似题目：
LeetCode 1738 - 找出第K大的异或坐标值：二维前缀和+异或版本
LeetCode 1177 - 构建回文串检测：前缀和 + 状态压缩表示各个字符出现次数的奇偶性