什么是前缀异或和？如何 O(1) 求区间异或、以及异或为 K 的子数组个数？

简化版

前缀异或和把前缀和里的「加法」换成「异或」:xorPre[i] = a[0] ^ a[1] ^ ... ^ a[i-1]。利用 x ^ x = 0,区间 [l, r] 的异或 = xorPre[r+1] ^ xorPre[l](公共前缀被抵消)。O(1) 查区间异或。求「异或为 K 的子数组个数」则用前缀异或 + 哈希:xorPre[r+1] ^ xorPre[l] = K ⟺ xorPre[l] = xorPre[r+1] ^ K,哈希记录前缀异或出现次数即可,O(n)。

详细版

区间异或查询:

int[] xorPre = new int[n + 1];             // xorPre[0] = 0
for (int i = 0; i < n; i++)
    xorPre[i + 1] = xorPre[i] ^ a[i];      // 前缀异或递推

int rangeXor = xorPre[r + 1] ^ xorPre[l];  // 区间 [l, r] 的异或

异或为 K 的子数组个数(前缀异或 + 哈希):

int countSubarraysXorK(int[] a, int k) {
    Map<Integer, Integer> count = new HashMap<>();
    count.put(0, 1);
    int xor = 0, res = 0;
    for (int x : a) {
        xor ^= x;                          // 当前前缀异或
        res += count.getOrDefault(xor ^ k, 0); // 找 xorPre[l] = xor ^ k
        count.merge(xor, 1, Integer::sum);
    }
    return res;
}

完整版教学

一、异或的关键性质:自反性

前缀异或能成立,靠异或的两个性质:

x ^ x = 0:一个数异或自己等于 0(自反)。
x ^ 0 = x:异或 0 不变。

所以异或有「成对抵消」的特性——出现两次的数会互相消掉。前缀异或正是利用这个:两个前缀异或一相消,公共部分抵消,只剩中间区间。这和前缀和「相减抵消公共部分」是完全平行的思想,只是把「加/减」换成了「异或」(异或的逆运算还是异或)。

二、区间异或 = 两个前缀异或再异或

定义 xorPre[i] = a[0] ^ ... ^ a[i-1](前 i 个的异或,xorPre[0]=0)。区间 [l, r] 的异或:

a[l] ^ a[l+1] ^ ... ^ a[r]
= (a[0]^...^a[r]) ^ (a[0]^...^a[l-1])   ← 后半段把 a[0..l-1] 再异或一次抵消
= xorPre[r+1] ^ xorPre[l]

因为 a[0..l-1] 被异或了两次(在 xorPre[r+1] 里一次、再和 xorPre[l] 异或一次),根据 x^x=0 成对抵消,剩下的正好是 a[l..r]。所以区间异或 = xorPre[r+1] ^ xorPre[l],O(1)。

三、异或为 K 的子数组:前缀异或 + 哈希

和「和为 K 的子数组」完全平行。要子数组 [l..r] 异或为 K:

xorPre[r+1] ^ xorPre[l] = K
⟺ xorPre[l] = xorPre[r+1] ^ K          （两边同时异或 K，K^K=0 抵消）

所以遍历时,对当前前缀异或 xor,去哈希表里找有多少个前缀异或等于 xor ^ K,累加。哈希记录前缀异或的出现次数,count.put(0,1) 初始化,先查后存。O(n)。和「和为 K」的唯一区别是把「减法」换成「异或」(而异或的逆还是异或,所以查 xor ^ k 而不是 xor - k)。

四、为什么初始化 count.put(0, 1)

和前缀和一样,count.put(0, 1) 处理「从头到当前位置整段异或就等于 K」的情况——此时 xorPre[l] = xorPre[0] = 0,对应 xor ^ k == 0(即 xor == k)。不初始化就会漏掉这类子数组。这是所有「前缀量 + 哈希」题的通用坑。

五、经典应用

区间异或查询:静态数组多次查「某段的异或值」。
异或为 K 的子数组个数(如 LeetCode 1442 变体、面试常见)。
最大异或对 / 区间最大异或:配合 0-1 字典树(见字典树专题),前缀异或 + Trie 求最大异或。
找出只出现一次的数字:一组数全异或,成对的抵消,剩下单个的(异或经典应用)。

前缀异或是「异或版前缀和」,把一批「区间异或」问题转成 O(1) 或 O(n)。

六、复杂度与要点

区间异或查询:预处理 O(n)、查询 O(1)。
异或为 K 的子数组:O(n) 时间、O(n) 空间。
要点:x^x=0 是核心;区间异或 = xorPre[r+1] ^ xorPre[l];求异或为 K 的子数组查 xor ^ k(不是 xor - k);别忘 count.put(0,1)。

七、从公式证明到手算闭环

这道题成立的核心是：异或满足自反与结合律，同一前缀出现两次会抵消，区间异或等于两个前缀异或。先明确每个数组槽或哈希键的数学含义，代码中的下标偏移才不是死记硬背。

px[0] = 0
px[i+1] = px[i] XOR a[i]
xor(l,r) = px[r+1] XOR px[l]
若 px[j] XOR px[i] = K，则 px[i] = px[j] XOR K

带数字推演：[4,2,2,6,4] 的前缀异或从 0 开始；扫描到当前 px 时，哈希中 px XOR 6 的出现次数就是新增答案数。手算时同时列出原数组、辅助状态和本轮新增答案，能够直接发现端点偏一、初始化遗漏以及更新顺序错误。

核对维度	本题结论
正确性依据	异或满足自反与结合律，同一前缀出现两次会抵消，区间异或等于两个前缀异或
复杂度	区间查询预处理 O(n)、单次 O(1)；计数题单次扫描期望 O(n)
关键边界	XOR 不是加法，不能用减号；初始化 0 出现一次才能统计从下标 0 开始的区间；整数位宽要明确

记忆钩子：不要先背代码，先说清辅助状态“代表哪一段”；公式只是把重叠部分消掉或把边界影响传播出去。

八、实现边界与测试策略

实现时最需要警惕的是：XOR 不是加法，不能用减号；初始化 0 出现一次才能统计从下标 0 开始的区间；整数位宽要明确。这不是语法细节，而是决定算法是否仍满足题目语义的前提。

提交前应分别验证：

空数组或最小合法规模，确认哨兵位置和初始化。
查询或更新紧贴左、上边界，确认没有访问负下标。
查询或更新紧贴右、下边界，确认“终点后一位”不会越界。
包含 0、负数或重复前缀的样例，确认频次与取模语义。
大数输入，确认累计和、乘积或答案数量的整数类型足够。

如果需求从离线变成在线，或从单次恢复变成更新查询交错，原方法可能不再合适。此时应根据操作类型改用树状数组、线段树、二维结构或其他能维护动态状态的数据结构，而不是强行沿用静态前缀模型。

九、常见误区与追问

误区：区间异或应使用两个前缀相减。 异或的逆运算仍是异或。
误区：哈希只需记录前缀是否出现。 求子数组个数必须记录出现次数。
误区：初始 0 可省略。 会漏掉从下标 0 开始且异或为 K 的区间。
追问：为什么查 px XOR K？ 由 old XOR px=K，两边再 XOR K 得 old=px XOR K。
追问：XOR 有大小单调性吗？ 没有，不能像正数和那样使用普通滑动窗口。
追问：空间能否降到 O(1)？ 单次固定区间查询可以；统计任意子数组通常需要保存前缀频次。

十、加强记忆

前缀异或和 xorPre[i] = a[0]^...^a[i-1],靠 x^x=0 成对抵消。区间 [l,r] 异或 = xorPre[r+1] ^ xorPre[l](公共前缀抵消),O(1)。求异或为 K 的子数组个数:xorPre[l] = xor ^ K,哈希记前缀异或出现次数、查 xor ^ k(不是减法)、count.put(0,1) 起步,O(n)。它是「异或版前缀和」,和「和为 K 子数组」框架一致,常配 0-1 Trie 求最大异或。

简化版

详细版