1310 子数组异或查询

题目描述#

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

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

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

示例：

输入：arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]
输出：[2,7,14,8]
解释：
  [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

提示：

1 <= arr.length <= 3 * 10^4
1 <= arr[i] <= 10^5
1 <= queries.length <= 3 * 10^4
queries[i].length == 2
0 <= queries[i][0] <= queries[i][1] < arr.length

知识边界#

异或运算（XOR）的核心性质#

本题的核心在于利用 XOR 的以下两条性质：

性质	公式
自反性	`a XOR a = 0`
恒等性	`a XOR 0 = a`
交换律 & 结合律	顺序无关，可任意组合

由自反性与结合律可以推出一个关键结论：

prefix[R+1] XOR prefix[L] = arr[L] XOR arr[L+1] XOR ... XOR arr[R]

其中 prefix[i] = arr[0] XOR arr[1] XOR ... XOR arr[i-1]。

这与前缀和的思路完全一致，只是加法换成了 XOR。

前缀异或数组（Prefix XOR）#

定义长度为 n+1 的前缀异或数组 prefix，其中：

prefix[0] = 0
prefix[i] = prefix[i-1] XOR arr[i-1]   （i 从 1 开始）

则区间 [L, R] 的 XOR 结果为：

prefix[R+1] XOR prefix[L]

证明：

prefix[R+1] = arr[0] XOR ... XOR arr[R]
prefix[L]   = arr[0] XOR ... XOR arr[L-1]

prefix[R+1] XOR prefix[L]
  = (arr[0] XOR ... XOR arr[L-1] XOR arr[L] XOR ... XOR arr[R])
    XOR
    (arr[0] XOR ... XOR arr[L-1])
  = arr[L] XOR ... XOR arr[R]   ← 前面相同的部分两两抵消

Go 语言中 XOR 运算符#

Go 中使用 ^ 表示按位异或：

a := 0b0110  // 6
b := 0b0011  // 3
c := a ^ b   // 0b0101 = 5

构建前缀异或数组示例：

arr := []int{1, 3, 4, 8}
prefix := make([]int, len(arr)+1)
for i, x := range arr {
    prefix[i+1] = prefix[i] ^ x
}
// prefix = [0, 1, 2, 6, 14]

查询区间 [1, 2]：

L, R := 1, 2
result := prefix[R+1] ^ prefix[L]
// prefix[3] ^ prefix[1] = 6 ^ 1 = 7  ✓

思路#

思路一：前缀异或数组（最优解）#

朴素思路的问题： 对每次查询 [L, R] 直接遍历 arr[L..R] 逐一 XOR，单次查询时间为 O(n)，多次查询总复杂度为 O(n * q)，当 n 和 q 都达到 3 * 10^4 时共需约 9 * 10^8 次操作，会超时。

优化方向： 预处理前缀异或数组，将每次查询的时间压缩到 O(1)。

具体步骤：

构建长度为 n+1 的 prefix 数组，prefix[0] = 0，prefix[i] = prefix[i-1] ^ arr[i-1]。
对每个查询 [L, R]，答案为 prefix[R+1] ^ prefix[L]。
将所有查询结果收集到 ans 数组中返回。

时间复杂度：

预处理：O(n)
每次查询：O(1)
总计：O(n + q)，其中 n 为数组长度，q 为查询次数

空间复杂度： O(n)，用于存储前缀异或数组。

代码#

func xorQueries(arr []int, queries [][]int) []int {
	// 构建前缀异或数组，长度比 arr 多 1，prefix[0] = 0
	prefix := make([]int, len(arr)+1)
	for i, x := range arr {
		prefix[i+1] = prefix[i] ^ x
	}

	// 对每个查询 [L, R]，利用前缀异或公式 O(1) 得到结果
	ans := make([]int, len(queries))
	for i, qu := range queries {
		L, R := qu[0], qu[1]
		ans[i] = prefix[R+1] ^ prefix[L]
	}
	return ans
}