如何更快计算数组区间内累积异或值的总和？

核心思路：按位拆分 + 前缀计数 #

当前逐次计算的方法时间复杂度为O(R-L+1)每查询，当查询次数Q多或区间范围大时效率极低。我们可以利用异或的位独立性和前缀统计，将单次查询的时间复杂度降到O(位数)（对应1e26量级约需90位），预处理时间为O(N×位数)，整体效率大幅提升。

关键推导 #

1. 前缀异或数组定义：设prefix_xor[0] = 0，prefix_xor[i] = Arr[1] ^ Arr[2] ^ ... ^ Arr[i]（数组为1-based）。根据异或的抵消性质，区间[L, k]的异或结果可简化为：

   Arr[L] ^ Arr[L+1] ^ ... ^ Arr[k] = prefix_xor[k] ^ prefix_xor[L-1]
   

2. 总和转换：原问题要求的总和可改写为：

   S = sum_{k=L}^R (prefix_xor[k] ^ prefix_xor[L-1])
   

3. 按位计算贡献：二进制第b位的贡献独立于其他位，(x ^ y)的第b位为1当且仅当x和y的第b位不同。只需统计区间[L, R]中与prefix_xor[L-1]第b位不同的prefix_xor[k]数量，再乘以2^b就是该位对总和的贡献。

预处理步骤 #

• 预处理前缀异或数组prefix_xor，长度为N+1（包含prefix_xor[0]）。
• 对每一位b，预处理前缀计数数组cnt[b][i]：表示prefix_xor[0..i]中第b位为1的元素个数。区间[L, R]中第b位为1的数量为cnt[b][R] - cnt[b][L-1]，为0的数量为(R-L+1) - (cnt[b][R] - cnt[b][L-1])。

查询步骤 #

对于每个查询[L, R]：

1. 取出prefix_xor[L-1]的第b位值bit（0或1）。
2. 计算区间内与bit不同的元素数量：若bit=0，取区间内第b位为1的数量；若bit=1，取区间内第b位为0的数量。
3. 将该数量乘以2^b，累加到总和中。
4. 遍历所有位后得到最终结果。

代码实现（C++） #

考虑到元素量级为1e26，使用__int128存储总和以避免溢出：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX_BIT = 90; // 1e26 < 2^87，预留足够位数

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

    int N, Q;
    cin >> N >> Q;

    vector<unsigned long long> arr(N+1); // 1-based数组
    for (int i = 1; i <= N; ++i) {
        cin >> arr[i];
    }

    // 预处理前缀异或数组
    vector<unsigned long long> prefix_xor(N+1, 0);
    for (int i = 1; i <= N; ++i) {
        prefix_xor[i] = prefix_xor[i-1] ^ arr[i];
    }

    // 预处理每一位的前缀计数数组
    vector<vector<int>> cnt(MAX_BIT, vector<int>(N+1, 0));
    for (int b = 0; b < MAX_BIT; ++b) {
        for (int i = 1; i <= N; ++i) {
            cnt[b][i] = cnt[b][i-1] + ((prefix_xor[i] >> b) & 1);
        }
    }

    // 输出__int128的工具函数
    auto print_int128 = [](__int128 x) {
        if (x == 0) { cout << "0"; return; }
        string s;
        while (x > 0) {
            s += (char)(x % 10 + '0');
            x /= 10;
        }
        reverse(s.begin(), s.end());
        cout << s;
    };

    while (Q--) {
        int L, R;
        cin >> L >> R;
        __int128 sum = 0;
        unsigned long long base = prefix_xor[L-1];

        for (int b = 0; b < MAX_BIT; ++b) {
            int bit = (base >> b) & 1;
            int total = R - L + 1;
            int cnt1 = cnt[b][R] - cnt[b][L-1];
            int cnt0 = total - cnt1;

            int contribute = (bit == 0) ? cnt1 : cnt0;
            sum += (__int128)contribute * (1ULL << b);
        }

        print_int128(sum);
        cout << '\n';
    }

    return 0;
}

复杂度分析 #

• 预处理时间：O(N × MAX_BIT)，对于N=1e5、MAX_BIT=90，仅需9e6次操作，完全可行。
• 单次查询时间：O(MAX_BIT)，约90次操作，即使Q=1e5，总操作量仅9e6次，远优于原方法的O(Q×(R-L+1))。

内容的提问来源于stack exchange，提问作者Dex