1310. 子数组异或查询

🎯 问题描述

描述：
给你一个正整数数组 arr（注意题目通常指非负整数），以及一个查询数组 queries，其中 queries[i] = [li, ri]。
对于每个查询 i，你必须计算 arr[li] ^ arr[li+1] ^ ... ^ arr[ri] 的结果（即从 li 到 ri 的所有元素的异或值）。
返回一个包含所有查询结果的数组。

说明：

这是一个位运算结合前缀和思想的问题。
核心策略：
- 异或运算满足结合律和交换律。
- 异或运算有一个极其重要的性质：自反性，即 $a \oplus a = 0$ 。
- 利用这一性质，我们可以通过前缀异或数组来快速计算任意区间的异或值，类似于前缀和中的区间减法。
示例：
示例 1：

输入：arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]
输出：[2,7,14,8]
解释：
- arr = [1,3,4,8]
- 前缀异或 pre = [0, 1, 1^3=2, 2^4=6, 6^8=14] -> [0, 1, 2, 6, 14]
- queries[0] = [0, 1]: pre[2] ^ pre[0] = 2 ^ 0 = 2
- queries[1] = [1, 2]: pre[3] ^ pre[1] = 6 ^ 1 = 7 (即 3^4)
- queries[2] = [0, 3]: pre[4] ^ pre[0] = 14 ^ 0 = 14
- queries[3] = [3, 3]: pre[4] ^ pre[3] = 14 ^ 6 = 8

💻 解题思路

思路1：前缀异或

核心逻辑

构建前缀异或数组 pre：
- pre[i+1] 表示 arr[0] 到 arr[i] 所有元素的异或值。
- 递推公式：pre[i+1] = pre[i] ^ arr[i]。
- 初始化 pre[0] = 0，方便处理从下标 0 开始的区间。
利用异或性质计算区间异或：
- 我们需要计算区间 [l, r] 的异或值： $arr[l] \oplus arr[l+1] \oplus ... \oplus arr[r]$ 。
- 我们知道 pre[r+1] 是 $arr[0] \oplus ... \oplus arr[l-1] \oplus arr[l] \oplus ... \oplus arr[r]$ 。
- 我们知道 pre[l] 是 $arr[0] \oplus ... \oplus arr[l-1]$ 。
- 利用 $a \oplus a = 0$ ，我们将两者异或： $pre[r+1] \oplus pre[l] = (arr[0] \oplus ... \oplus arr[l-1]) \oplus (arr[0] \oplus ... \oplus arr[l-1]) \oplus (arr[l] \oplus ... \oplus arr[r])$ $= 0 \oplus (arr[l] \oplus ... \oplus arr[r])$ $= arr[l] \oplus ... \oplus arr[r]$
- 因此，区间 [l, r] 的异或值等于 pre[r+1] ^ pre[l]。

代码实现

class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        n = len(arr)
        ans = []
        
        # 1. 构建前缀异或数组
        # pre[i+1] 表示 arr[0...i] 的异或值
        pre = [0] * (n + 1)
        
        for i, num in enumerate(arr):
            pre[i+1] = pre[i] ^ num
            
        # 2. 处理每个查询
        for l, r in queries:
            # 利用前缀异或计算区间 [l, r] 的异或值
            # 原理：A ^ A = 0，消去前缀部分
            c = pre[r+1] ^ pre[l]
            ans.append(c)
            
        return ans

📊 性能分析

时间复杂度： $O(N + Q)$ $O (N + Q)$
- 构建前缀异或数组： $O(N)$ ，其中 $N$ 是 arr 的长度。
- 处理查询： $O(Q)$ ，其中 $Q$ 是 queries 的长度。每个查询只需 $O(1)$ 时间进行异或运算。
- 总体线性时间，非常高效。
空间复杂度： $O(N)$ $O (N)$
- 需要一个长度为 $N+1$ 的 pre 数组来存储前缀异或值。
- 结果数组 ans 占用 $O(Q)$ 空间（通常不计入额外空间复杂度，因为是返回值）。

思考

异或的“减法”：
- 在前缀和中，区间和 = $Sum(r) - Sum(l-1)$ 。
- 在前缀异或中，区间异或 = $Xor(r) \oplus Xor(l-1)$ 。
- 这是因为异或运算中，加法和减法是同一个操作（即异或本身）。
pre 数组的定义：
- 定义 pre[0] = 0 是关键。
- 如果查询区间从 0 开始（即 l=0），我们需要计算 pre[r+1] ^ pre[0]。
- 因为 pre[0] = 0，且 $x \oplus 0 = x$ ，所以结果就是 pre[r+1]，逻辑正确。
为什么不用暴力法？
- 暴力法对于每个查询都遍历区间，时间复杂度 $O(Q \cdot N)$ 。
- 如果 $N=30000, Q=30000$ ，运算次数可达 $9 \times 10^8$ ，极易超时。
- 前缀异或将复杂度降为 $O(N+Q)$ ，能够轻松通过。
位运算的性质：
- $a \oplus a = 0$
- $a \oplus 0 = a$
- 结合律： $(a \oplus b) \oplus c = a \oplus (b \oplus c)$
- 这些性质是解决此类位运算区间问题的基础。