5
19
2016
0

【新姿势】动态树初探

理解原理后,选择简洁明白的实现方式也是很重要的一环.

十分感谢%%% 陈乐群 的小结,一遍一遍读,发现写得真心不错,要不我还在兜圈子呢.

传送门:https://oi.abcdabcd987.com/summary-of-link-cut-tree/

接下来写一下我自己对模板的理解:

struct splay{
	int fa,l,r,siz;//fa:path_parent
	bool rev;
}t[N];

其实结构体表示的Splay在写旋转模板时不是那么方便..

既然Splay中的根节点还有父亲,为了确定哪个节点是当前Splay的根,我们必须对正常的Splay tree进行修改。大致有两种方法:

1在每个节点记下 Root 标记,以确定当前节点是否为它所在的Splay tree的根。然后旋转的时候通过标记下传修改Root标记。

>优点:方便调试

>缺点:LCT的操作写起来麻烦,而且容易出错

2不记录Root标记,但是修改旋转过程。

>优点:LCT非常好写好理解

>缺点:需要修改splay操作

我个人还是偏向后面那种方法.

 

另外,LCT操作的实现也有两种方法:

1固定根,通过修改过的 Access 操作 (Access2) 进行查询和修改。

2动态根,通过换原树的根和原始的Access进行查询和修改。

很明显第一个由于少了换根,常数肯定要小的多。

但是我觉得第二个理解比较容易,而且比较好写,不容易出错。


void Access(int x)
{
	int y=0;
	while(x){
		Splay(x);
		t[x].r=y;
		y=x;
		x=t[x].fa;
	}
}

处理孩子和处理path父节点的方法是类似的,故代码统一:

 

最初y=0,用来清除x的右子节点,即将边实变虚

 

之后每次找到path父节点,用y所在的平衡树(之前x已经Splay到根,经过赋值,ySplay的根)替换x的右子树。(原先x的右子树似乎不作处理?)

 

直到父节点不存在,即已处理到根。


void MakeRoot(int x)
{
	Access(x);
	Splay(x);
	t[x].rev^=1;
}
Category: 动态树问题 | Tags: Splay LCT 学习笔记 | Read Count: 304

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com