简介

trie(retrieval)树,一种存储多个有序序列的树,在存储前缀相等次数多的数据时有很大的优势

一般来说,trie树是用于字典树,但这篇文章不谈字典树,而谈一谈它的近亲——binary trie

如果将固定字长的正整数的二进制看作一个01有序序列(从高位往低位存储,允许前导零填充满位数),那么就可以直接存储到trie树里了,而这种trie树称作binary trie

这棵树有一个明显的特点,一个节点最多只有两个儿子,分别是0儿子和1儿子,因此空间复杂度可以近似的看成O(nBIT)

用途?十分好写的“平衡树”

(出门必备的骗分神器……几分钟种植一棵“平衡树”……)

加引号是因为它本质是权值线段树,因为在trie树上的进入左右儿子的过程本质上是在权值线段树上往[l,mid]或者[mid+1,r]进行移动,因为01分类法使得它就是基于区间的二分

至于操作,就类似于权值线段树上的操作了,看代码更加直观

当然,简洁的代码背后是某些天坑

1.空间消耗过大,如果有n个数字那么空间消耗为O(nw)

2.插入浮点数?两种方法,第一种是离散化之后当成int来搞,不过一般题是不支持离线的样子,第二种是将浮点数看成高位和低位拼接起来的一个数串,不过空间复杂度需要再乘二

3.插入负数?这样可以加上一个数使得所有数都大于等于零(输出的时候再减去就行)

4.插入非数字?不过这样的话只能离线读进去后hash编码了,或者可以事先得知大小关系

可持久化之后,就可以解决区间上的查询了,跟可持久化线段树差不多

启发式合并也是很支持的

1.对于每棵树维护一个保存着所有值的链表(vector或者list随意),合并的时候直接将较小的那棵树整体放入垃圾回收装置(这个就随意了,array、queue、list、vector都行),然后遍历链表并插入到较大的那棵树里,最后将小的那棵树的链表直接接到大的那棵树的链表的结尾(这是O(1)的,如果使用vector的话就是O(n)的,不过也没什么关系,但是不能用array,因为开不下数组啊(dynamic array另说))

再分配新节点的时候,如果当前垃圾回收装置非空,那么就拿起末尾的那个节点,由于存储的时候没有删除它的子节点的那些信息,所以将它的左右节点再分别存入回收装置,然后对拿起的这个节点进行清理相关信息并当做新节点返回

2.当然其实直接对较小的那棵树dfs一遍搞出所有的值就行了……插入后把较小的那棵树直接扔到垃圾回收装置里就行……

3.貌似trie也可以跟线段树一样直接合并……但好像垃圾回收的时候比较惨(某一些可以回收,某一些不需要回收……)……

GC是一个很神奇的东西,因为它只存删除的那棵树的树根,真正做到了O(1)删除一棵树,O(1)新建节点

“HNOI2012永无乡”是个不错的例题

代码

luogu P3369 普通平衡树

HNOI2012 永无乡