可持续化数据结构 课件-2021-2022学年中学生信息学奥林匹克竞赛数据结构（难点）精讲

可持久化数据结构 信息学奥林匹克竞赛知识点（难点）精讲——数据结构【尖端】 可持久化的定义 我们对于一个数据结构，想维护其所有的历史版本 部分可持久化：允许访问历史版本，不能修改历史版本 完全可持久化：允许把目前版本替换为历史版本 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，字面意思就是每次