图解实验室 / 入门进阶 · 16 分钟 · 算法
前缀异或图解：相同的位出现两次，为什么会消失？
不是减掉一个数，而是让共同前缀的每一份位贡献出现两次。八列从 128 到 1，始终保持同一位对齐。
① 从左到右，构造前缀
实心位 = 1，空心位 = 0；橙色标注共同项，绿色标注目标区间。原数组 A=[5, 3, 5]，查询 [1,3)。淡色行尚未处理。
步骤 0/6。P[0]=0：尚未读入元素，八位都为 0。
P[0]=0；P[k+1]=P[k] XOR A[k]；查询 [1,3) = P[3] XOR P[1]。
P[0] = 0;← / → 单步，Home / End 首尾。输入与滚动区域保留原有按键行为；无自动播放，减少动画偏好关闭位贡献的移动与淡出。数据只留在本页。
自测：非空的 [5,5] 为什么也得到 0？
每一位出现两次，逐位抵消。结果 0 只表示各位的 1 出现偶数次，不能反推区间为空。
看完图，带走这些结论
令 P[0]=0，P[k+1]=P[k] XOR A[k]。零基左闭右开 [l,r) 的异或结果为 P[r] XOR P[l]，不是普通减法。XOR 逐位计算：相同为0、不同为1，不进位。相同贡献出现两次会抵消，因此只留下所选区间。
适用条件与边界
本课是静态数组查询。教学模型接收 1–16 项稠密数组，每项为 0–255 整数，拒绝负零、小数、负数和越界值；边界为 0≤l≤r≤n 的整数，拒绝负零。图中始终保留八位，从高位128到低位1。允许空区间，但不接收空数组；数字0是合法教学值。图形中的位格是每位状态，不代表长度、面积或普通求和。
始终保持的规律
P[k] 恰为前 k 项的逐位奇偶；每个位中1的个数为奇数则结果位为1。P[r] XOR P[l] 让共同前缀每个位的贡献出现两次而抵消。
逐步例子
- 原创数组 A=[5,3,5]。二进制低三位为101、011、101；101 XOR 011=110，即5 XOR 3=6。八位图保留前导0，避免在不同宽度下错位。
- 从 P[0]=0 开始，依次得到 P=[0,5,6,3]。P[k] 表示前 k 项的异或，不是 A[k]；有 n 项输入就有 n+1 个前缀边界。
- 查询 [1,3)：取 P[3] XOR P[1]=3 XOR 5=6；直接计算所选 A[1] XOR A[2]=3 XOR 5 也得到6。右边界3不包含 A[3]。
- 将两个前缀展开为原始项：P[3]=A[0] XOR A[1] XOR A[2]，P[1]=A[0]。由结合律、交换律，同一个 A[0] 的两份位贡献可放在一起；x XOR x=0，x XOR0=x，所以只剩 A[1] XOR A[2]。图形消去的是重复贡献，不是把原数组元素删除。
- 一般地，P[r] 与 P[l] 的共同 A[0]…A[l−1] 各出现两次，消去后留下 A[l]…A[r−1]。l=0 时前缀0为单位元；l=r 时两份完全相同，空段结果0；r=n 时照常查询到数组末尾。
- 非空 [5,5] 的异或也为0，因此不能从结果0推断区间为空。全零输入、相等值抵消和单元素区间都满足同一规则；高位例子 [128,255,128] 全段为255。
- 异或不是加法、减法、OR 或 min。OR 的重复1不会消失，不能照搬此公式。P=[0,5,6,3] 也不单调，不可直接对它做要求有序的二分。
- CSES Range Xor Queries 使用一基闭区间 [a,b]，对应 P[b] XOR P[a−1]。原题值在1到10⁹，本页0值是教学扩展。它是静态查询练习，不包含动态修改；不能把本图说成完整动态数据结构。
静态查询、验证与整数位宽
建立前缀表 O(n) 时间、O(n) 空间，已建立且合法的 P 上查询只做一次 XOR，为 O(1)，q 次静态查询总计 O(n+q)，按固定宽度机器整数模型分析。本页 rangeXor 包装函数会验证数组并重建前缀，因此单次调用是 O(n)，动画渲染成本不计入查询算法。修改 A[i] 后后续前缀可能都需重建，普通前缀并非免费支持动态更新。JavaScript Number 的 ^ 会转换为有符号32位整数；教学0…255与CSES输入小于2³⁰的非负范围均适用，但不能推广到所有安全整数。更大整数须重新选择表示（如BigInt），不可先截断再补救，也不可混用Number与BigInt运算。
常见误区
- 把 P[r]−P[l] 当作异或查询；减法公式属于求和
- 漏掉 P[0]，混淆第k项与前k项
- 右端r也算进去，或把一基闭区间直接当零基半开
- 把非空零结果当空段，或把图中消去贡献当删除输入
- 把 ^ 当乘方；JavaScript 的乘方是 **
- 以为任何安全整数都能直接用32位位运算
自测与答案
A=[5,5]，查询[0,2)与[1,1)结果分别是什么？能据此认为两个区间相同吗？
两者都为0，但[0,2)包含两个元素，靠重复贡献抵消；[1,1)没有元素，是空段。相同的异或值不能确定区间长度或内容。