FHQ版LCT教程

LCT but FHQ：

邪教 ——FHQ & LCT

小言：

每條重鏈單獨使用一個平衡樹進行維護。
LCT：實鏈剖分與平衡樹維護動態樹的信息，并且同時維護多個動態樹，所以全局是森林。
每個節點認定一個實兒子，然后把這條邊看成實邊，其他為虛邊，然后忽視虛邊，維護一堆鏈，如果需要別的操作，虛實邊可以隨時轉換。
通過一個個連邊建樹來建圖，開始連的都是虛邊，在以后通過 \(\operatorname{access}\) 函數轉實邊，時間復雜度看似很大，實際不錯。

概念：

原樹：原來的多叉樹，方便觀察原樹形態。
輔助樹：把一整個平衡樹看成一個整塊，用虛邊連起來這些整塊，方便觀察各個平衡樹形態。一坨實鏈里是平衡樹（二叉），然后虛邊連了好幾坨（多叉）

為了方便，我把下面的單個平衡樹（一坨實鏈）全說成輔助樹了。

結合代碼講解：

其實 LCT 就像個暴力算法，大膽去寫，下面未解釋區域是因為自己推導并不難。

注意：
\(\operatorname{link(x,y)}\) 和 \(\operatorname{cut}(x,y)\) 如果不保證合法，就都要判合法。

……—— FHQ 定義

bool fx[300030];
struct treap {int l,r,fa,sui,xu,v,x;bool lan;} t[300030];
struct node {int x,y;};

\(\operatorname{pushdown}\) —— FHQ 下傳懶標記

懶標記之翻轉：用于 \(\operatorname{access}\)，是必寫的，同時也是為什么只能用 FHQ 和 splay 的原因。

void pushdown(int o)
{
	if(t[o].lan) swap(t[o].l,t[o].r),t[t[o].l].lan^=1,t[t[o].r].lan^=1,t[o].lan=0;
}

\(\operatorname{updata}\) —— FHQ 更新

這里的異或是題目要求異或和。

inline void updata(int o)
{
	t[o].x=t[o].v^t[t[o].l].x^t[t[o].r].x;
	if(t[o].l) t[t[o].l].fa=o;
	if(t[o].r) t[t[o].r].fa=o;
}

\(\operatorname{hebing}\) —— FHQ 合并

int hebing(int x,int y)
{
	if(!x||!y) return x+y;
	if(t[x].sui<t[y].sui) return pushdown(x),t[x].r=hebing(t[x].r,y),updata(x),x;
	else return pushdown(y),t[y].l=hebing(x,t[y].l),updata(y),y;
}

\(\operatorname{isroot}\) —— 是否是輔助樹樹根

bool isroot(int o) {return (t[t[o].fa].l!=o&&t[t[o].fa].r!=o)||!t[o].fa;}}

\(\operatorname{findroot}\) —— 找輔助樹的根

這里的 fx 數組同時記錄分裂時的方向，因為要按 o 的位置分裂，所以用分裂要先用這個函數。

int findroot(int o)
{
	top=0;
	while(!isroot(o)) fx[++top]=(t[t[o].fa].l==o),o=t[o].fa;
	return o;
}

\(\operatorname{findleft}\) —— 找當前輔助樹中中序最小的

本質上是找輔助樹在原樹上深度最小的節點。

int findleft(int o)
{
	o=findroot(o),pushdown(o);
	while(t[o].l) o=t[o].l,pushdown(o);
	return o;
}

另一種寫法直接省略此函數，直接用輔助樹的根的 fa 數組為原樹深度最小的節點的父親（fa 數組是 FHQ 的），如果按此方法寫，可以用 \(\operatorname{findroot}\) + fa 數組解決。

復雜度是一樣的，因為 \(\operatorname{findroot}\) 和 \(\operatorname{findleft}\) 復雜度一樣。

但是 FHQ 貌似只能用 \(\operatorname{findleft()}\)，splay 一般維護 fa 數組。

\(\operatorname{split}\) —— 改的 FHQ 分裂

在當前輔助樹中把位置 \(\le o\) 的分裂為左，余為右。

關于如何找 \(o\) 的位置，我們在分裂前必須用 \(\operatorname{findroot}\) 來記錄數組。

void split(int o,int &l,int &r)
{
	if(!top) return pushdown(o),l=o,r=t[o].r,t[o].r=0,updata(o),void();
	bool d=fx[top--];
	d^=t[o].lan,pushdown(o);
	if(d) r=o,split(t[o].l,l,t[o].l);
	else l=o,split(t[o].r,t[o].r,r);
	updata(o);
}

\(\operatorname{access}\) —— 把當前節點到根全部改為實鏈

int access(int o)
{
	int last=0;
	while(o)
	{
		int shang,xia;
		split(findroot(o),shang,xia);
		t[findleft(last)].xu=0;
		last=hebing(shang,last);
		t[findleft(xia)].xu=o;
		o=t[findleft(last)].xu;
	}
	return last;
}

\(\operatorname{root}\) —— 找當前節點所在原樹的根

int root(int o) {return findleft(access(o));}

\(\operatorname{changroot}\) —— 把當前節點改為原樹的根

void changeroot(int o) {t[access(o)].lan^=1;}

\(\operatorname{link}\) —— 連 x 到 y 的邊

void link(int x,int y) {changeroot(x),t[x].xu=y;}

\(\operatorname{cut}\) —— 切斷 x 到 y 的邊

void cut(int x,int y) {changeroot(x),access(y),access(x),t[y].xu=0;}

\(\operatorname{query}\) —— 查詢

這個代碼是查詢 x 到 y 的路徑上的 xor 和：

int query(int x,int y) {return changeroot(x),access(y),t[findroot(y)].x;}

\(\operatorname{change}\) —— 修改

這個代碼是將點 x 上的權值變成 y。

void change(int o,int v)
{
	int o1,o2;
	changeroot(o);
	split(findroot(o),o1,o2);
	t[o].v=v,hebing(o1,o2);
}

\(\operatorname{solve}\)

cin>>n>>m;
for(int i=1;i<=n;++i) cin>>t[i].v,t[i].x=t[i].v,t[i].sui=rand();
for(int i=1,op,x,y;i<=m;i++)
{
  cin>>op>>x>>y;
  if(op==0) cout<<query(x,y)<<'\n';
  else if(op==1&&root(x)!=root(y)) link(x,y);
  else if(op==2) cut(x,y);
  else if(op==3) change(x,y);
}

優秀的時間復雜度

splay 時間復雜度 \(O(n \log n)\)，常數 \(≈11.4514\)。
由于實現只要能維護翻轉操作就行，所以可以選擇 FHQ，FHQ 常數更小了，但是時間復雜度是 \(O(n \log ^2n)\)，寫個快讀表現就和 splay 差不多了。

關于 splay LCT 時間復雜度的嚴謹證明。
參照這個，我們發現訪問虛邊的勢能分析沒影響，但是 FHQ 無法均攤平衡樹復雜度，所以時間復雜度要把 FHQ 的 \(O( \log n)\) 和跳鏈的 \(O( \log n)\)，最后證明是 \(O(n \log ^2n)\)。

LCT 應用：

1. 動態樹問題。

無需多言。

2. 大部分樹鏈剖分操作。

好處：

在維護鏈用 splay 理論復雜度甚至更快，但是常數很大！樹剖非理論復雜度很快。
比樹剖套數據結構的代碼短。

壞處：

維護子樹難
最好學的 LCT 動態樹無法修改子樹！令人傷心。
至于怎么路徑改子樹查……
蒟蒻我寫 FHQ 維護寫掛了，沒調出來，思路大概是每個點用 set 維護虛子樹信息，然后查詢把所有兒子都變成虛兒子后查自己和 set 的信息并。
我知道我的說法并不好，建議大家另找別的博客學習維護子樹，抱歉。

3. 支持刪除邊的并查集（需保證無環）。

找根操作。

4. 可在線維護邊權。（最小生成樹之類）。

看題理解吧。

5. 在線加邊維護邊雙聯通分量。

在 \(\operatorname{link}\) 的時候，如果發現 \(x\) 和 \(y\) 在一個樹里，有環，那肯定要開始縮了，鎖點的時候，把這個環上的所有點全部鎖到這個輔助樹的根節點，因為可以把根節點的 \(fa\) 設為原樹父親，比較特殊，所以縮這里。

根節點為標志節點，用并查集代表當前節點被鎖到哪去了，然后把當前環上的點提出來一個輔助樹，然后遞歸這個輔助樹更新并查集為標志節點，最后斷開標志節點與子樹的連接，同時在需要訪問原樹的父親節點的時候，需要套用并查集，因為這個點的父親可能已經被縮了。

函數遞歸縮點：

void del(int x,int y) {if(x) bcj[x]=y,del(lc,y),del(rc,y);}

找爸爸：

\(fa(x)←find(fa_x)\)

6. 維護樹上染色聯通塊。