Trie 讲义

Trie , 即字典树，是一种非常简单的数据结构，可以轻松处理字符串之间的前缀关系。

我们通过几个例子来理解 Trie 是怎样工作的。

现在，我们将依次插入几个字符串。

插入 king

插入 kin

插入 kind

插入 kiev

插入 kan

插入 str

我们可以看到，一个字符串插入 Trie 的过程，就是其每个字符从根节点到下依次插入的过程。一个字符串插入一后，就会形成一条从根节点延伸向下的树链。

这可以衍生出许多有趣的性质。

比如 king 和 kind 两个字符串，它们在插入之后，其树链就会有一段公共部分，即它们的公共前缀。

模板题

附参考代码

01 Trie

当然，Trie 不仅可以用于处理字符串，也可以将数字当做字符串与 Trie 使用。

例如，将数字以二进制的形式插入，就可以得到 01 Trie

01 Trie 的写法与标准的 Trie 类似。

代码

最大异或对

我们尝试用 Trie 解决这道题。

我们现将所有的数从 高位 到 低位 以 二进制 的形式插入。

然后考虑每一个数 $x$，找到另一个数 $y$ ，使两者的 异或 最大。

贪心地想，我们应该尽可能寻找与 $x$ 尽可能相反的数，并且从 高位 到 低位 考虑。由于我们已经将所有的数从 高位 到 低位 插入 01 Trie 中，我们可以在 01 Trie 上从上到下尽可能寻找与 $x$ 的对应的位数相反的数，然后就可以使 $x$ 的 异或 最大。

int query(Node* root,int x) {
	Node* current=root;
	int res=0;
	for(int i=31; i>=0; i--) {
		bool b=(x>>i)&1;
		if(current->child[!b]) {
			res+=(1<<i);
			current=current->child[!b];
		} else {
			current=current->child[b];
		}
	}
	return res;
}

对于每一个数进行一次上述操作结合起来即可得到答案。

参考代码