最大异或和——广义前缀和的应用 Trie树

最大异或和

给定一个非负整数数列 a，初始长度为 N。
请在所有长度不超过 M 的连续子数组中，找出子数组异或和的最大值。
子数组的异或和即为子数组中所有元素按位异或得到的结果。

$XOR$异或前缀和

$XOR$的性质：

1. $a\oplus a=0$
2. $a\oplus b=b\oplus a$
3. $a\oplus b\oplus c=a\oplus (b\oplus c)=(a\oplus b)\oplus c$;
4. $a\oplus b\oplus a=b$
5. $a\oplus b=!a\oplus !b$
6. $!a\oplus b=a\oplus !b=!(a\oplus b)$

我们可以将前缀和的定义推广:

在$\mathrm{a}\left[0\right]\sim \mathrm{a}\left[\mathrm{n}\right]$序列上定义运算$\cdot$，如果$\cdot$有逆则可以使用前缀和的技巧。$0$到$k$位上的前缀和可以表示为$\mathrm{a}\left[0\right]\cdot \mathrm{a}\left[1\right]\cdot \mathrm{a}\left[2\right]\cdots \mathrm{a}\left[\mathrm{k}\right]$。

我们让$\cdot$为异或$\oplus$，$\left(i\oplus j\right)\oplus j=i$满足逆运算，所以可以使用前缀和计算部分区间的异或和。如对于$XOR$前缀和数组$S$ 有$\mathrm{S}\left[l\sim r\right]=\mathrm{S}\left[r\right]\oplus \mathrm{S}\left[l-1\right]$。

• 另，$0$到$4n-1$的所有数一起异或的和为$0$,如$3711$ …,原理是每两位会不断出现$00,01,10,11$,对应位上两个$1$异或为$0$

解法1 暴力 $O(n^2)$

我们可以枚举$i,j$作为起点和终点,预处理异或前缀和后，每次计算区间长度小于$m$的最大异或值,更新$max$。

#include <iostream>
using namespace std;
const int N = 1e6 + 10, M = 31 * N;
int a[N];
int s[N];

int get(int l, int r) {
    //由于n^a^a等价于n自身,故前缀和计算时可以通过异或l-1部分来把r中l-1的部分去掉
    return s[r] ^ s[l - 1];
}
int main() {
    int n, m;
    cin >> n >> m;
    int x, maxn = 0;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        s[i] = s[i - 1] ^ a[i];//前缀异或和
    }

    int res = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = i; j <= n && j < i + m; ++j) {
            res = max(res, get(i, j));//
        }
    }
    cout << res << endl;

    return 0;
}

这样可以过$80$数据。

解法2 Tire树 $O(nlogn)$

加入$XOR$前缀和后问题就变成就最大异或对了，这个问题可以由$Trie$树优化。

将数字变成二进制，在$Tire$树中存储（二叉树）。假设前面已经存储了$k$个值，第$k+1$个数与前$k$个数之间的最大异或值怎么找呢？只需要对k从高位到低位遍历，每次尝试找当前这一位的反向（是$0$就找$1$，是$1$就找$0$），让异或值最大。如果没有反向就顺着走。所以$Trie$树可以一次查询一个值和一个区间中最大的异或对。

故本题树中维护$m$长度的区间，每次查询准备新加入的值，更新$max$。如果区间长度$>m$就删除区间的第一个数。删除只需要将插入的值改成$-1$。

总复杂度就是遍历$\ast$查询，查询只要看数字的位数，$O(nlogn)$

详细代码

注意看推的样例!文章来源地址https://uudwc.com/A/NZ6XX

/*
 * @Author: ACCXavier
 * @Date: 2021-05-10 22:07:21
 * @LastEditTime: 2022-03-18 10:32:38
 * Bilibili:https://space.bilibili.com/7469540
 * 题目地址:https://www.acwing.com/problem/content/3488/
 * @keywords: 
 */
#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

const int N = 100010 * 31, M = 100010;//每一个数字最多31个分叉,故开31*1e5

int n, m;
int s[M];
int son[N][2], cnt[N], idx;

void insert(int x, int v) {//插入/删除x 取决于v是1还是-1
    int p = 0;
    for (int i = 30; i >= 0; i--) {
        int u = x >> i & 1;
        if (!son[p][u]) son[p][u] = ++idx;
        //!接下来两行顺序不能反,因为此时p
        p = son[p][u];
        cnt[p] += v; // 每一位都记录
    }
}

int query(int x) {//查询最大值
    int res = 0, p = 0;
    for (int i = 30; i >= 0; i--) {
        int u = x >> i & 1;
        if (cnt[son[p][!u]]) // 看反向点是否存在
            p = son[p][!u], res = res * 2 + 1;
        else // 没有反向就顺着走，这条路肯定是存在的。最坏就是000...0
            p = son[p][u], res = res * 2;
    }
    return res;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);
        s[i] = s[i - 1] ^ x;
    }

    int res = 0;
    insert(s[0], 1);//至少要插入0,与0异或是自己

    for (int i = 1; i <= n; i++) {
        if (i > m) insert(s[i - m - 1], -1);//剔除前面的
        // 遍历到i 只会查询i - m ~ i - 1共m长度
        res = max(res, query(s[i]));//意会一下
//要求的是长度<=m的最大异或值,,每次i更新,都相当于走到当前m区间的最后一个数字,前面的数字都已经插入trie集合,且前面的最大值已经更新,然后当前的数字只需要进入trie集合找最大值即可 这个是从1开始递推的 比如m=3
//i为1 trie集合只有0,最大就是1处的值 0101
//i为2 trie集合0101,当前1000,异或得1100,1100为最大值,同时1000存入trie
//i为3 trie 0101,1000 ,当前1110,按照trie树走第一位取0,故按照0101异或,得1011 最大值不更新
//i为4 trie 1000,1110(0101已经被删除),当前0001,按照trie树走1110,得1111,更新为最大值
/*
上述例子输入测试
4 3
5   
8
14
1
 结果为15 也就是1111
*/
        insert(s[i], 1);//插入当前序列
    }

    printf("%d\n", res);
    return 0;
}