LeetCode 1310. 子数组异或查询
目录
题目描述
题意分析
给定一个正整数数组
arr和一批查询queries，每个查询是一对闭区间端点[l, r]。要为每个查询算出arr[l] ^ arr[l+1] ^ ... ^ arr[r]，并按查询顺序把结果放进一个数组返回。题目的核心特征是多次区间查询、数组本身不变。数组只读这一条极其重要：它意味着可以先花一次代价把整个数组「加工」成某种便于查询的形态，之后每个查询都能吃这份加工结果的红利，而不必担心中途被修改打乱。
约束给出
arr.length和queries.length都可达 $3 \times 10^4$，元素值小于 $10^9$。两个规模同阶且都是万级：如果每个查询都老老实实遍历区间，最坏情况是把整个数组扫一遍，总量接近 $9 \times 10^8$，明显超时。这组约束是在明示单次查询必须做到常数时间。数组元素都是正整数、区间保证
0 <= l <= r < arr.length，所以不存在空区间、不存在越界、不存在负数带来的符号位麻烦。边界要留意三点：
l == r时答案就是arr[l]本身，不是 0；查询下标是闭区间，右端点要取到；返回数组的长度等于查询个数而不是数组长度，且顺序必须与输入查询一一对应。
解法：前缀异或
核心思路
数组不修改，却要回答很多区间查询，适合先做一次前缀预处理。异或满足
x ^ x = 0、x ^ 0 = x，因此一段前缀可以用再次异或的方式抵消。定义
prefix[i]为arr前i个元素的异或值，prefix[0] = 0。递推为：
prefix[i + 1] = prefix[i] ^ arr[i]。对闭区间
[left, right]，prefix[right + 1]同时包含区间左侧前缀与目标区间，再异或prefix[left]后，左侧元素各出现两次并全部抵消：
xor(left, right) = prefix[right + 1] ^ prefix[left]。不变量：构造到下标
i后，prefix[i]恰好等于前i个元素的异或。多出的空前缀使left = 0和单元素区间都无需特判。正确性：对任意查询，
arr[0..left-1]在两个前缀中各出现一次，异或后消失；arr[left..right]只出现在prefix[right+1]中，恰好保留。查询之间互不影响，按原顺序写入结果即可。
解题步骤
- 创建长度为
n + 1的prefix，保留prefix[0] = 0。- 遍历
arr，按prefix[i + 1] = prefix[i] ^ arr[i]构造前缀异或。- 对每个
[left, right]，计算prefix[right + 1] ^ prefix[left]。- 按查询原顺序返回结果。
样例
arr = [1,3,4,8]得到prefix = [0,1,2,6,14]。查询[1,2]的答案为prefix[3] ^ prefix[1] = 6 ^ 1 = 7；查询[3,3]为14 ^ 6 = 8。边界上，
left = 0时空前缀为 0；left = right时相邻两个前缀只相差该元素；重复查询也只是重复做一次常数时间计算。
代码实现
class Solution {
public int[] xorQueries(int[] arr, int[][] queries) {
int[] prefix = new int[arr.length + 1];
for (int i = 0; i < arr.length; i++) {
prefix[i + 1] = prefix[i] ^ arr[i];
}
int[] answer = new int[queries.length];
for (int i = 0; i < queries.length; i++) {
int left = queries[i][0];
int right = queries[i][1];
answer[i] = prefix[right + 1] ^ prefix[left];
}
return answer;
}
}
func xorQueries(arr []int, queries [][]int) []int {
prefix := make([]int, len(arr)+1)
for i, value := range arr {
prefix[i+1] = prefix[i] ^ value
}
answer := make([]int, len(queries))
for i, query := range queries {
left, right := query[0], query[1]
answer[i] = prefix[right+1] ^ prefix[left]
}
return answer
}
复杂度分析
- 时间复杂度：$O(n + q)$，其中
n是数组长度，q是查询数；预处理 $O(n)$，每个查询 $O(1)$。- 空间复杂度：$O(n)$，用于前缀异或数组；返回数组不计入额外空间。
关键点总结
- “静态数组 + 多次区间查询”是前缀预处理的典型信号。
prefix[i]表示前i个元素，而不是截至下标i，这是公式下标的依据。- 异或的逆运算仍是异或，因此区间公式使用
^抵消公共前缀。- 长度
n + 1的空前缀统一处理left = 0。
易错点总结
- 右端点漏加 1：
prefix[right] ^ prefix[left]会漏掉arr[right]；单元素查询甚至得到 0。- 左端点写成
left - 1：当前前缀定义下应抵消前left个元素，left = 0还会产生负下标。- 把前缀定义和公式混用：若
prefix[i]改成“截至下标i”，就不能继续套用本文公式。- 结果数组按
arr.length创建：查询数与数组长度无关，应使用queries.length。- 逐查询扫描区间：最坏会退化为 $O(nq)$，丢失预处理的意义。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 303. 区域和检索 - 数组不可变 | 简单 | 把异或换成求和的同款模板，重点是构造函数里完成预处理 |
| 304. 二维区域和检索 - 矩阵不可变 | 中等 | 前缀升到二维，查询需要容斥四个角，多减的一块要补回来 |
| 307. 区域和检索 - 数组可修改 | 中等 | 数组可改导致前缀失效，必须换树状数组或线段树支持 $O(\log n)$ 单点更新 |
| 560. 和为 K 的子数组 | 中等 | 前缀值不再直接查询而是配对计数，需要哈希表且先查后写 |
| 974. 和可被 K 整除的子数组 | 中等 | 按前缀和的余数分桶，负数取模要先加 k 再取模 |
| 523. 连续的子数组和 | 中等 | 同余分桶但要求子数组长度至少为 2，需记录余数首次出现的下标 |
| 525. 连续数组 | 中等 | 把 0 映射成 -1 后转化为「前缀和相等」，求最长而非计数 |
| 1248. 统计「优美子数组」 | 中等 | 前缀统计奇数个数，也可用滑动窗口做差求解 |
| 930. 和相同的二元子数组 | 中等 | 值域仅 0/1，前缀计数可退化成计数数组，还能用「恰好等于 = 至多之差」 |
| 1442. 形成两个异或相等数组的三元组数目 | 中等 | 由 pre[i] == pre[k+1] 推出中间任意分割点都成立，答案退化成配对计数 |
| 1177. 构建回文串检测 | 中等 | 用 26 位掩码做前缀异或，靠奇数字符个数判断能否重排成回文 |
| 421. 数组中两个数的最大异或值 | 中等 | 不是区间查询，而是用 01 字典树按位贪心找最大异或对 |
| 136. 只出现一次的数字 | 简单 | 同样吃异或的自反性，全体异或后成对元素自动抵消 |
| 1094. 拼车 | 中等 | 差分数组是前缀和的逆操作，适合区间批量修改后一次性求值 |