01-Trie的原理与应用
CF1895D这道题用到了01-Trie，那就再来复习一下01-Trie。
简介
01-Trie 中文名 是01字典树 ，是一种特殊的字典树，它的字符集只有\(\{0,1\}\)，主要用来解决一些异或问题。
背景
所以，我们先来看一下字典树。
应用：
1.检索字符串
字典树最基础的应用——查找一个字符串是否在「字典」中出现过。（ps:最容易理解）
2.AC 自动机
trie 是 AC 自动机 的一部分。（先不学）
3.维护异或极值
将数的二进制表示看做一个字符串，就可以建出字符集为\(\{0,1\}\)的 Trie 树。
4.维护异或和
01-trie 是指字符集为\(\{0,1\}\)的
trie。01-trie 可以用来维护一些数字的异或和，支持修改（删除 +
重新插入），和全局加一（即：让其所维护所有数值递增
1，本质上是一种特殊的修改操作）。
如果要维护异或和，需要按值从低位到高位建立 trie。
重点来研究一下3两点。
正文
问题引入
给一个长为 \(n\) 的数列，要求一个\(a_i,a_j\)，使得\(a_i\ xor\ a_j\)最大。
题解
重点是解决已知\(a_i\)，如何找到异或和最大的\(a_j\)
我们先建一个01-Trie
现在对于上面问题，我们贪心地解决即可。如果我们要找与给定数异或最大的数，就尽可能走与该数当前位不同的路径。反之则尽可能走与当前位相同的路径。
这样可以在$n $的复杂度下求出极值。
总结
思想就是这些，代码难度也一般。
在今后遇到异或求极值的时候或是求字符串前缀、是否出现等问题的时候，trie是一个很不错的选择。