加载中…
正文 字体大小:

可持久化线段树学习总结

(2013-08-13 01:29:09)
标签:

数据结构

线段树

分类: 算法学习

于是大概是参考CLJ的《可持久化数据结构研究》学习了可持久化线段树..其它的可持久化数据结构暂时不考虑..

单纯的可持久化线段树主要适用于一类只包含查询而不包含修改的(广义)区间查询问题,这类问题至少满足下面的第二项条件:1、整体查询可利用(离散化后的)权值线段树解决,部分区间却无法解决;2、每一个元素的状态可表示为某个前趋元素的修改版本,修改通常是极少的——具体来说,在线段树中只会修改常数条链。

如果条件1、2都具备,我们通常可以建立具有前缀和性质的可持久化线段树解决。所谓前缀和性质,指的是对每个元素i建立线段树T(i)后,T(i)包含了1-i的信息,而这个信息是可减的。我们可以利用树的减法将部分区间变为整个区间。具体来说,对于线性表上的查询[l,r],常用的模式是Query(T(l)-T(r-1));对于树上路径的查询,由于每个节点都有惟一的前趋节点,我们可以把路径视作一种广义的区间,查询[l,r]时,设p=lca(l,r),常用的查询模式是Query(T(l)+T(r)-T(p)-T(par[p]))(对点)或Query(T(l)+T(r)-2T(p))(对边)。

如果只具备条件2,我们常常不利用前缀和性质(也常常无法利用),而是将区间问题转化为点问题,单独查询某个点上的线段树,并在特定的一棵线段树上获取区间信息。这时,可能需要二分答案。这一类问题的典型例子是BZOJ2653。

上述一类问题的解决过程中,在建树时通常需要利用上一节点的已有版本。

如果题目还要求修改操作,单纯的可持久化线段树通常不能完成。这时,对于满足上述1、2条件的问题,我们会发现,修改一个版本的线段树会对后续版本造成影响——这与修改前缀和数组中某个值会对后继值造成影响是类似的。因此,我们可以考虑使用树状数组维护前缀和。如果是树上的问题,我们可以建立DFS序的树状数组来维护前缀和。这样,节点不存在明确的前趋,建树时也就不再需要利用上一节点的已有版本了。

只满足上述条件2且需要修改的题目我还在思考中,不知道有没有这一类的题目(如带修改的bzoj2653)。此外,我还在考虑可持久化线段树更复杂的应用(如区间运算?),因此这个总结未来也许会更新。


0

阅读 评论 收藏 转载 喜欢 打印举报
已投稿到:
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 不良信息反馈 电话:4006900000 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有