简介

Trie 树是用来存储和查找字符串或数字等构成元素不多的数据结构，多用来匹配特定前缀，C++ 中使用和静态链表类似。下面以一道例题记录 Trie 树的用法：

维护一个字符串集合，支持两种操作：

  1. I x 向集合中插入一个字符串 xx；
  2. Q x 询问一个字符串在集合中出现了多少次。

共有 NN 个操作，所有输入的字符串总长度不超过 10510^5，字符串仅包含小写英文字母。

题目链接：AcWing 835。

以 tree[i] 为一个节点，node[k] 表示 k 对应的下一个节点，这里以 idx 自增的形式分配新节点。

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;

const int N = 1e5+10;
int tree[N][26], cnt[N], idx;
char x[N];

void insert(char* str) {
    int p = 0;
    for (int i = 0; str[i]; i++) {
        int k = str[i] - 'a';
        if (!tree[p][k]) tree[p][k] = ++idx;
        p = tree[p][k];
    }
    cnt[p]++;
}

int find(char* str) {
    int p = 0;
    for (int i = 0; str[i]; i++) {
        int k = str[i] - 'a';
        if (tree[p][k] == 0) return 0;

        p = tree[p][k];
    }
    return cnt[p];
}

int main() {
    int n; char op[2];
    scanf("%d", &n);
    while (n--) {
        scanf("%s%s", op, x);
        if (*op == 'I') insert(x);
        else printf("%d\n", find(x));
    }
    return 0;
}

最大异或对

在给定的 N∈[1,105]N \in [1, 10^5] 个整数 A1,A2,⋯ ,AN∈[0,231]A_1,A_2,\cdots,A_N \in [0, 2^{31}] 中选出两个进行 xor ^（异或）运算，得到的结果最大是多少？

第一行输入一个整数 NN。

第二行输入 NN 个整数 A1A_1 ~ ANA_N。

题目链接：AcWing 143。

这题需要将每个数字的二进制用 Trie 树存起来，类似二叉树那样。但是要注意，有 10510^5 个数的时候有 31×10531\times10^5 个二进制位，所以直接用 1e5 作为节点的长度是不可以的，要用 31e5 才够。

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
#include <bits/stdc++.h>
using namespace std;

const int N = 31e5;
int tree[N][2], idx;

void insert(int a) {
    int p = 0;
    for (int i = 30; i >= 0; --i) {
        int b = (a >> i) & 1;
        if (!tree[p][b]) tree[p][b] = ++idx;
        p = tree[p][b];
    }
}

int find(int a) {
    int p = 0, res = 0;
    for (int i = 30; i >= 0; --i) {
        int b = (a >> i) & 1;
        if (tree[p][!b]) {
            res = res * 2 + !b;
            p = tree[p][!b];
        } else {
            res = res * 2 + b;
            p = tree[p][b];
        }
    }
    return res;
}

int main() {
    int n, a, res = 0;
    scanf("%d", &n);
    while (n--) {
        scanf("%d", &a);
        insert(a);
        res = max(res, find(a) ^ a);
    }
    printf("%d\n", res);
    return 0;
}

寻找的时候从高位到低位，尽量使每一位都不同，但是如果没有只能退而求其次了。其中，res * 2 + b 也可以是 res << 1 + b，但我这样写时间也没什么显著的变化，反而还多花了一点时间。至于这两个写法等价的原因如下：

a=∑i=0N(bi⋅2i)2a=∑i=0N(bi⋅2i+1)=a≪1\begin{aligned} a&=\sum_{i=0}^N(b_i\cdot 2^i)\\ 2a&=\sum_{i=0}^N(b_i\cdot2^{i+1})\\ &=a\ll1 \end{aligned}

其中 bib_i 代表相应位置上的二进制位。

最大异或和

给定一个非负整数序列 a，初始长度为 N。

有 M 个操作，有以下两种操作类型：

  1. A x：添加操作，表示在序列末尾添加一个数 x，序列的长度 N 增大 11。
  2. Q l r x：询问操作，你需要找到一个位置 p，满足 l≤p≤r，使得：a[p] xor a[p+1] xor … xor a[N] xor x 最大，输出这个最大值。

题目链接：AcWing 256。

首先进行一个前缀和的操作，求出前缀异或值，对于一个解 pp，它对应的值就是 Sp−1 xor SN xor xS_{p-1} \text{ xor } S_N\text{ xor }x

如果只是 1∼R1\sim R，只需要在第 RR 个版本的可持久化 Trie 中查询即可，但是这里是 L∼RL\sim R，那在查找的时候需要判断一下某个节点的版本是否大于等于 LL，这样就可以处理 L∼RL\sim R 区间内的最大值了。

说实话这题我没太搞清楚，但它是个紫题，就等如果能过复赛再来研究吧。

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
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 6e5+10, M = 25*N;
int s[N];
int tr[M][2], latest[M], root[N], idx;

void insert(int i, int k, int p, int q)
{
    if (k < 0) {
        latest[q] = i;
        return;
    }

    int v = s[i] >> k & 1;
    if (p) tr[q][v ^ 1] = tr[p][v ^ 1];

    tr[q][v] = ++idx;
    insert(i, k - 1, tr[p][v], tr[q][v]);
    latest[q] = max(latest[tr[q][0]], latest[tr[q][1]]);
}

int query(int u, int c, int l) {
    for (int i = 23; i >= 0; i--) {
        int v = c >> i & 1;
        if (latest[tr[u][v^1]] >= l) u = tr[u][v^1];
        else u = tr[u][v];
    }
    return c^s[latest[u]];
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    latest[0] = -1;
    root[0] = ++idx;
    insert(0, 23, 0, root[0]);
    for (int i = 1; i <= n; i++) {
        int v; scanf("%d", &v);
        s[i] = s[i-1] ^ v;
        root[i] = ++idx;
        insert(i, 23, root[i-1], root[i]);
    }
    while (m--) {
        char op[2];
        scanf("%s", op);
        if (*op == 'A') {
            int x; scanf("%d", &x);
            n++;
            root[n] = ++idx;
            s[n] = s[n-1]^x;
            insert(n, 23, root[n-1], root[n]);
        } else {
            int l, r, x; scanf("%d%d%d", &l, &r, &x);
            printf("%d\n", query(root[r-1], s[n]^x, l-1));
        }
    }
    return 0;
}