CloudySky

纵使世界万般残酷

总有温暖值得守护

字典树 学习笔记

字典树是 OI 中常用的数据结构，实现起来较为简单且常数较小，具有较高可拓展性，目前应用比较广泛的是 字符串 TrieTrie 树， ACAC 自动机， 01Trie01Trie ，和可持久化 01Trie01Trie ，它甚至可以实现平衡树的部分功能。

字符串 TrieTrie

时间复杂度: O(n)O(n)

能方便地判定一个模式串是否为一些文本串的前缀 或 在文本串中出现过，又或者有些题会要求判出现次数。

具体实现（以判出现次数为例）：

  • 读入文本串时，对于任意一个文本串，将每个字符作为边，并在路径末端节点（即每个字符串的末尾，并非每条边的终点）权值 +1+1，表示当前位置有一个字符串结束了。
  • 每跳一个字符，如果当前节点已经存在就直接跳，否则新建一个节点。
  • 匹配时，如果跳到某个节点不存在，直接 return false ，如果跳完所有的边还在树上就 return v[p]
代码实现： 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 字典树 学习笔记
// 字符串 Trie 具体实现
int trie[Maxn][26], v[Maxn], tot;
// trie 数组记录边的信息, v 记录点的信息, tot 为总结点数
void insert(char* s) {
  int p = 0, n = strlen(s);
  for (int k = 0; k < n; ++k) {
    int ch = s[k] - 'a';    // 将字符转为 int
    if (!trie[p][ch])
      trie[p][ch] = ++tot;  // 如果没有就新建节点
    p = trie[p][ch];        // 直接跳
  }
  v[p]++;                   // 标记跳到这里有一个字符串结束了
}

int search(char* s) {
  int n = strlen(s), p = 0;
  for (int k = 0; k < n; ++k) {
    p = trie[p][s[k] - 'a'];  // 直接跳
    if (!p) return false;     // 节点不存在
  }
  return v[p];                // 已经跳完所有边
}

01Trie01Trie

时间复杂度:O(nlogn)O(nlogn)

01 trie 是将数字按照二进制位从高到低依次表示存入字典树的数据结构，经常被用来解决最大异或和问题。

具体实现：

  • 将所有数按照二进制存入 trie 树，长度不够的在高位补 0，保证树的深度一致。
  • 每跳到一个节点就将当前节点的权值 +1,表示沿着当前节点往下走存在多少个数。
  • 查询两个数的最大异或和时，能向不同的方向走，就向不同的方向走，不能就向同一方向走，边跳边记录数字，最终这两个数即为这个序列中异或和最大的两个数。
代码实现： 
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
// 字典树 学习笔记
// 01Trie 具体实现
void insert(int val) {
  int x = 0;
  bool c;
  for (int k = (1 << 30); k; k >>= 1) {  //最高位补齐
    c = val & k;
    if (!trie[x][c]) {  //如果没有就新建节点
      trie[x][c] = ++tot;
    }
    x = trie[x][c];  //跳到子节点
  }
}

int ask(int val) {
  int ans = 0, x = 0;
  bool c;
  for (int k = (1 << 30); k; k >>= 1) {
    c = val & k;
    if (trie[x][!c]) {
      //如果存在相反的方向就向相反的方向跳,同时计入答案
      ans += k;
      x = trie[x][!c];  //这里直接就入了异或和
    } else
      x = trie[x][c];  //否则就向相同的方向跳
  }
  return ans;
}

可持久化 01Trie01Trie

时间复杂度：O(nlogn)O(nlogn)

可持久化 01Trie01Trie 与非可持久化 01Trie01Trie 功能类似，支持静态区间查询。

具体实现与线段树类似。

代码实现： 
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
// 字典树 学习笔记
// 可持久化 01Trie 具体实现
//v数组记录的是当前这位及以上数的个数
void insert(int p, int lst, int val) {
  for (int i = 28; i >= 0; --i) {
    v[p] = v[lst] + 1;  //先继承
    if ((val & (1 << i)) == 0) {
      if (!trie[p][0]) trie[p][0] = ++tot;  //后修改
      trie[p][1] = trie[lst][1];
      p = trie[p][0];
      lst = trie[lst][0];
    } else {
      if (!trie[p][1]) trie[p][1] = ++tot;
      trie[p][0] = trie[lst][0];
      p = trie[p][1];
      lst = trie[lst][1];
    }
  }
  v[p] = v[lst] + 1;
  return;
}

int ask(int p1, int p2, int val) {
  int ans = 0;
  for (int i = 28; i >= 0; --i) {
    bool t = (val & (1 << i));
    if (v[trie[p1][!t]] - v[trie[p2][!t]]) {  //能向相反方向跳,就向相反方向跳。
      ans += (1 << i);
      p1 = trie[p1][!t], p2 = trie[p2][!t];
    } else  //否则向相同方向跳
      p1 = trie[p1][t], p2 = trie[p2][t];
  }
  return ans;
}

TrieTrie 树实现平衡树功能

时间复杂度：O(nlogn)O(nlogn)

根据之前的内容，不难发现，TrieTrie 树可以实现在 O(logn)O(logn) 时间内找到序列中比某个数小的数的个数，且支持 O(log)O(log) 时间内修改操作，于是我们就可以借助 trie 树实现平衡树的功能。

Tire 树实现平衡树优点是常数较小，代码较好实现；缺点是对空间要求较大，容易被卡空间。

插入操作

具体实现：同 01trie 插入操作。

修改操作

具体实现：可以转为删除后插入操作。

1.2代码实现： 
1
2
3
4
5
6
7
8
9
10
11
12
// 字典树 学习笔记
// Trie 树实现平衡树功能 || 插入修改操作具体实现
void insert(int val, int k) {
  int p = 1;
  for (int i = Maxk - 1; i >= 0; --i) {
    int c = (val >> i) & 1;
    if (!trie[p][c])
      trie[p][c] = ++cnt;
    p = trie[p][c];
    v[p] += k;
  }
}

查询排名操作

具体实现：一位一位的匹配，如果当前位为 0 直接向左跳，否则将左半边计入答案，向右跳。

代码实现： 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 字典树 学习笔记
// Trie 树实现平衡树功能 || 查询排名操作具体实现
int check_nlt(int x) {
  int p = 1, ans = 0;
  for (int i = Maxk - 1; i >= 0; i--) {
    if ((x >> i) & 1) {
      ans += v[trie[p][0]];
      p = trie[p][1];
    } else
      p = trie[p][0];
    if (!p) break;
  }
  return ans;
}
//直接查到的是比 x 小的数的个数,排名要 +1

根据排名查询数值操作

具体实现：类似线段树二分，如果左边个数小于 k 直接向左跳，否则 查询右半边 排名为 k-左半边个数 的数。

代码实现： 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 字典树 学习笔记
// Trie 树实现平衡树功能 || 根据排名查询数值具体实现
int check_kth(int k) {
  int p = 1, ans = 0;
  for (int i = Maxk - 1; i >= 0; --i) {
    if (v[trie[p][0]] >= k)
      p = trie[p][0];
    else {
      ans |= (1 << i);
      k -= v[trie[p][0]];
      p = trie[p][1];
    }
  }
  return ans;
}

前驱后继操作

具体实现：可以转换为 3.4 操作的组合。

5.6代码实现： 
1
2
3
4
5
6
7
8
9
10
11
// 字典树 学习笔记
// Trie 树实现平衡树功能 || 前驱后继具体实现
int pre(int x) {
  return check_kth(check_nlt(x));
}

int nxt(int x) {
  int ans;
  ans = check_kth(check_nlt(x + 1) + 1);
  return ans;
}

本文作者：CloudySky
写作时间： 2021-08-19
最后更新时间： 2021-08-19
遵循协议： BY-NC-SA

Top