数据结构——字典树 学习笔记

字典树，也叫 trie 树。

检索字符串

本质是记录字符串前缀的一棵查找树，形态类似于：

字典树使用边表示字母，节点表示一个前缀，同时也可以在节点上记录状态 \(\mathit{tag}\)。

基本实现形如：

var:
	nex[0..siz][0..rng], idx
	est[0..siz], pre[0..siz]
function insert(str, map): -> void
	root := 0
	for c in str:
		pos := map(c)
		if nex[root][pos] = 0:
			nex[root][pos] := ++idx	// 分配节点
		p := nex[root][pos]
		++pre[p]	// 前缀计数
	est[p] := True	// 存在
function is_exist(str, map): -> boolean
	root := 0
	for c in str:
		pos := map(c)
		if nex[root][pos] = 0:
			return False
		root := nex[root][pos]
	return est[root]
function is_prefix(str, map): -> boolean
	root := 0
	for c in str:
		pos := map(c)
		if nex[root][pos] = 0:
			return False
		root := nex[root][pos]
	return True
function cnt_prefix(str, map): -> integer
	root := 0
	for c in str:
		pos := map(c)
		if nex[root][pos] = 0:
			return 0
		root := nex[root][pos]
	return pre[root]

01-trie

01-trie 是指字符集为 \(\{0,1\}\) 的 trie 树。01-trie 可以用来维护一些数字的异或和，支持修改（删除 + 重新插入），和全局加一。如果要维护异或和，需要按值从低位到高位建立 trie。

对于简单题来说，就是前面的板子不用修改。

难题我也不会，不知道咋用，见 https://oi-wiki.org/string/trie/#维护异或和 吧。

示例代码（P4551 最长异或路径）：

struct Trie {
    vector<array<int, 2>> ch; int idx;
    function<void(int)> insert = [&] (int x) {
        int root = 0; for (int k = 30; ~k; --k) {
            int pos = (x >> k) & 1;
            if (!ch[root][pos]) ch[root][pos] = ++idx;
            root = ch[root][pos];
        } return (void)("rp++");
    }; function<int(int)> query = [&] (int x) {
        int root = 0, r = 0; for (int k = 30; ~k; --k) {
            int pos = (x >> k) & 1;
            if (ch[root][pos ^ 1]) root = ch[root][pos ^ 1], r |= 1 << k;
            else if (ch[root][pos]) root = ch[root][pos];
            else throw("UNKNOWN ERROR");
        } return r;
    }; Trie(int N) { idx = 0, ch.resize(N); }
} trie(n * 31 + 5);

Reference

[1] https://oi-wiki.org/string/trie/