发表于 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 - 构建回文串检测：前缀和 + 状态压缩表示各个字符出现次数的奇偶性

• LC 题目链接