字典树笔记

阿丑 · 2022-09-05 20:48:03 · 算法·理论

例题

1.doubt

• 给出数组 a,b，让 a,b 以某种顺序排序，令 c_i=a_i\operatorname{xor} b_i，使 c 字典序最小。

考虑对 a 和 b 分别建出 01-Trie，并将两棵 Trie 合并：先 0 对 1、1 对 0 合并，再 0 对 0、1 对 1 合并。

貌似很暴力，但分析一下复杂度：如果遍历到一种状态没有因为子树为空返回（访问空状态的复杂度和总非空状态数线性相关，每次 \mathcal O(1)，可以不管），那么一定会从该状态继续遍历到下一层，除非该层是底层。即，搜索树的所有叶子节点都是底层。

最底层的每个非空状态都至少需要匹配两棵 Trie 的各一个元素，而总共只会匹配 \mathcal O(n) 次，所以搜索树的叶子节点只有 \mathcal O(n) 个，总大小 \mathcal O(n\log V)，其中 V 是值域。