1. 概述
在本教程中，我们将探讨如何高效计算一个数组中指定区间元素的异或（XOR）结果。
首先，我们会介绍直接遍历区间的朴素方法。接着，我们会通过前缀异或（Prefix XOR）技巧来优化查询效率。最后，我们会对两种方法进行比较，帮助你理解它们的适用场景和性能差异。
2. 问题定义
我们给定一个长度为 n 的数组 A 和若干次查询请求。每次查询要求我们计算区间 [L, R] 内所有元素的异或值，即：
A[L] XOR A[L+1] XOR A[L+2] XOR ... XOR A[R]
数组内容在查询过程中保持不变，也就是说，没有更新操作。
3. 异或基础知识
异或（XOR）是一种按位运算。其运算规则如下：
| A | B | A XOR B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
从表中可以看出：
- 若两个位相同，结果为 0；
- 若两个位不同，结果为 1。
✅ 关键性质：
- 异或满足交换律和结合律；
- 任何数异或 0 仍等于它本身；
- 任何数异或自身等于 0。
⚠️ 一个重要的点是：每个 bit 的异或运算互不干扰。也就是说，最终结果中每一位的值只取决于该位在所有操作数中 1 的个数奇偶性。
4. 朴素解法
算法思路
直接遍历 [L, R] 区间，逐个异或所有元素，得到最终结果。
示例代码
int naiveXorRange(int[] A, int L, int R) {
int answer = 0;
for (int i = L; i <= R; i++) {
answer ^= A[i];
}
return answer;
}
时间复杂度
- 预处理：无
- 单次查询复杂度：
O(n)，最坏情况下需要遍历整个数组
📌 适用于查询次数少、数组较小的场景。
5. 前缀异或优化方法
5.1 核心思想
我们预先计算一个前缀异或数组 prefix，其中：
prefix[i] = A[0] XOR A[1] XOR ... XOR A[i - 1]
这样，当我们需要查询 [L, R] 区间的异或时，可以通过以下公式快速计算：
A[L] XOR A[L+1] XOR ... XOR A[R] = prefix[R + 1] XOR prefix[L]
✅ 为什么成立？
因为异或具有自反性，prefix[R + 1] XOR prefix[L] 实际上是将 [0, L) 区间的异或抵消，只保留 [L, R] 区间的异或结果。
5.2 预处理算法
int[] buildPrefixXor(int[] A) {
int n = A.length;
int[] prefix = new int[n + 1];
for (int i = 1; i <= n; i++) {
prefix[i] = prefix[i - 1] ^ A[i - 1];
}
return prefix;
}
时间复杂度
- 预处理复杂度：
O(n)
5.3 查询算法
int query(int L, int R, int[] prefix) {
return prefix[R + 1] ^ prefix[L];
}
时间复杂度
- 单次查询复杂度：
O(1)
6. 方法对比
| 方法 | 预处理复杂度 | 查询复杂度 | 是否支持更新 | 适用场景 |
|---|---|---|---|---|
| 朴素解法 | 无 | O(n) |
✅ | 查询少、数组小 |
| 前缀异或法 | O(n) |
O(1) |
❌ | 查询频繁、数组大 |
📌 结论：
- 如果你只需要处理少量查询或数组频繁更新，直接使用朴素方法更简单；
- 如果你需要处理大量查询且数组固定不变，前缀异或法效率更高。
7. 总结
本文介绍了两种求数组区间异或和的方法：
- 朴素方法：简单直观，适合小规模或频繁更新的场景；
- 前缀异或法：通过预处理换取查询效率的大幅提升，适合大规模、固定数组的场景。
掌握异或的性质以及前缀异或的构造方式，有助于你在处理类似问题时写出更高效的代码。