526互联

「Note」数据结构方向 - 数据结构进阶

发布时间 2023-08-22 08:18:50作者: Eon_Sky

1. 平衡树

咕咕咕

2. 树套树

咕咕咕

3. LCT

3.1. 介绍

3.1.1. 基本概念

LCT 全名 Link-Cut-Tree，动态树，是用来维护动态森林的数据结构。
它支持以下操作（需要保证任意操作时刻维护的都为森林）：

  • 连边。
  • 断边。
  • 换根。
  • 提取路径信息。

LCT 的大体思路是将每棵树拆分为若干条链，并用平衡树维护链中节点，维护关键字为节点深度，每一条链的状态都是动态的。

由于 LCT 结构的特殊性，一般我们用 Splay 维护链，更加抽象的，我们实际上并不直接利用类似 \(\mathrm{build}\) 的东西将树划分成若干链，我们在需要的时候动态维护我们需要的链，这基于了 Splay 方便的各种操作。

在维护的时候，对于每一个节点，我们选出至多一个儿子作为实儿子，令节点到实儿子的边为实边，剩余边为虚边。实边组成的链成为实链，因为实链是我们所选择的，所以 LCT 的才是灵活多变的，请牢记我们的实链是不断变化去维护信息的。

3.1.2. 辅助树

我们用 Splay 以节点深度为关键字维护每条实链上的点，虚边连接了一棵棵 Splay，每个 Splay 的根节点都有一条虚边指向其维护原链顶的父节点。以这样的方式连接，一棵树上的多个 Splay 就组成了一棵辅助树，多棵辅助树就构成了我们的 LCT。

一颗辅助树有如下性质：

  • 中序遍历每棵 Splay 得到的点序列，对应其维护链从上至下的一条路径。
  • 辅助树节点与原树节点一一对应。
  • 每棵 Splay 根节点父节点并不为空，其用虚边指向了此 Splay 维护原链的父节点。需要注意的，根节点并不是其父节点的子节点（认父不认子）。

由于辅助树的以上性质，我们任何操作都不需要维护原树，辅助树可以在任何情况下提取出一棵原树。

需要注意的：

  • 原树的根不等于辅助树的根，原树的父节点指向不等于辅助树的父节点指向。
  • 虚实链是可以在辅助树上进行变换，实现了动态的树链剖分，这也是前文说到的“实链是不断变化去维护信息的”。

至于为什么在操作过程中需要翻转 Splay，目的是保证复杂度，具体证明大概是论文级的，这里不会提及，只需要记住即可。

3.1.3 实现过程

以洛谷模板题为例，进行实现过程的讲解。
维护一个结构体表示一个节点，其中含有以下信息：

\(fa\) \(son_{1/0}\) \(val\) \(sum\) \(siz\) \(lazy\)
父节点 子节点 此节点权值 此节点在 Splay 中的子树异或和 此节点在 Splay 中的子树大小 翻转标记

介绍 LCT 的核心函数之前先给出两个 Splay 的函数（\(t\) 是我们的节点结构体数组）。

void rotate(int rt)
{
	int fa=t[rt].fa,gfa=t[fa].fa,gs=get(rt),gfs=get(fa);
	bool flag=che_rt(fa);
	t[fa].son[gs]=t[rt].son[!gs],t[t[rt].son[!gs]].fa=fa;
	t[rt].son[!gs]=fa,t[fa].fa=rt,t[rt].fa=gfa;
	if(!flag)
		t[gfa].son[gfs]=rt;
	push_up(fa),push_up(rt);
	return;
}
void splay(int rt)
{
	push_down_(rt);
	for(int now=t[rt].fa;!che_rt(rt);rotate(rt))
		if(!che_rt(now=t[rt].fa))
			rotate((get(now)==get(rt))?now:rt);
	return;
}

rotate（） 函数进行单旋操作，splay() 函数将节点旋至其所在 Splay 的根节点。与正常 Splay 不同的是，我们需要判断一个节点是否为其所在 Splay 的根（che_rt() 函数的作用），同时也请注意翻转标记的下传。

接下来我们介绍 LCT 的核心操作。

void access(int rt)
{
	for(int lst=0;rt;lst=rt,rt=t[rt].fa)
	{
		splay(rt);
		t[rt].son[1]=lst;
		push_up(rt);
	}
	return;
}

此函数作用是把某节点到当前辅助树的根路径上的点合并为一棵新的 Splay，具体过程如下：

  • 现将当前节点旋至其所在 Splay 的根。
  • 将上一节点接到当前节点上（这样直接实现了新链的合并与原来 Splay 边的断开）。
  • 更新当前节点信息。
  • 跳转到父亲，重复操作直到跳至根。

我们的剩余函数都以 access() 函数为基础进行操作，接下来介绍其他的函数。

  • tag() 用于对节点打上旋转标记。
void tag(int rt)
{
	swap(t[rt].son[0],t[rt].son[1]);
	t[rt].lazy^=1;
	return;
}
  • che_rt() 用于检查节点是否为 Splay 的根。
bool che_rt(int rt)
{
	return (t[t[rt].fa].son[0]!=rt&&t[t[rt].fa].son[1]!=rt);
}
  • get() 用于找到当前节点是其父节点的哪个儿子。
int get(int rt)
{
	return ((t[t[rt].fa].son[1]==rt)?1:0);
}
  • push_up() 更新当前节点信息。
void push_up(int rt)
{
	t[rt].siz=t[t[rt].son[0]].siz+t[t[rt].son[1]].siz+1;
	t[rt].sum=t[t[rt].son[0]].sum^t[t[rt].son[1]].sum^t[rt].val;
	return;
}
  • push_down() 下传标记。
void push_down(int rt)
{
	if(t[rt].lazy!=0)
	{
		tag(t[rt].son[0]);
		tag(t[rt].son[1]);
		t[rt].lazy=0;
	}
	return;
}
  • push_down_() 下传当前节点至 Splay 根节点的标记（从上至下）。
void push_down_(int rt)
{
	if(!che_rt(rt))
		push_down_(t[rt].fa);
	push_down(rt);
}
  • make_rt() 使当前节点变为辅助树的根。
void make_rt(int rt)
{
	access(rt);
	splay(rt);
	tag(rt);
	return;
}
  • find_rt() 查询当前节点所在辅助树的根（请考虑 splay() 的过程，不难得出结论）。
int find_rt(int rt)
{
	access(rt);
	splay(rt);
	while(t[rt].son[0])
	{
		push_down(rt);
		rt=t[rt].son[0];
	}
	splay(rt);
	return rt;
}
  • check() 查询两节点是否连通。
bool check(int x,int y)
{
	make_rt(x);
	return (find_rt(y)==x);
}
  • link() 连边（先判连通）。
bool link(int x,int y)
{
	make_rt(x);
	return (find_rt(y)==x);
}
  • cut() 断边（判相连，仍然考虑实现过程即可理解）。
void cut(int x,int y)
{
	if(check(x,y)&&t[x].siz<=2)
		t[y].fa=t[x].son[1]=0;
}
  • split() 分离一条链，正是前文提到的“提取路径信息”。
int split(int x,int y)
{
	make_rt(x);
	access(y);
	splay(y);
	return y;
}
  • change() 单点修改（并不是所有的题都有）。
void change(int rt,int val)
{
	splay(rt);
	t[rt].val=val;
	push_up(rt);
	return;
}

对于模板题的构建至此结束，LCT 的拓展性较强，具体题目还需具体分析。

3.2. 常用技巧

3.2.1 基础技巧

对于维护操作应多考虑优化，可以复杂化 push_up() 函数，但要注意代码结构的简洁性，并尽可能减少代码量与数据结构的操作难度，即使可能是复杂度变为少劣（在无风险前提下）。

3.2.？咕咕咕

咕咕咕

3.2. 题目

\(\color{blueviolet}{P3690\ 【模板】动态树（LCT）}\)

板子。
\(\text{Code:}\)

#include<bits/stdc++.h>
#define LL long long
#define UN unsigned
using namespace std;
//--------------------//
const int N=1e5+5;

struct LCT
{
	struct Tree_Node
	{
		int fa,son[2];
		int val,sum,siz;
		int lazy;
	}t[N];
	void tag(int rt)
	{
		swap(t[rt].son[0],t[rt].son[1]);
		t[rt].lazy^=1;
		return;
	}
	bool che_rt(int rt)
	{
		return (t[t[rt].fa].son[0]!=rt&&t[t[rt].fa].son[1]!=rt);
	}
	int get(int rt)
	{
		return ((t[t[rt].fa].son[1]==rt)?1:0);
	}
	void push_up(int rt)
	{
		t[rt].siz=t[t[rt].son[0]].siz+t[t[rt].son[1]].siz+1;
		t[rt].sum=t[t[rt].son[0]].sum^t[t[rt].son[1]].sum^t[rt].val;
		return;
	}
	void push_down(int rt)
	{
		if(t[rt].lazy!=0)
		{
			tag(t[rt].son[0]);
			tag(t[rt].son[1]);
			t[rt].lazy=0;
		}
		return;
	}
	void push_down_(int rt)
	{
		if(!che_rt(rt))
			push_down_(t[rt].fa);
		push_down(rt);
	}
	void rotate(int rt)
	{
		int fa=t[rt].fa,gfa=t[fa].fa;
		int gs=get(rt),gfs=get(fa);
		bool flag=che_rt(fa);
		t[fa].son[gs]=t[rt].son[!gs];
		t[t[rt].son[!gs]].fa=fa;

		t[rt].son[!gs]=fa;
		t[fa].fa=rt;
		t[rt].fa=gfa;
		if(!flag)
			t[gfa].son[gfs]=rt;
		push_up(fa),push_up(rt);
		return;
	}
	void splay(int rt)
	{
		push_down_(rt);
		for(int now=t[rt].fa;!che_rt(rt);rotate(rt))
			if(!che_rt(now=t[rt].fa))
				rotate((get(now)==get(rt))?now:rt);
		return;
	}
	void access(int rt)
	{
		for(int lst=0;rt;lst=rt,rt=t[rt].fa)
		{
			splay(rt);
			t[rt].son[1]=lst;
			push_up(rt);
		}
		return;
	}
	void make_rt(int rt)
	{
		access(rt);
		splay(rt);
		tag(rt);
		return;
	}
	int find_rt(int rt)
	{
		access(rt);
		splay(rt);
		while(t[rt].son[0])
		{
			push_down(rt);
			rt=t[rt].son[0];
		}
		splay(rt);
		return rt;
	}
	bool check(int x,int y)
	{
		make_rt(x);
		return (find_rt(y)==x);
	}
	void link(int x,int y)
	{
		if(!check(x,y))
			t[x].fa=y;
	}
	void cut(int x,int y)
	{
		if(check(x,y)&&t[x].siz<=2)
			t[y].fa=t[x].son[1]=0;
	}
	int split(int x,int y)
	{	
		make_rt(x);
		access(y);
		splay(y);
		return y;
	}
	void change(int rt,int val)
	{
		splay(rt);
		t[rt].val=val;
		push_up(rt);
		return;
	}
}L;
//--------------------//
int n,m;
//--------------------//
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&L.t[i].val);//L.t[i].sum=L.t[i].val;
	for(int op,x,y,i=1;i<=m;i++)
	{
		scanf("%d%d%d",&op,&x,&y);
		if(op==0)
			printf("%d\n",L.t[L.split(x,y)].sum);
		else if(op==1)
			L.link(x,y);
		else if(op==2)
			L.cut(x,y);
		else 
			L.change(x,y);
	}
    return 0;
}