首页 程序设计 数据结构

# Trie 树的介绍

TrieTrie 树（字典树），是一棵像字典一样的树

显然，字典树一个典型的应用就是查找字符串是否出现过，下面给出一个典型例题

# Trie 字符统计

# 题目大意

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

  • I x ：向集合中插入一个
  • Q x ：询问一个字符串在集合中出现过多少次

# 数据范围

  • 1≤N≤2×1041 \le N \le 2 \times 10^4，代表操作数
  • 保证字符串中仅包含小写字母

# 题解

trie[i][j] 表示，以 ii 为父节点的，连 jj 的字符的个数（字符串 ijij，仅考虑两个）

C++
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
int trie[N][27], cnt[N], idx = 0;

void insert(string s) {
    int root = 0;

    for (int i = 0; i < s.size(); i++) {
        int u = s[i] - 'a' + 1;

        if (!trie[root][u])
            trie[root][u] = ++idx;

        root = trie[root][u];
    }

    cnt[root]++;
}

int query(string s) {
    int root = 0;
    for (int i = 0; i < s.size(); i++) {
        int u = s[i] - 'a' + 1;

        if (!trie[root][u])
            return 0;

        root = trie[root][u];
    }

    return cnt[root];
}

int t;
char op;
string s;

void solve () {
    cin >> t;
    while (t--) {
        cin >> op >> s;
        if (op == 'I')
            insert(s);
        else
            cout << query(s) << endl;
    }
}

TrieTrie 树可以应用于求异或和。

# 最大异或对

# 题目大意

在给定的 NN 个整数 A1,A2,...,ANA_1,A_2, ..., A_N 中任选两个进行异或运算，最大结果是多少？

# 数据范围

  • 1≤N≤1051 \le N \le 10^5

# 题解

trie[i][j] 表示，ii 为编号的，当前二进制位的值

  • trie[i][j] != 0 ：表示子节点的编号
  • trie[i][j] == 0 ：表示没有子节点

C++
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
int n, a[N], trie[M][2];
int res = 0, idx = 0;

void insert(int x) {
    int root = 0;

    for (int i = 30; i >= 0; i--) {
        int &s = trie[root][x >> i & 1];

        if (s == 0)
            s = ++idx;

        root = s;
    }
}

int query(int x) {
    int res = 0, root = 0;

    for (int i = 30; i >= 0; i--) {
        int s = x >> i & 1;

        if (trie[root][!s])
            res += 1 << i, root = trie[root][!s];
        else
            root = trie[root][s];
    }

    return res;
}

void solve () {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i], insert(a[i]);

    for (int i = 1; i <= n; i++)
        res = max(res, query(a[i]));

    cout << res << endl;
}