介绍01trie树及其可持久化。

        trie树（字典树）在AC自动机中已经有过介绍。01trie树是一种trie树的变种：存很多二进制数。01trie树可以很好地解决异或问题。
        给定很多数，现判断哪一个数与给定的数x异或值最大。这个问题可以用01trie树快速解决。方法是将所有数化为二进制，存入trie树中，再根据给定的数从高位开始进行贪心，从而得到最大值。

异或运算的基本性质

        在此之前，先来了解异或运算的基本性质。

  • 0是异或运算中的幺元，即对于任意x，有$x \oplus 0=x$
  • 任何数是其本身的逆元，即有$x \oplus x=0$

        这些性质使得连续区间的异或和可以用前缀和维护。

01Trie树

        一道例题：P4551。
        这是一道经典的异或问题。如果要求最长路径和的话，这就是求树的直径问题了。对于最大异或和，考虑如何将其与trie树联系起来。
        首先无根树转有根树，一遍DFS求出所有点到根结点路径的异或和。这时，任意两个点这个异或和的异或值就是它们路径上的异或值。根据异或的运算性质，两点LCA到根的重叠路径部分会抵消，异或后得到的就是两点路径异或和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<bits/stdc++.h>

using namespace std;

inline int read() {//读优
    char e = getchar();
    int s = 0;
    while (e < '-')e = getchar();
    while (e > '-')s = (s << 1) + (s << 3) + (e & 15), e = getchar();
    return s;
}

struct Node {//trie树结点定义，只存左右儿子
    int ch[2];
} node[100005 * 31];
struct Edge {//存边
    int to, next, v;
} edge[100005 << 1];
int head[100005], cnt = 1, n, tp[100005];

inline void add(int x, int y, int v) {
    edge[cnt].to = y, edge[cnt].next = head[x], edge[cnt].v = v, head[x] = cnt++;
}

inline int newNode() {//分配新结点，1为根
    static int cnt = 2;
    return cnt++;
}

inline void insert(int x) {//插入元素
    int now = 1;
    for (int i = 31; i >= 0; i--) {//从高位开始
        if ((1 << i) & x) {
            if (node[now].ch[1] == 0)node[now].ch[1] = newNode();//没有就新建
            now = node[now].ch[1];
        } else {
            if (node[now].ch[0] == 0)node[now].ch[0] = newNode();
            now = node[now].ch[0];
        }
    }
}

inline int find(int x) {
    int now = 1, ans = 0;
    for (int i = 31; i >= 0; i--) {
        if ((1 << i) & x) {
            if (node[now].ch[0])now = node[now].ch[0], ans |= (1 << i);//向反方向找
            else now = node[now].ch[1];
        } else {
            if (node[now].ch[1])now = node[now].ch[1], ans |= (1 << i);
            else now = node[now].ch[0];
        }
    }
    return ans;
}

void DFS(int fa, int x, int y) {//预处理
    insert(y), tp[x] = y;
    for (int i = head[x]; i; i = edge[i].next) {
        if (edge[i].to != fa)DFS(x, edge[i].to, y ^ edge[i].v);
    }
}

int main() {
    n = read();
    for (int i = 1; i < n; i++) {
        int x = read(), y = read(), z = read();
        add(x, y, z), add(y, x, z);
    }
    DFS(0, 1, 0);
    int ans = -1;
    for (int i = 1; i <= n; i++)ans = max(ans, find(tp[i]));
    cout << ans;
    return 0;
}

可持久化01Trie树

        下面就是可持久化01Trie树的部分，例题一道：P4735。
        首先后缀转前缀。注意到$a[p]\oplus a[p+1]\oplus…\oplus a[N]\oplus x=sum[p-1]\oplus sum[N]\oplus x$。sum是异或前缀和，这样问题转化为找一个值$sum[p-1]$使得与$sum[N]\oplus x$异或值最大。
        但是容易发现p的选取有限制（为[l-1，r-1]），普通的01trie树不能加上这个限制。这里需要借鉴主席树维护区间第k大的思想。在trie树的结点上增加指标num，记录数量。然后对于每一个i（$1\leq i\leq N$）分别建立一棵存1~i这些数的01trie树，查询时作差即可。这样需要建立N棵树，空间消耗过大，于是需要用主席树的思想来重用空间，降低空间复杂度，这一步与主席树类似。
        对于插入操作，由于只是末尾插入，建立一棵新版本的trie树即可。对于查询操作，本质上就是找到一个$p（l-1\leq p\leq r-1）$使得$sum[p]$与$sum[N]\oplus x$异或值最大。找到r-1和l-2这两个trie树，作差即可判断。注意当l=1时需要特判。
        可持久化01trie树不要向主席树那样建立空树，否则空间开销达到指数级。对于那些空的结点，统一用0号结点代替。
        另外，本题卡常，需要尽可能减小常数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<bits/stdc++.h>

using namespace std;
int root[300005 << 2], n, m, la;
struct Node {
    int ch[2], num;
} node[300005 << 6];

inline int newNode() {
    static int cnt = 1;
    return cnt++;
}

inline int newTree(int pre, int x, int p) {//新建一棵树
    register int rt = newNode();
    if (p == -1) {
        node[rt].num = node[pre].num + 1;
        return rt;
    }
    node[rt].ch[0] = node[pre].ch[0], node[rt].ch[1] = node[pre].ch[1], node[rt].num = node[pre].num + 1;//继承和修改
    if ((1 << p) & x)node[rt].ch[1] = newTree(node[pre].ch[1], x, p - 1);
    else node[rt].ch[0] = newTree(node[pre].ch[0], x, p - 1);
    return rt;
}

inline int query(int a, int b, int x) {
    register int p = 25, ans = 0;
    while (p >= 0) {
        if ((1 << p) & x) {
            if (node[node[b].ch[0]].num > node[node[a].ch[0]].num) {
                b = node[b].ch[0], a = node[a].ch[0], ans |= (1 << p);
            } else b = node[b].ch[1], a = node[a].ch[1];
        } else {
            if (node[node[b].ch[1]].num > node[node[a].ch[1]].num) {
                b = node[b].ch[1], a = node[a].ch[1], ans |= (1 << p);
            } else b = node[b].ch[0], a = node[a].ch[0];
        }
        p--;
    }
    return ans;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        register int x;
        scanf("%d", &x), la ^= x;
        root[i] = newTree(root[i - 1], la, 25);
    }
    for (register int i = 0; i < m; i++) {
        char e;
        register int a, b, c;
        scanf(" %c", &e);
        if (e == 'A')scanf("%d", &a), la ^= a, root[n + 1] = newTree(root[n], la, 25), n++;
        else {
            scanf("%d%d%d", &a, &b, &c);
            register int p = query(a != 1 ? root[a - 2] : 0, root[b - 1], c ^ la);
            printf("%d\n", a == 1 ? max(p, c ^ la) : p);//a=1时特判一步
        }
    }
    return 0;
}

异或最小生成树

        01trie树的一个经典应用是求异或最小生成树。
        给定一个完全图，每一个点都有一个权值$v_i$，其中$dis(i,j)=v_i⊕v_j$。
        思路是贪心思想。我们找到权值的最高二进制位（比如30），将点分为两部分，一部分该位为0，另一部分为1。如果我们将这两部分分别构造生成树，再在这两部分之间连一条尽可能短的边，生成树就建好了。
        上述算法是正确的，简单证明如下：
        按照这种算法，现在长的一条边必然就是我们连接这两个部分的边（毕竟最高位是1），并且只有这一条边最高位是1。如果存在一种方案可以使得有多条连接这两个部分，但是最后总和较小的生成树方案，这和Kruskal算法是矛盾的。
        问题是如何找两个部分之间最小的权值，这个问题可以用01trie在$O(nlogn)$复杂度内解决。
        由于最外层按二进制位划分，所以最后算法复杂度是$O(nlognlogv)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;
vector<int> vec;
int n, ch[2000005][2], tot;
inline void insert(int& rt, int x, int p)
{
    if (rt == 0) rt = ++tot, ch[rt][0] = ch[rt][1] = 0;
    if (p == -1) return;
    insert(ch[rt][(x >> p) & 1], x, p - 1);
}
inline long long query(int rt, int x, int p)
{
    if (p == -1) return 0;
    int c = (x >> p) & 1;
    if (ch[rt][c]) return query(ch[rt][c], x, p - 1);
    return query(ch[rt][c ^ 1], x, p - 1) ^ (1ll << p);
}
long long f(vector<int> vec, int p)
{
    if (vec.size() == 0 || p < 0) return 0;
    vector<int> tmp[2];
    for (int i : vec) tmp[(i >> p) & 1].push_back(i);
    long long ans = 0;
    int rt = 0;
    if (tmp[0].size() && tmp[1].size()) {
        tot = 0, ans = 1l << (p + 1);
        for (int i : tmp[0]) insert(rt, i, 30);
        for (int i : tmp[1]) ans = min(ans, query(rt, i, 30));
    }
    // cout << ans << endl;
    return 1ll * ans + f(tmp[0], p - 1) + f(tmp[1], p - 1);
}
int main()
{
    scanf("%d", &n);
    for (int i = 1, x; i <= n; i++) scanf("%d", &x), vec.push_back(x);
    printf("%lld\n", f(vec, 30));
}