一种用线段树实现 01 Trie 的思路

前提是值域允许，而且还是 ${\log }^2$ 的。

比如给定序列 $a_{1\dots n}$，每次询问给出 $x$，求 $max(x\mathrm{xor}{a}_i)$。

可以使用 01 Trie，从高到低位尽量往不同的方向走。

但也可以枚举每一位，求出满足 $y\in a_{1\dots n}$ 且能够让 $x\mathrm{xor}y$ 最大的 $y$。

把 $a$ 全部丢进值域线段树，如确定到 $\bullet \bullet \bullet i\text{ - - -}$ 这一位（圆点是已经确认的高位），根据贪心，如果存在一个数 $\bullet \bullet \bullet (i\mathrm{xor}1)000$ 和 $\bullet \bullet \bullet (i\mathrm{xor}1)111$，那么 $y$ 的这一位就可以取 $i\mathrm{xor}1$，而这就是一个区间查询的操作。

然后就没了，同理可以用主席树爆炒可持久化 01 Trie，P3293 [SCOI2016] 美味。