(
课件网) 可持久化数据结构 信息学奥林匹克竞赛知识点（难点）精讲———数据结构【尖端】 可持久化的定义 我们对于一个数据结构，想维护其所有的历史版本 部分可持久化：允许访问历史版本，不能修改历史版本 完全可持久化：允许把目前版本替换为历史版本 Confluent persistent：允许合并历史版本，几乎不太能维护 可持久化线段树 如果每次都暴力复制整棵线段树，时间复杂度无法承受 考虑每次修改，线段树只有O( logn )个节点会被修改，所以我们可以对每个被修改的节点，将其复制一份进行修改 可持久化线段树 可以发现这样做，我们时间复杂度和空间复杂度都变成了O( mlogn )，比起暴力复制改善了很多 很多情况下，如果题目没有强制在线，那么我们可以用分治来解决，而不用可持久化 经典问题 给一个序列，每次查询区间的k小值 值域线段树 定义值域线段树：我们在离散的值域上建立一棵线段树，可以考虑预先进行离散化来缩小值域，这时线段树每个节点表示值在一个范围内的数，在这个例子中我们只需要统计一个范围内有多少数。 Solution 我们先维护出每个前缀的值域线段树，这个可以用刚才讲的可持久化的方法 每次从前缀[1,t]拓展到[1,t+1]的时候，即在t版本的值域线段树上插入a[t+1]这个值，并将这个版本记做第t+1个版本 发现可以用之前讲的技巧进行优化，使得复杂度做到O( nlogn ) Solution1 我们维护出了每个前缀的值域线段树，考虑怎么求出kth 发现可以二分答案，然后转化为区间中小于x的数个数 我们可以用r位置和l-1位置的值域线段树差分，即在两个历史版本的线段树上都查询小于x的数个数，来知道区间小于x的数个数 总时间复杂度O( nlogn + mlog^2n ) Solution2 在一棵值域线段树上，我们可以可以二分来求出kth 由于值域线段树结构是相同的，所以可以很方便地一起二分 每次传两个指针，表示当前走到的r位置树的节点a，和当前走到的l-1位置树的节点b 每次二分的时候，判断当前的k和a -> left -> size – b -> left -> size大小即可，和普通的线段树上一起二分类似 总时间复杂度O( (n+m)logn ) 存在O( (n+m)logn/loglogn )的解法 Path Copy 上述的方法即path copy，字面意思就是每次复制被修改的整条路径来实现可持久化 在竞赛中，一般来说path copy的功能是足够的 优点：方便理解，出题人也只会这个 缺点：空间有时候显得很大 Fat Node 我们每个节点开一个vector，如果这个节点被访问到了，则在这个节点的vector中push_back一个二元组信息，表示这个节点在某个时刻被更改为了一个状态 每次我们访问到一个节点的信息时，则在其vector上二分（不一定要这么做，vector可以换成其他数据结构，这里是为了简单理解），找到距离查询的时刻最近的一次修改之后这个节点的信息变成了什么，然后返回结果 Fat Node 可以发现这样修改复杂度O( logn )，如果使用vector，则查询复杂度为O( log^2n )，这个复杂度是难以优化的，目前没有方法优化到O( logn )的复杂度，但是可以做到O( lognloglogn ) 优点：修改高效，空间常数小 缺点：查询低效 Note 还有其他很多可持久化的技术，算法竞赛圈在可持久化这个方面感觉内容很少 HDU - 4757 Tree 给出一颗树，每棵树上有ｎ个结点，每个结点对应一个值，有ｍ组查询操作，查询在从ｘ到ｙ的这条路径上选出一个数与ｚ进行异或的最大值。 值域是n Solution 考虑如何类比前面的区间kth做法 Solution 给定一个集合，如何查询一个数x与集合的最大xor和？ 对集合建立一棵可持久化01Trie（和值域线段树一样） 从高位到低位贪心，如果当前x这一位是0，则尽可能走1，否则尽可能走0 Solution 树上怎么做？ 考虑树上前缀和的方法，从根到叶子建立可持久化0 ... ...
