子数组异或查询

难度: Medium

有一个正整数数组 arr，现给你一个对应的查询数组 queries，其中 queries[i] = [L_i,R_i]。

对于每个查询 i，请你计算从 L_i 到 R_i 的 XOR 值（即 arr[L_i] xor arr[L_i+1] xor ... xor arr[R_i]）作为本次查询的结果。

并返回一个包含给定查询 queries 所有结果的数组。

示例 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]

提示：

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

Submission

运行时间: 36 ms

内存: 27.7 MB

class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        n = len(arr)
        prefix = [0] * (n + 1)
        for i in range(1, n + 1):
            prefix[i] = prefix[i - 1] ^ arr[i - 1]
        ans = [0] * len(queries)
        for i, (start, end) in enumerate(queries):
            ans[i] = prefix[end + 1] ^ prefix[start]
        return ans

Explain

为了高效地回答多个查询，本题解采用了前缀异或数组的技术。首先构建一个前缀数组 prefix，其中 prefix[i] 表示从 arr[0] 到 arr[i-1] 的元素的异或和。使用这个前缀数组可以在 O(1) 的时间内计算任何子数组的异或和。具体来说，子数组 arr[L] 到 arr[R] 的异或和可以表示为 prefix[R+1] ^ prefix[L]，这是因为 prefix[R+1] 包含了 arr[0] 到 arr[R] 的异或结果，而 prefix[L] 包含了 arr[0] 到 arr[L-1] 的异或结果，两者异或后刚好可以得到 arr[L] 到 arr[R] 的异或结果。

时间复杂度: O(n + q)

空间复杂度: O(n + q)

class Solution:
    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:
        n = len(arr)
        # 初始化前缀异或数组，多一个元素便于处理边界条件
        prefix = [0] * (n + 1)
        # 构建前缀异或数组
        for i in range(1, n + 1):
            prefix[i] = prefix[i - 1] ^ arr[i - 1]
        # 初始化结果数组
        ans = [0] * len(queries)
        # 计算每个查询的异或结果
        for i, (start, end) in enumerate(queries):
            ans[i] = prefix[end + 1] ^ prefix[start]
        return ans

Explore

初始化prefix数组的长度为n+1而不是n是为了方便处理边界情况，特别是当子数组的起始索引L为0时。prefix数组中的每个元素prefix[i]代表从数组arr的开始到arr[i-1]的元素的异或和。因此，prefix[0]需要被设为0，这样可以直接使用prefix[R+1]来获取从arr[0]到arr[R]的异或和。如果只初始化为n，那么计算从arr[0]到arr[R]的异或和时，需要做额外的条件判断，增加了复杂度。

前缀异或数组中prefix[i]的计算方法是将前一个元素的前缀异或结果prefix[i-1]与当前数组元素arr[i-1]进行异或。这种方法的理解基于异或运算的性质：任何数与自身异或的结果为0且异或运算具有交换律和结合律。通过使用prefix[i-1] ^ arr[i-1]，我们实际上是将arr[0]到arr[i-2]的异或结果与arr[i-1]进行异或，从而得到从arr[0]到arr[i-1]的所有元素的异或和，这样可以递归地构建整个prefix数组。

在构建前缀异或数组时，prefix[0]被初始化为0是关键的边界条件处理方式。这是因为prefix[0]代表了空子数组的异或结果，也即没有任何元素的异或结果应为0。这样的初始化使得当我们需要计算从arr[0]到某个元素arr[R]的异或和时，可以直接使用prefix[R+1]，因为prefix[R+1]实际上包含了arr[0]到arr[R]的异或结果。如果没有将prefix[0]初始化为0，那么在计算整个数组的异或结果时就需要特别处理这种情况。

这个计算方式基于异或运算的性质，特别是异或运算的撤销性质（任何数与自身异或结果为0）和结合律。prefix数组中，prefix[R+1]代表从arr[0]到arr[R]的元素的异或结果，而prefix[L]代表从arr[0]到arr[L-1]的元素的异或结果。当使用prefix[R+1] ^ prefix[L]时，arr[0]到arr[L-1]的部分被“撤销”，只留下arr[L]到arr[R]的异或和。这样我们可以在常数时间O(1)内得到任意子数组的异或结果，极大地提高了查询效率。