可持久化数据结构简介
分类
部分可持久化
所有版本都可以访问,但是只有最新版本可以修改。
完全可持久化
所有版本都既可以访问又可以修改。
实际应用
几何计算(扫描线),字串处理(合并操作 rope
),版本回溯,函数式编程。
可持久化线段树
引入[P3834 【模板】可持久化线段树 2]
首先考虑静态全局第 \(k\) 小,可以用权值线段树,在线段树上二分,同时也支持动态全局第 \(k\) 小(单点修改)。
考虑静态区间第 \(k\) 小,对于每个前缀 \(a_{1,2,\dots,n}\) 都建一个权值线段树 \(T_i\),\(T_i\) 中代表区间 \([l,r]\) 的节点存前缀 \(a_{i,2,\dots,n}\) 中有多少个数在 \([l,r]\) 内。
对于 \([l,r]\) 的询问,我们只需将 \(T_r\) 与 \(T_{l-1}\) 两棵树中的对应节点相减,就得到了该区间的权值线段树。
但一共需要 \(O(n^2)\) 个节点,考虑优化。
发现 \(T_i\) 较 \(T_{i-1}\) 只修改了从 \(a_i\) 对应的叶子节点到根节点的路径上的权值,共 \(O(\log n)\) 个节点。
因此,从 \(T_{i-1}\) 到 \(T_i\) 的过程中,我们只需要新建发生变化的 \(O(\log n)\) 个节点,剩下的节点与 \(T_{i-1}\) 共用(即新建根节点,被修改的儿子新建节点,未被修改的儿子仍用 \(T_{i-1}\) 的)。
区间修改同理,同样只有 \(O(\log n)\) 个节点被修改。
标签:持久,log,线段,修改,权值,数据结构,节点 From: https://www.cnblogs.com/CheZiHe929/p/18325966