trie树 | Serendipity

type

status

date

slug

summary

定义

字典树，英文名 trie。顾名思义，就是一个像字典一样的树。

可以发现，这棵字典树用边来代表字母，而从根结点到树上某一结点的路径就代表了一个字符串。

举个例子，表示的就是字符串 caa。

字典树最基础的应用——查找一个字符串是否在 “字典” 中出现过。

01-trie 是指字符集为的 trie。01-trie 可以用来维护一些数字的异或和，支持修改(删除，重新插入)，和全局加一 (即让其所维护所有数值递增1，本质上是一种特殊的修改操作)。

如果要维护异或和，需要按值从低位到高位建立 trie。