RainAir
My OI Blog
RainAir
Trie 树学习笔记
Trie 树学习笔记

定义

又称单词查找树,字典树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希树高。
https://blog.aor.sd.cn/wp-content/uploads/2018/12/d62a6059252dd42a745cc2c2033b5bb5c9eab806.jpg

实现

首先我们以一道例题来看。

首先它给出了一个字符串集合,然后每次给出一个字符串询问有多少个字符串的前缀包含它。
如果暴力的话就会比较崩溃,这里我们可以使用一种优化。考虑暴力的时间瓶颈在于每次查询的时候必须从头开始重复计算,于是我们可以考虑用某种方式来把一些字符串相同的前缀合并起来表示,于是我们想到了
那么如何表示每一个单词呢?
我们把字母放在边上,如果这个节点是一个单词的结尾就打个标记就好了。
例如上图中的单词就有:abc,abd,abcd,b,bcd,efg,hi

结构体定义

插入操作

询问操作

总体来说还是十分通俗易懂的,trie 树的核心思想就是压缩数据规模,这样原来需要 $O(nm)$ 的复杂度被降到了 $O(size \times len)$ ,其中 $size$ 表示字符集大小,$len$ 表示字典中单词最大长度(即 trie 树最大深度)

题目练习

接下来我们来看一道变式题。
最长异或路径

题目描述

给定一棵 $n$ 个点的带权树,结点下标从 $1$ 开始到 $n$。寻找树中找两个结点,求最长的异或路径。
异或路径指的是指两个结点之间唯一路径上的所有边权的异或。

解题报告

我们用 $\oplus$ 来表示异或。
首先发现异或有两个重要的性质:$a\oplus a = 0$,$a \oplus 0 = a$
所以我们发现询问两点之间的路径异或和相当于询问这两个点分别到根节点的异或和的异或值(因为 lca 到根的多余部分被重复异或抵消)。
一边 dfs 后问题转化为从一个序列中选择两个数使他们的异或和最大。
我们可以对所有数字按照从高位到低位的顺序建立一棵 01 trie 树,枚举第一个数,贪心的从二进制高位开始考虑第二个数,选择与当前这个数字二进制位不一样的路径走下去,最后取个 max 就可以了。

代码

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/344
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

Trie 树学习笔记
定义 又称单词查找树,字典树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的…
扫描二维码继续阅读
2018-12-10
标签
近期评论