字典树

题目链接：P8306 【模板】字典树

①什么是字典树

字典树，又称Trie树，用于保存排序大量的字符串。其特点是能存储字符串的公共前缀，从而实现快速查询。

②字典树的应用

字典树应用多样，比如最长公共前缀的查找，字符串排序，字符串的快速检索等等。

③字典树的基本操作

无论什么字典树都离不开以下几点操作：建立、查找、插入

建立

字典树有三个性质：①根节点不存储任何数据，我们称之为虚点 ②从从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串 ③每个节点的所有子节点包含的字符都不相同

因此，我们可以用一个二维数组t[N][N]来表示字典树，但这里和一般的树状数组不同，我们用t[u][c]来表示节点u代表的字符串后面添加一个字符c所形成的字符串的节点。这里类似于链表，其中c的取值取决于我们的字符集的大小。那么我们的建树就显而易见了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//字符转化成为ASCII码
int getnum(char x)
{
    if(x>='A'&&x<='Z')
        return x-'A';
    else if(x>='a'&&x<='z')
        return x-'a'+26;
    else
        return x-'0'+52;
}
//建树
void insert(string s)
{
    int p = 0;
    for(int i=0;i<s.size();i++)
    {
        int x = getnum(s[i]);
        if(t[p][x] == 0) t[p][x] = id++;
        p = t[p][x];
        cnt[p]++;
    }
}

这里要知道几个变量的作用：

  • id：id即为每一个结点的编号，id的大小只与插入字典树的先后顺序有关
  • p：p是插入时的当前节点编号，从虚点开始。在for循环中，t[p][x]一开始表示虚点到x的字符串，如果为0表示不存在，那么我们就根据当前的id建树

这也可以称之为字典树的初始化过程，时间复杂度为O(n)，显然和字符串的长度成线性关系。那么既然建立都有O(n)的时间复杂度了，字典树究竟强大在什么地方呢？在于它均摊O(1)的查询

查询

根据我们刚才的思路，对于字典树，t[p][x]一开始表示p到x的字符串。
那么我们给定一个字符串进行查询，我们显然是每一位的查询，假若x为我们的每一位字符，我们的t[p][x]就完成了当前字符的查询。

1
2
3
4
5
6
7
8
9
10
11
12
13
//查询
int find(string s)
{
    int p = 0;
    for(int i=0;i<s.size();i++)
    {
        int x = getnum(s[i]);
        //没有找到
        if(t[p][x] == 0) return 0;
        p = t[p][x];
    }
    return cnt[p];
}

当p=0的时候（即在虚点的时候），若t[p][x]为0，即说明字符串不存在，这是显然的。因为我们任何字符串都是从虚点开始。接下来我们重点分析这个cnt数组的作用

  • cnt：由建树过程我们容易知道cnt[i]表示的是以i为结尾的字符串个数。假如为0表示没有以该字符结尾的字符串。

至此为止，我们完成了字典树的所有操作。易知查询的时间复杂度为O(k)，k为查询字符串的长度，均摊时间复杂度为O(1)

应用

维护前缀个数

模板题即为这种题，我们只需要得到cnt即可。cnt就是我们维护的前缀个数

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

const int N = 3e6+10;
int t[N][65],cnt[N],id = 1,n,q,m;
string str;

//字符转化成为ASCII码
int getnum(char x)
{
    if(x>='A'&&x<='Z')
        return x-'A';
    else if(x>='a'&&x<='z')
        return x-'a'+26;
    else
        return x-'0'+52;
}
//建树
void insert(string s)
{
    int p = 0;
    for(int i=0;i<s.size();i++)
    {
        int x = getnum(s[i]);
        if(t[p][x] == 0) t[p][x] = id++;
        p = t[p][x];
        cnt[p]++;
    }
}
//查询
int find(string s)
{
    int p = 0;
    for(int i=0;i<s.size();i++)
    {
        int x = getnum(s[i]);
        //没有找到
        if(t[p][x] == 0) return 0;
        p = t[p][x];
    }
    return cnt[p];
}

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> m;
    while(m--)
    {
        for(int i=0;i<=id;i++)
            for(int j=0;j<=122;j++)
                t[i][j] = 0;
        for(int i=0;i<=id;i++)
            cnt[i] = 0;
        id = 1;
        cin >> n >> q;
        for(int i=1;i<=n;i++)
        {
            cin >> str;
            insert(str);
        }
        for(int i=1;i<=q;i++)
        {
            cin >> str;
            cout << find(str) << endl;
        }
    }
    return 0;
}

本题卡常严重，必须要关闭同步以及删去memset，否则会出现严重的tle

维护异或极值

题目链接

首先我们要知道一个性质：随便指定一个根 root，用 T(u, v) 表示 u 和 v 之间的路径的边权异或和，那么 T(u,v)=T(root, u) ^ T(root,v)，因为 LCA 以上的部分异或两次抵消了。

知道这个性质，我们就可以把整棵树插入到一个trie中，用这个性质快速求出异或值，从 trie 的根开始，如果能向和 T(root, u) 的当前位不同的子树走，就向那边走，否则没有选择。

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

const int N = 100010;

int head[N], nxt[N << 1], to[N << 1], weight[N << 1], cnt;
int n, dis[N], ch[N << 5][2], tot = 1, ans;

void insert(int x) {
  for (int i = 30, u = 1; i >= 0; --i) {
    int c = ((x >> i) & 1);  // 二进制一位一位向下取
    if (!ch[u][c]) ch[u][c] = ++tot;
    u = ch[u][c];
  }
}

void get(int x) {
  int res = 0;
  for (int i = 30, u = 1; i >= 0; --i) {
    int c = ((x >> i) & 1);
    if (ch[u][c ^ 1]) {  // 如果能向和当前位不同的子树走，就向那边走
      u = ch[u][c ^ 1];
      res |= (1 << i);
    } else
      u = ch[u][c];
  }
  ans = max(ans, res);  // 更新答案
}

void add(int u, int v, int w) {  // 建边
  nxt[++cnt] = head[u];
  head[u] = cnt;
  to[cnt] = v;
  weight[cnt] = w;
}

void dfs(int u, int fa) {
  insert(dis[u]);
  get(dis[u]);
  for (int i = head[u]; i; i = nxt[i]) {  // 遍历子节点
    int v = to[i];
    if (v == fa) continue;
    dis[v] = dis[u] ^ weight[i];
    dfs(v, u);
  }
}

int main() {
  scanf("%d", &n);

  for (int i = 1; i < n; ++i) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    add(u, v, w);  // 双向边
    add(v, u, w);
  }

  dfs(1, 0);

  printf("%d", ans);

  return 0;
}