可持久化的trie以及二进制trie
这里不会对trie本身进行介绍。
让我们首先从一道题目说起CF916D Jamie and To-do List
题目要求设计出一种储存字符串的优先级的数据结构，支持如下操作：
- set a x，将字符串a的priority设置为x，假若a原本存在，则将原优先级修改为x。
- remove a，将字符串a的记录移除，假若a不存在，则do nothing。
- query a，查询有多少个字符串的priority严格小于a
- undo d，假设当前是第i次操作，则将结构恢复到第i-d-1操作后的状态
- 操作次数上限为10^5，字符串长度不会超过15，x范围是[1,10^9]，保证undo操作合法
我们首先不考虑undo操作的话，经过思考，我们会发现应该需要两个数据结构，第一个用于维护字符串和priority的对应关系；第二个用于储存所有的priority用于查询rank。显然，第一个结构随便用一个hashmap或者trie，第二个使用一个能够查询rank的BST，e.g. treap, splay就能够完成。
ds<-> data structure
然而，现在+上了undo操作，这意味着我们需要把历史记录保存下来。具体实现便是使用两个数组firstds[max_operation_num], secondds[max_operation_num]在进行第i次操作时便读取firstds[i-1]和secondds[i-1]中的数据结构，然后将修改之后的数据结构放入firstds[i]和secondds[i]中，注意！我们这里不能够对第i-1位上的两个数据结构进行任何修改。
假设我们依然采用之前的hashmap和BST，每一次操作我们都需要将之前的结构copy一遍然后再进行操作，无论是空间上还是时间上都感觉……太暴力了。
让我们考虑一下第一个结构使用trie以及set一个原本不存在的字符串的情况。无妨说第一条指令是set aaa 5，insert之后的结果就是
第二条指令是set bbb 4，再次insert之后的结果就是
可以看出，前后的trie仅仅只有一条链的变化。说得更加详细一点：
- 一个set a x操作后的trie必然会至少多出一个新节点n，就是用于存储新字符串优先级的节点(图一中的5和图二中的4，因为该字符串原本不存在
- 对于1中所说的新节点n，我们需要一个新节点n’来使n’成为n的父亲，其中n’通过a中的最后一个字符指向n
- 由于n’同样是一个新节点，我们依然需要一个新节点n’’来使n’’成为n’的父亲，其中n’’通过a中的倒数第二个字符指向n’
- ……按照上述做法不断往上新建节点，最终就形成了一条链
同样也是前后只有一条链的变化，很容易让人联想到可持久化线段树中的操作。
因此我们copy实际上并不是copy整个trie树，而是仅仅只是新建一条链，剩下的节点和之前的树共用。下图是存有aaa的trie中先插入aab再插入cc的过程。第一排代表着理论上发生的情况，第二排是实际上共用了节点的情况
刚刚讨论的情况是set一个原本不存在的字符串，假若是set是更新一个字符串的priority呢？按照如上的分析，结果是一样的，同样是修改了一条链而已。对于remove a操作呢？看做set a 0即可。可持久化trie的基本思想到此结束
二进制trie：用于储存整数的trie，可以用于查询rank。对于一个int，我们由高位向低位储存一个整数。与普通trie不同的是，二进制trie在插入的时候并不是仅仅是最后一个节点有特别的值，而是从根节点开始到最后一个节点整条链上的值都进行修改。例如，向二进制trie中插入1、2和3如图4
我们可以发现，从根节点到某一个节点n所经过的路径path，节点n上的对应的值就是以path为前缀的int出现次数。那么对应某一个int n我们如何查询它的rank呢？算法描述如下：
定义局部变量now=root，ans=0表示答案，迭代变量i : 从n的最高位->n的最低位
1 | if(i==1) |
正确性？想一想就知道了嘛
最后，题目的AC代码:
在循环写法中set与add的时候为什么需要一个tmp变量呢？答案是我们需要让新节点指向原来的相同位置上的节点的子节点来达到共用的效果，tmp变量跟随着now同时向下移动来进行copy node的操作。假若tmp为空了，那么也就没有子节点可以共用了，tmp也就没有意义了。