# 前缀异或图解：相同的位出现两次，为什么会消失？

用八位 SVG 位图逐步构造前缀异或，让共同前缀的位贡献成对消去；同步理解区间 XOR、零结果、空区间与 JavaScript 位宽边界。

原文 / Canonical: https://crazycloud.cc/learn/prefix-xor
作者: crazycloudcc
首次发布: 2026-11-02
更新: 2026-11-02

本阅读版与网页共用课程数据；互动请访问原文。

## 一句话答案

令 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] 让共同前缀每个位的贡献出现两次而抵消。

## 逐步例子

1. 原创数组 A=[5,3,5]。二进制低三位为101、011、101；101 XOR 011=110，即5 XOR 3=6。八位图保留前导0，避免在不同宽度下错位。
2. 从 P[0]=0 开始，依次得到 P=[0,5,6,3]。P[k] 表示前 k 项的异或，不是 A[k]；有 n 项输入就有 n+1 个前缀边界。
3. 查询 [1,3)：取 P[3] XOR P[1]=3 XOR 5=6；直接计算所选 A[1] XOR A[2]=3 XOR 5 也得到6。右边界3不包含 A[3]。
4. 将两个前缀展开为原始项：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]。图形消去的是重复贡献，不是把原数组元素删除。
5. 一般地，P[r] 与 P[l] 的共同 A[0]…A[l−1] 各出现两次，消去后留下 A[l]…A[r−1]。l=0 时前缀0为单位元；l=r 时两份完全相同，空段结果0；r=n 时照常查询到数组末尾。
6. 非空 [5,5] 的异或也为0，因此不能从结果0推断区间为空。全零输入、相等值抵消和单元素区间都满足同一规则；高位例子 [128,255,128] 全段为255。
7. 异或不是加法、减法、OR 或 min。OR 的重复1不会消失，不能照搬此公式。P=[0,5,6,3] 也不单调，不可直接对它做要求有序的二分。
8. 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)没有元素，是空段。相同的异或值不能确定区间长度或内容。

## 延伸学习

都通过前缀消去共同贡献，但运算不同：求和用减法，异或用 XOR，不能混用公式。

[对比：前缀和的普通相减](https://crazycloud.cc/learn/prefix-sum)

## 参考资料

- [CSES 1650：Range Xor Queries（常青静态区间练习）](https://cses.fi/problemset/task/1650/)
- [ECMAScript：Number 位运算的32位转换](https://tc39.es/ecma262/multipage/ecmascript-data-types-and-values.html#sec-numberbitwiseop)

[返回图解实验室](https://crazycloud.cc/learn)