华师一附中OI组

标题: 可持久化线段树 [打印本页]

作者: admin 时间: 2020-2-20 10:40
标题: 可持久化线段树
可持久化线段树
个人认为大部分数据结构转变为可持久化都是比较简单的，只需要保存历史版本的信息即可。在每次进行更改操作时，先复制的到之前的一个版本，然后对要进行更改的节点，复制一个出来改。并且将它的父亲指向新复制出来的点。

也就是说，我们只是在原来的历史版本上加边加点，并没有重新建一个树。

除此之外我觉得还可以有一个大胆的搞法。历史版本我们可以不用线性的结构保存，我们可以用树状数组来快速实现。这个玩意是可以实现的，但是，实现起来非常恶心。即使如此，我觉得还是有必要的写一写的。

代码是CQBZ-2111（区间查询不带修改操作）
区间查询操作就是有历史版本提供基础的。对于区间[l,r]我们只需要询问第r个和第l-1个历史版本就可以。

欢迎光临华师一附中OI组 (http://hsyit.cn/)