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

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

动态树:实现  

2011-06-18 23:51:22|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
我最近看到zjoi2011的一道题:
之后一惊:这不是传说中的动态树吗,怎么都出到省选里了?
我又看到了某神牛的博文:
“不过我权衡了一下,觉得树链剖分我几乎写过10多次了。。应该还是写的出来的。。”
我被震撼了:真是人在北京好似坐井观天,人家都写了10遍的东西我竟然还认为OI中不会考呢!
于是,我痛下决心:疯狂练习,攻克动态树。
动态树除了上面的那题外,还有
也是zjoi的题。
以及spoj上的QTREE。
我决定就把这三道题刷了好了。

动态树的实现主要有5种:
link-cut tree *
Euler-Tour tree
全局平衡二叉树 *
树链剖分
树块剖分 *
我们重点关注带星号的实现

link-cut tree的思想是把树剖分成若干个链,不过这些链是用splay动态维护的,每次查询的时候把一个点到根的路径连成一个链。几篇入门文章可以到这里下载:
http://cid-354ed8646264d3c4.office.live.com/self.aspx/.Public/DynamicTree/QTREE^_YangZhe.pdf
http://cid-354ed8646264d3c4.office.live.com/view.aspx/.Public/DynamicTree/CollectionOfAlgorithms^_DynamicTree.doc
一些实现上的技巧可以参考杨哲的文章,我综合以上两篇文章得出了我自己的写法:
http://cid-354ed8646264d3c4.office.live.com/self.aspx/.Public/DynamicTree/2325^_2.cpp
总体来说,是融合了朴素与飘逸。程序100多行,4K,还行。最核心的连接操作非常经典:
node *Expose(node *p){
node *q;
for (q=NULL;p;p=p->f){
Splay(p);
p->r=q;
(q=p)->update();
}
return q;
}
Splay操作则是唐文斌教给我的写法(融合了杨哲的改进):
void Splay(node *p){
while (p->f && (p->f->l==p || p->f->r==p)){
node *q=p->f,*y=q->f;
if (y && y->l==q){
if (q->l==p)zig(q),zig(p);
else zag(p),zig(p);
}else if (y && y->r==q){
if (q->r==p)zag(q),zag(p);
else zig(p),zag(p);
}else{
if (q->l==p)zig(p);
else zag(p);
}
}
p->update();
}
这些代码其实非常优雅、流畅,默写一遍20分钟足矣,我写到第2遍的时候就已经不用调试直接正确了。
SPOJ上QTREE那题用这个模板AC没有阻碍:
http://cid-354ed8646264d3c4.office.live.com/self.aspx/.Public/DynamicTree/375.cpp
可以说,以后考试的时候遇到动态树我就写Link-Cut Tree了。

Link-Cut Tree的常数其实很糟糕,这主要是splay导致的。
改进常数的方法是建立一棵”全局平衡二叉树“,也是树链剖分,不过把整个树看做一体,修改每个链选择根节点的规则,使得任何一个节点的深度不超过2logN。具体见杨哲的文章。
我很纠结地写出来了代码。
http://cid-354ed8646264d3c4.office.live.com/self.aspx/.Public/DynamicTree/2325^_3.cpp
说它纠结,其实倒不是建树的过程有多麻烦,相反,非常容易。恶心的是查询的写法。
我写的第一个版本跑得比link-cut tree还慢。经过参考各种代码之后,我终于找到了正确、高效的写法:
int Ask(int x,int y){
rec left=rec::empty(),right=rec::empty();
while (head[x]!=head[y]){
if (depth[head[x]]>depth[head[y]]){
for (int b=rc[x],i=x;i!=-1;i=tf[i]){
if (b==rc[i]){
left=left+R[i];
if (lc[i]!=-1)left=left+S[lc[i]];
}
b=i;
}
x=fa[head[x]];
}else{
for (int b=rc[y],i=y;i!=-1;i=tf[i]){
if (b==rc[i]){
right=right+R[i];
if (lc[i]!=-1)right=right+S[lc[i]];
}
b=i;
}
y=fa[head[y]];
}
}
int bx,by,flg=depth[x]<depth[y];
if (flg)bx=lc[x],by=rc[y];
else bx=rc[x],by=lc[y];
while (x!=y){
if (dep2[x]>dep2[y]){
if (flg && bx==lc[x]){
left=left+R[x];
if (rc[x]!=-1)left=left+S[rc[x]].reverse();
}else if (!flg && bx==rc[x]){
left=left+R[x];
if (lc[x]!=-1)left=left+S[lc[x]];
}
bx=x;
x=tf[x];
}else{
if (flg && by==rc[y]){
right=right+R[y];
if (lc[y]!=-1)right=right+S[lc[y]];
}else if (!flg && by==lc[y]){
right=right+R[y];
if (rc[y]!=-1)right=right+S[rc[y]].reverse();
}
by=y;
y=tf[y];
}
}
rec ret=left+R[x]+right.reverse();
return max(ret.b[0][0],ret.b[0][1]);
}
50多行,占代码中动态树部分的一半。
这里有特别多的细节,必须把所有东西都想明白才能AC。
效果是让人欣慰的:zjoi2011道馆之战那题
4 121844(5) fanhqme 5648 KB 1910 MS C++ 4821 B 2011-06-18 22:29:08
排名刷到了第4,非常有成就感。
我造了一组数据,通过gprof的统计,全局平衡二叉树的实现调用合并统计信息的函数的次数比link-cut tree的实现少60%
 67.24      0.39     0.39  1601129     0.00     0.00  rec::operator+(rec const&) const
 78.43      0.80     0.80  4291053     0.00     0.00  rec::operator+(rec const&) const
这就是为什么它的常数小;实际上,程序运行的大部分时间都花费在计算统计信息的和上了。

不过,正如唐文斌曾经问过的一个经典问题,”这东西你写过不重要,重要的是你还想写第2遍吗?”
我斩钉截铁地回答:不!

那么,动态树的高性价比的实现是什么呢?
树块剖分!
http://cid-354ed8646264d3c4.office.live.com/self.aspx/.Public/DynamicTree/2325^_1.cpp
动态树的部分就50多行(差不多跟GBT(Global  Balanced Tree)的Ask部分一样长),可以先写朴素形式,之后改动20行变成树块剖分形式。
树块剖分的思想是什么呢?
我们依然把树剖分,不过,这回我们是把树剖分成若干个联通块。每个联通块里,我们维护每个点到整个联通块的根(连通块中深度最小的点)的信息和。
统计两个点之间的路径的信息的时候,我们把这个路径拆分到各个树块中,这样,除了这两个点的LCA所在的树块以外,其他的树块中的路径都是已经计算好的,直接累加即可。而LCA所在的树块中的信息可以暴力统计。
把树块的大小设定为sqrt(N),那么算法的时间复杂度就是sqrt(N)。虽然比logN大很多,不过,实际效果非常好:
下面是我造的一组道馆之战的数据的gprof的结果,可以看出,它的常数比link-cut tree仅仅大一点。
73.91      0.85     0.85  4408485     0.00     0.00  rec::operator+(rec const&) const(树块剖分)
78.43      0.80     0.80  4291053     0.00     0.00  rec::operator+(rec const&) const(link-cut tree)
67.24      0.39     0.39  1601129     0.00     0.00  rec::operator+(rec const&) const(GBT)
实践中效果也很好,zjoi的两个题AC毫无压力,甚至跑的比一些写的不是很好的link-cut tree还快。

有一个问题:如何让每个联通块的大小都是sqrt(N)呢?
当然,这是一个不可能的任务。
不过,我们可以把要求降低一点:
每个点到根的路径上的树块数为O(sqrt(N)),每个树块大小<=sqrt(N)。
这样,就有了一个简单的思路:尝试合并dfs入栈序相邻的两个节点,直到块的大小满了。这个可以用另一种语言来描述:
def dfs(a,color):
  a.belong=color
  color.size+=1
  for i in a.childs:
    if color.size<L:
        dfs(i,color)
    else:
        dfs(i,i)
嗯,这个python程序表达的就是那个意思吧(换一种语言。。。)。
为什么这么做是对的呢?一句话证明:路径上相邻两个树块的大小的和肯定超过L。

划分完联通块之后,更新和查询都很好写。更新就是从这个节点往下dfs,修改同一个树块内的统计信息。查询就是两个节点比赛往上爬,直到找到LCA。
O(sqrt(N))是一个理论上的复杂度,实际中,比较弱的数据(例如随机数据)上根本到不了这个复杂度。所以,AC起来就非常愉快。
如何卡掉树块剖分呢?好像菊花形数据应该可以(一条链+一个星)让它达到理论复杂度

动态树除了维护形态静止的树上的信息外,还要处理动态的问题。
例如:
把一个子树砍下来
把另一棵树接上去
改变一个树的根

link-cut tree生下来就是为了处理这些问题的,通过强大的splay可以很容易来处理树的形态改变的问题。
那么其他的呢?
GBT可以见阎王了。当然,也可以有一些补救办法,例如修改的时候忽略2logN的约束,当树的形态太不像样了就重新建一遍(类似暴力懒惰删除)
树块剖分呢?
其实是可以在一定程度上动态起来的。
我们用如下的方法来维护树块:
对每次要访问的节点x,沿x走到根,把路径上相邻两个能合并的树块合并。
这样,理论复杂度不变,均摊下来都是O(sqrt(N))。(N是整个森林的节点数)
这么做得好处是,我们可以在树的形态改变的时候比较“奔放”地处理树块,在查询的时候再让它们规整起来就行了。
砍树和接树都能快速完成,唯独修改根不行。

总结一下吧。
目前的动态树问题都是静态的树,动态的信息。
追求代码短可以使用树块剖分,简洁高效易调错。
追求稳定可以用link-cut tree,复杂度有保证。
如果你的时间真的很充裕,如果你真的很牛,可以写GBT,效率高,常数小,时间复杂度低。

未来的发展方向呢?
1.重量级统计信息(例如6*N最短路之类的)
2.动态的形态(例题:动态最小生成树,正在研发中。。。)
3.和dp优化、网络流、图论等结合(例题:无向图动态连通性,正在找思路中。。。)

  评论这张
 
阅读(14529)| 评论(34)
推荐 转载

历史上的今天

评论

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

页脚

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