题目描述
思路解析动画文字版
记牢一句话:先把前缀异或数组 pre 建出来,之后每个区间查询都等于 pre[R+1] 异或 pre[L]。下面每一帧都在套这个公式。
阶段一 · 准备建前缀异或：上面这排是 arr = [1, 3, 4, 8]。右边面板是要建的前缀异或数组 pre,它比 arr 多一格,一共 5 格,现在全是问号。第一格 pre[0] 我们约定它等于 0,这是一段空异或的自然起点,异或上 0 什么都不变。
阶段一 · 先看二进制：异或是按二进制位算的,所以先把 arr 每个数写成二进制看清楚:1 是 0001,3 是 0011,4 是 0100,8 是 1000。两个数异或时,逐位比较,这一位相同就得 0、不同就得 1,各位互不影响。心里有了这张二进制表,后面建前缀异或、算查询都顺。
阶段一 · pre[0] = 0：先把 pre[0] 写成 0。它代表前 0 个数的异或,也就是什么都不异或,结果就是 0。0 是异或的零元,谁异或 0 都等于它自己,这个性质待会儿处理从下标 0 开始的查询时会非常顺手。
阶段一 · 算 pre[1]：把 arr[0] = 1 接进来。新的前缀值 pre[1] 等于上一格 pre[0] = 0 再异或这个 1,二进制是 0000 异或 0001 等于 0001,也就是 1。把它记到 pre[1] 这一格。
阶段一 · 算 pre[2]：把 arr[1] = 3 接进来。新的前缀值 pre[2] 等于上一格 pre[1] = 1 再异或这个 3,二进制是 0001 异或 0011 等于 0010,也就是 2。把它记到 pre[2] 这一格。
阶段一 · 算 pre[3]：把 arr[2] = 4 接进来。新的前缀值 pre[3] 等于上一格 pre[2] = 2 再异或这个 4,二进制是 0010 异或 0100 等于 0110,也就是 6。把它记到 pre[3] 这一格。
阶段一 · 算 pre[4]：把 arr[3] = 8 接进来。新的前缀值 pre[4] 等于上一格 pre[3] = 6 再异或这个 8,二进制是 0110 异或 1000 等于 1110,也就是 14。把它记到 pre[4] 这一格。
阶段一完成 · pre 数组：前缀异或数组建好了,从左到右是 0、1、2、6、14。从这一帧起,舞台上摆的就是这排 pre,不再是原来的 arr。记住每一格的含义:pre[i] 是 arr 前 i 个数的异或值,比如 pre[3] = 6 就是 arr[0] 异或 arr[1] 异或 arr[2]。
阶段二 · 区间查询公式：现在用 pre 来回答查询。任意区间 [L, R] 的异或值,等于 pre[R+1] 异或 pre[L]。为什么是 R+1 而不是 R?因为 pre[R+1] 才包含到 arr[R] 这一项,pre[R] 只到 arr[R-1]。下面对 3 个查询逐个套这个公式。
阶段二 · 为什么能抵消：先用查询 [3,3] 体会抵消。pre[4] 是 arr[0] 异或 arr[1] 异或 arr[2] 异或 arr[3],pre[3] 是 arr[0] 异或 arr[1] 异或 arr[2]。两者异或时,共有的 arr[0]、arr[1]、arr[2] 各出现两次,而一个数异或它自己等于 0,于是成对抵消,只剩下 arr[3] = 8。这就是公式成立的根。
查询 0 · [0, 1] 定位：第 0 个查询是 [0, 1]。套公式,R 是 1,那 R+1 就是 2,所以要取 pre[2] 这一格;L 是 0,取 pre[0] 这一格。下一步把这两格异或起来。
查询 0 · 两格异或：把绿色这两格异或:pre[2] = 2,pre[0] = 0。二进制是 0010 异或 0000,逐位算下来等于 0010,也就是 2。这就是区间 [0, 1] 的异或值。
查询 0 · 结果 2：查询 [0, 1] 的答案是 2。验一下:arr 这一段是 1、3,直接全异或起来也是 2,对得上。把它接到答案数组,目前是 [2]。
查询 1 · [0, 3] 定位：第 1 个查询是 [0, 3]。套公式,R 是 3,那 R+1 就是 4,所以要取 pre[4] 这一格;L 是 0,取 pre[0] 这一格。下一步把这两格异或起来。
查询 1 · 两格异或：把绿色这两格异或:pre[4] = 14,pre[0] = 0。二进制是 1110 异或 0000,逐位算下来等于 1110,也就是 14。这就是区间 [0, 3] 的异或值。
查询 1 · 结果 14：查询 [0, 3] 的答案是 14。验一下:arr 这一段是 1、3、4、8,直接全异或起来也是 14,对得上。把它接到答案数组,目前是 [2、14]。
查询 2 · [3, 3] 定位：第 2 个查询是 [3, 3]。套公式,R 是 3,那 R+1 就是 4,所以要取 pre[4] 这一格;L 是 3,取 pre[3] 这一格。下一步把这两格异或起来。
查询 2 · 两格异或：把绿色这两格异或:pre[4] = 14,pre[3] = 6。二进制是 1110 异或 0110,逐位算下来等于 1000,也就是 8。这就是区间 [3, 3] 的异或值。
查询 2 · 结果 8：查询 [3, 3] 的答案是 8。验一下:arr 这一段是 8,直接全异或起来也是 8,对得上。把它接到答案数组,目前是 [2、14、8]。
完成 · 答案 [2, 14, 8]：三个查询都答完了,回放一遍:[0,1] 是 pre[2] 异或 pre[0] 等于 2;[0,3] 是 pre[4] 异或 pre[0] 等于 14;[3,3] 是 pre[4] 异或 pre[3] 等于 8。最终答案数组就是 [2、14、8]。全程 pre 只建一次,每个查询都是一步异或。
边界先想清:单元素查询就是它本身、两个相等的数异或得 0、异或结果可能比两数都大(不像求和那样单调递增)。
面试重点:前缀异或用预处理换查询 O(1)、它和前缀和同构只是把加换成异或、要支持修改则上树状数组或线段树。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *from string import *from operator import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]: s = list(accumulate(arr, xor, initial=0)) return [s[r + 1] ^ s[l] for l, r in queries]复杂度
- 时间：O(n + m)，n 是 arr 长度,m 是查询个数。建前缀异或数组扫一遍 arr 是 O(n);每个查询是一步异或 O(1),m 个查询共 O(m);合起来 O(n+m)
- 空间：O(n)，主要开销是长度 n+1 的前缀异或数组,峰值 O(n);答案数组 O(m) 属必需输出,通常不计入额外空间
易错点
面试追问把动画讲成自己的话
追问为什么前缀异或能把每次查询降到 O(1),而暴力是多少?
追问前缀和与前缀异或有什么相同和不同?
追问如果还要支持单点修改 arr 某个值,这个方法够用吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
每个元音包含偶数次的最长子字符串
LeetCode 1371 · 中等 · 沿着 字典树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题