题目见BZOJ…

其实就是zej在WC讲的那题的简化版,不过简单了不少,我就自己推了一下.

让我们考虑一棵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上速度完艹各种平衡树。。。空间也不会挂了。。