华师一附中OI组

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 984|回复: 0
打印 上一主题 下一主题

可持久化线段树

[复制链接]

738

主题

1485

帖子

5422

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5422
跳转到指定楼层
楼主
发表于 2020-2-20 10:40:47 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
可持久化线段树
个人认为大部分数据结构转变为可持久化都是比较简单的,只需要保存历史版本的信息即可。在每次进行更改操作时,先复制的到之前的一个版本,然后对要进行更改的节点,复制一个出来改。并且将它的父亲指向新复制出来的点。

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

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

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


回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|服务支持:DZ动力|华师一附中OI组  

GMT+8, 2024-12-26 01:41 , Processed in 0.218485 second(s), 23 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表