前缀和

异或前缀和

在竞赛中，“异或前缀和”是一个非常常用的技巧，核心思想是利用异或运算的可逆性将“区间异或”转化为前缀异或的查询，从而将原本 O(n) 的区间统计降到 O(1) 或 O(n) 甚至 O(n log C)（C 是数值范围）级别。

---

1. 定义与核心性质

• 前缀异或

  令 pre[i] 表示数组 a[1…i] 的全部元素的异或值：

  pre[0] = 0;
  for (int i = 1; i <= n; i++)
      pre[i] = pre[i-1] ^ a[i];

• 区间异或公式

  任意区间 [l, r] 的异或和

  $a[l] \oplus a[l+1] \oplus \cdots \oplus a[r] = \mathrm{pre}[r] \oplus \mathrm{pre}[l-1]$

---

2. 常见应用

1. 在线/离线区间异或查询

   预处理 pre[] 数组后，任何一个区间异或查询都可在 O(1) 内完成。

2. 统计子数组异或等于 K 的个数

   我们要找数量

   #$\{(i,j)\mid 1 \le i \le j \le n,\; \mathrm{pre}[j] \oplus \mathrm{pre}[i-1] = K\}.$

   等价于：对每个 j，统计之前有多少个 i-1 满足

   $pre[i−1]=pre[j]⊕K.$

   用哈希表（unordered_map<long long, int>）记录每个前缀值出现的次数，整体 O(n)。

3. 求最大子数组异或和

   经典做法是把所有前缀异或插入一棵二叉 Trie，然后对每个 pre[j] 在 Trie 中贪心查询使得 pre[j] ^ 某前缀 最大，整体 O(n · log C)。

---

3. 样例：统计子数组异或和为 K

下面给出一个完整、可通过 Codeforces/AtCoder 模版的 C++17 实现，时间复杂度 O(n)，空间 O(n)。代码同时包含随机测试数据生成示例。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // ---- 输入部分 ----
    int n;
    ll K;
    cin >> n >> K;
    vector<ll> a(n+1), pre(n+1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pre[i] = pre[i-1] ^ a[i];
    }

    // ---- 计数部分 ----
    unordered_map<ll, ll> cnt;
    cnt.reserve(n*2);
    cnt[0] = 1;           // 空前缀
    ll ans = 0;
    for (int j = 1; j <= n; j++) {
        ll want = pre[j] ^ K;
        if (cnt.count(want)) ans += cnt[want];
        cnt[pre[j]]++;
    }

    // ---- 输出结果 ----
    cout << ans << "\n";
    return 0;
}

解释要点：

• cnt[x] 记录前缀异或等于 x 的次数。

• 每遍历到 j，之前出现了 cnt[pre[j] ^ K] 个下标 i-1，与当前 j 配对即可得到异或为 K 的子数组。

---

4. 拓展：随机测试数据

下面给出几组随机生成的测试例子，方便你本地测强度或压边界：

序号	n	K	数组 a
1	5	0	3 1 4 1 5
2	6	7	2 2 2 2 2 2
3	8	10	5 9 7 3 8 2 0 1
4	10	15	随机生成：每个元素 0 ≤ a[i] < 2³¹；n=10
5	100000	随机	n=10⁵，大随机测试，验证性能边界（只在本地生成，不手写）

示例 1 输入：

5 0
3 1 4 1 5

预期输出：

所有异或和为 0 的子数组对有 2 段（[1..4] 和 [2..5]），输出 2。

---

以上就是“异或前缀和”的基本原理、典型应用及 C++ 模版。若需最大异或和或其他高级应用，可在此基础上接入二叉 Trie 等结构。