01-Trie 的应用

01-trie 就是把一个整数的二进制表示看成一个 01 字符串然后插进字典树里。

因为我们的 01-trie 要体现像平衡树一样的大小关系，同时有时还需要知道异或最值等信息，所以一般都是从高位往低位插。

01-trie 的一个节点一般可能需要维护这些信息：左右儿子、子树内包含的整数个数、子树内插入整数的最大值、子树内最大编号等。

异或极值

有一个序列，每次给出一个整数，问这个整数异或上序列中一个数的异或和的最大值是多少。

对序列建出 01-trie，考虑从根节点开始游走至最底层，于是每次看往左右哪边走更优。

例题 -INF：野猪骑士

基本思想是分治，然后用 01-trie 做。

这题有一个找序列中异或 \(x\) 大于 \(y\) 的位置中编号最大的位置。

也可以对序列建 01-trie，然后同样是从根节点开始游走，分类讨论一下最优性，注意我们还需要维护子树内插入数的编号最大值。

例题 1：最长异或路径

钦定一个根节点，先处理出每个点到根的异或和 \(s_i\)，则任意两个点的路径的异或和都为 \(s_i\oplus s_j\)，因为它们 LCA 到根的路径异或两次没有贡献。

然后就变成了任意两数的异或最大值，对 \(s\) 建出 01-trie，枚举一个 \(s_i\) 让它在 01-trie 上匹配即可。

例题 2：异或粽子

配合堆或可持久化 01-trie。

维护异或和

需要从低位往高位建 01-trie。

全局加 1

所有数的数值加 \(1\)。

01-Trie 合并

类似于合并线段树的思路，均摊复杂度是正确的。

维护异或和 & 全局加 1 & 01-Trie合并 例题：[Ynoi2010] Fusion tree

实现平衡树

我们可以用 01-trie 代替平衡树，可以做到 \(O(n\log V)\)，其中 \(V\) 是值域。

实现可持久化平衡树

把 01-trie 做平衡树的做法可持久化即可，01-trie 可持久化的方法与可持久化线段树类似。