Compacted-Trie

让我们考虑一棵Trie。

注意到实际上有用的结点只有O(n)个。

那么我们像后缀树一样的压缩方法。可以得到空间O(n)的Trie。

插入删除修改的复杂度变成了O(min(n,W)),W表示位数

有啥用呢?首先是降低时间复杂度的常数,因为可以使用位运算一次往下前进很多步。

其次是狂降空间。 

比方说:

http://www.lydsy.com/JudgeOnline/problem.php?id=1146

这题

如果使用主席树的话空间复杂度是O(nlog^2n)了。

但是如果改用树状数组套compacted-Trie。空间复杂度就变成了O(nlogn)。

当然时间复杂度不变。

 

其实基本没啥用,不过在Int上速度完艹各种平衡树。。。空间也不会挂了。。