简介
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永无乡”是个不错的例题
