注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

动态树  

2011-02-07 21:38:32|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
动态树是一种“超级数据结构”,它能够维护一个由若干有根树组成的森林,在对数的时间复杂度内支持:
1.查询一个点的父亲
2.查询一个点所在的树的根
3.修改某个节点的权
4.向从某个节点到它所在的树的根的路径上的所有的节点的权增加一个数
5.查询从某个节点到它所在的树的根的路径上的所有的节点的权的最小值
6.把一棵树从某个节点和它的父亲处断开,使其成为两棵树
7.让一棵树的根成为另一棵树的某个节点的儿子,从而合并这两棵树
8.把某棵树的根修改为它的某个节点
9.查询在同一棵树上的两个节点的LCA
*10.修改以某个节点为根的子树的所有节点的权
*11.查询以某个节点为根的子树的所有节点的权的最小值
......
为了简化问题,我们只考虑一个简化版本:不支持10和11操作

百度文库里有关于动态树的论文。其中介绍的比较多的是Link-Cut Tree,它的核心思想是:
把树剖分成若干个链,之后用平衡树去维护维护这些链。
可以选择的平衡树有Splay,或者在树的形态不改变的情况下使用“全局平衡二叉树”(见2007年某人的某论文)。

有了动态树,我们能够做很多事情,例如:

优化网络流(看某些有关费用流的论文吧)

除了这个“正当”用途外,还有各种“不正当用途”:
并查集(不光支持合并,还支持按某种规则分离呢)
LCA(动态的LCA啊)
RMQ(所谓数列就是一个链,所谓链就是一种退化了的树。对每次要操作的区间,先从树上砍下来,操作完之后合并回去)
可并优先队列(所谓队列就是一个链。。。。。。)

如果你不嫌弃常数,如果你有套模板刷题的习惯,那么可以“一切皆动态树”。

代码真的不算很长,也就190行,3.9K(不算很长。。。)
http://cid-354ed8646264d3c4.office.live.com/self.aspx/.Public/DynamicTree.cpp
  评论这张
 
阅读(7913)| 评论(10)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017