LeetCode-Go 题解 1310：前缀异或（Prefix XOR）将子数组 XOR 查询降为 O(1)

LeetCode-Go 题解 1310前缀异或Prefix XOR将子数组 XOR 查询降为 O(1)【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本文以 LeetCode 第 1310 题《XOR Queries of a Subarray》为核心讲解如何利用前缀异或Prefix XOR思想将每次区间异或查询的耗时从 O(n) 降至 O(1)整体时间复杂度降为 O(n)。文章完整继承 LeetCode-Go 仓库中该题题解文档 README.md 的题目定义、示例与推导过程并结合仓库内 实现源码 与 单元测试 做源码级印证读完即可独立复现并验证该解法。题目子数组的 XOR 查询给定一个正整数数组arr与一个查询数组queries其中queries[i] [Li, Ri]。对于每个查询i需要计算从下标Li到Ri的按位异或结果即arr[Li] xor arr[Li1] xor ... xor arr[Ri]最终返回一个数组包含queries中所有查询的结果。XOR异或运算满足按位运算的交换律与结合律且对二进制位逐位独立这正是本题可以借助前缀思想优化的前提。示例分析示例 1Input: arr [1,3,4,8], queries [[0,1],[1,2],[0,3],[3,3]] Output: [2,7,14,8]各元素的二进制表示如下1 0001 3 0011 4 0100 8 1000四个查询对应的异或计算过程为[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 8注意最后一个查询[3,3]是单元素区间结果就是arr[3]本身这验证了区间长度为 1 时结果等于该元素这一边界情况。示例 2Input: arr [4,8,2,10], queries [[2,3],[1,3],[0,0],[0,3]] Output: [8,0,4,4]其中[1,3] 8 xor 2 xor 10 0说明非零元素的区间异或结果完全可能为 0这正是异或运算区别于加法的重要特性。约束条件与复杂度预判题目给出的约束是算法设计的关键输入1 arr.length 3 * 10^41 arr[i] 10^91 queries.length 3 * 10^4queries[i].length 20 queries[i][0] queries[i][1] arr.lengtharr与queries的数量级都达到3 * 10^4。若对每个查询朴素地遍历区间求异或单次查询为 O(n)总复杂度为 O(n × q)最坏约9 × 10^8次运算在严格的时间限制下很容易超时。因此必须寻找更高效的做法——这正是前缀异或的用武之地。解题思路从前缀和到前缀异或此题求区间异或很容易让人联想到区间求和。区间求和利用前缀和Prefix Sum可以使得单次查询从 O(n) 降为 O(1)。那么区间异或能否也采用类似前缀和的思想呢答案是肯定的。关键依据是异或运算的两个基本性质x ^ x 0相同值异或抵消为 0x ^ 0 x任何值与 0 异或保持不变设前缀异或数组xors[i] arr[0] ^ arr[1] ^ ... ^ arr[i]即前 i1 个元素的异或则任意区间[left, right]的异或可以推导如下原题解文档中用 $\oplus$ 表示异或以避免与 LaTeX 特殊字符^冲突$$\begin{aligned}Query(left,right) arr[left] \oplus \cdots \oplus arr[right]\(arr[0] \oplus \cdots \oplus arr[left-1]) \oplus (arr[0] \oplus \cdots \oplus arr[left-1]) \oplus (arr[left] \oplus \cdots \oplus arr[right])\ (arr[0] \oplus \cdots \oplus arr[left-1]) \oplus (arr[0] \oplus \cdots \oplus arr[right])\ xors[left] \oplus xors[right1]\ \end{aligned}$$推导的核心思想是先在Query(left, right)前面补上一段arr[0] ^ ... ^ arr[left-1]由于x ^ x 0这段补充会被异或抵消从而将任意区间查询等价转化为两个前缀异或值的一次异或。因此只要预处理出前缀异或数组xors每次查询[Li, Ri]的结果就是xors[Ri] ^ (Li 0 ? xors[Li-1] : 0)当Li 0时xors[Li-1]越界此时直接用 0 参与异或因为x ^ 0 x等价于使用整个前缀。仓库中的 Go 实现与逐行解读仓库内 1310. XOR Queries of a Subarray.go 中的实现与题解文档 README.md 中给出的代码完全一致全文如下package leetcode func xorQueries(arr []int, queries [][]int) []int { xors : make([]int, len(arr)) xors[0] arr[0] for i : 1; i len(arr); i { xors[i] arr[i] ^ xors[i-1] } res : make([]int, len(queries)) for i, q : range queries { res[i] xors[q[1]] if q[0] 0 { res[i] ^ xors[q[0]-1] } } return res }逐段拆解如下第一步构建前缀异或数组xorsxors : make([]int, len(arr)) xors[0] arr[0] for i : 1; i len(arr); i { xors[i] arr[i] ^ xors[i-1] }xors[i]的含义是arr[0] ^ arr[1] ^ ... ^ arr[i]即前缀异或递推关系为xors[i] arr[i] ^ xors[i-1]只需一趟线性扫描即可完成预处理由于题目约束1 arr.length数组至少有一个元素因此xors[0] arr[0]的初始化不会越界。第二步遍历查询用前缀异或求解每个区间res : make([]int, len(queries)) for i, q : range queries { res[i] xors[q[1]] if q[0] 0 { res[i] ^ xors[q[0]-1] } }每个查询q [Li, Ri]先取xors[q[1]]即arr[0] ^ ... ^ arr[Ri]当q[0] 0时再异或上xors[q[0]-1]即arr[0] ^ ... ^ arr[Li-1]利用x ^ x 0把多余的前缀部分抵消得到精确的区间结果arr[Li] ^ ... ^ arr[Ri]当q[0] 0时不做抵消因为此时区间就是从 0 开始的完整前缀。边界情况处理Li 0这是本题实现中最容易出错的地方。xors[q[0]-1]在q[0] 0时会访问下标-1直接越界 panic。仓库实现通过if q[0] 0的判空保护优雅地规避了这一问题逻辑上等价于公式中的xors[left] ^ xors[right1]在left 0时退化为xors[right]。复杂度分析时间复杂度O(n)。预处理前缀异或数组需要一趟 O(n) 的遍历回答每个查询只需 O(1)共 q 个查询因此总时间复杂度为 O(n q)其中n len(arr)q len(queries)空间复杂度O(n)。额外使用了长度为 n 的前缀异或数组xors与长度为 q 的结果数组res结果数组为题目要求的返回值可视为必须输出核心辅助空间为 O(n)。相比朴素解法 O(n × q) 的时间复杂度前缀异或方案在n与q都达到3 * 10^4时优势明显从约9 × 10^8次操作下降到约6 × 10^4次操作。测试验证100% 覆盖率的题解仓库LeetCode-Go 仓库以 100% test coverage 为特色本题同样配有完整的单元测试文件 1310. XOR Queries of a Subarray_test.go。测试采用仓库统一的表格驱动组织方式用para1310结构体封装输入参数arr与queries用ans1310结构体封装期望输出测试用例直接取自题目给出的两个官方示例例如para1310{[]int{1, 3, 4, 8}, [][]int{{0, 1}, {1, 2}, {0, 3}, {3, 3}}}, ans1310{[]int{2, 7, 14, 8}},以及第二个示例para1310{[]int{4, 8, 2, 10}, [][]int{{2, 3}, {1, 3}, {0, 0}, {0, 3}}}, ans1310{[]int{8, 0, 4, 4}},这两个用例恰好覆盖了Li 0、Li Ri单元素区间、区间完全重叠如[0,3]等多种边界情形能够有效验证实现中q[0] 0分支的正确性。运行测试时测试函数会打印输入与输出以便人工核对【input】:[1 3 4 8] [[0 1] [1 2] [0 3] [3 3]] 【output】:[2 7 14 8]仓库根目录的 gotest.sh 脚本展示了整个仓库的测试与覆盖率收集方式go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...即在仓库根目录执行该脚本或直接运行上述go test命令即可对leetcode/目录下所有题解包括本题所在包执行带覆盖率统计的测试产出统一的coverage.txt覆盖率报告。思想延伸前缀异或在 LeetCode-Go 仓库中的其他应用前缀异或并非本题独有它是位运算与区间查询结合的一类通用范式。在 LeetCode-Go 仓库中还能看到它的多种变体1442. Count Triplets That Can Form Two Arrays of Equal XOR利用x ^ x 0将a b等价转化为区间异或为 0再配合前缀异或计数1738. Find Kth Largest XOR Coordinate Value将前缀异或推广到二维类比二维前缀和1486. XOR Operation in an Array、1720. Decode XORed Array 等题目也反复使用异或的自反性质。掌握了前缀异或 区间差分这一组合拳就能举一反三地解决一大类区间异或查询/统计问题。本文的推导公式与 Go 实现正是理解上述所有变体的基石。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考