[模板] 动态树/LCT

时间：2021-11-24 13:11:36

简介

LCT是一种数据结构, 可以维护树的动态加边, 删边, 维护链上信息(满足结合律), 单次操作时间复杂度 \(O(\log n)\).(不会证)

思想类似树链剖分, 因为splay可以换根, 用splay维护重链, splay的中序遍历即为链按深度从小到大遍历的结果.

操作

注意区分splay和整棵树的区别, splay根和树根的区别.

\(Access(p)\) 操作指的是将p与根放在同一棵splay中.

\(MakeRoot(p)\) 操作指的是将p变为它所在树(而不是splay)的根. 由于维护的是链上信息, 这不会对答案产生影响.

\(FindRoot(p)\) 操作指的是求p所在树(而不是splay)的根.

\(Link(x,y)\) 操作指的是如果p与q不在同一棵树中, 那么连边 \((x,y)\).

\(Cut(x,y)\) 操作指的是如果p与q有边相连, 那么连边 \((x,y)\).

其中, 'p与q有边相连' 等价于同时满足:

- p,q在同一棵树中.

- p,q深度相差1.(splay中p,q中序遍历时相邻)

\(Split(x,y)\) 操作指的是取出 \((x,y)\) 这个链, 并放在一棵splay中.

具体实现见代码.

应用

  • 动态树(代替树链剖分)
  • 动态最小生成树
  • 维护子树信息(AAA树)
  • 维护并查集(e.g. 可持久化并查集)
  • 优化dinic(据tarjan论文)(怕不是会写死)

Code

const int nsz=3e5+50;

int n,val[nsz];

struct tlct{

	struct tnd{int ch[2],fa,sum,rv;}tree[nsz];

#define ls(p) tree[p].ch[0]

#define rs(p) tree[p].ch[1]

#define fa(p) tree[p].fa

#define dir(p) (rs(fa(p))==p)

	bool isrt(int p){return ls(fa(p))!=p&&rs(fa(p))!=p;}//splay rt

	void rev(int p){swap(ls(p),rs(p));tree[p].rv^=1;}

	void pu(int p){

		tree[p].sum=tree[ls(p)].sum^val[p]^tree[rs(p)].sum;

	}

	void pd(int p){

		if(tree[p].rv==0)return;

		if(ls(p))rev(ls(p));

		if(rs(p))rev(rs(p));

		tree[p].rv=0;

	}

	void pdt(int p){//push down whole splay; from top to bottom

		if(!isrt(p))pdt(fa(p));

		pd(p);

	}

	void rotate(int p){//fa(p) should exist

		int x=fa(p),y=fa(x),dir1=dir(p),dir2=dir(x),z=tree[p].ch[dir1^1];

		if(!isrt(x))tree[y].ch[dir2]=p;fa(p)=y;

		tree[p].ch[dir1^1]=x;fa(x)=p;

		tree[x].ch[dir1]=z;if(z)fa(z)=x;

		pu(x),pu(p);//can't swap

	}

	void splay(int p){

		pdt(p);

		while(!isrt(p)){

			if(!isrt(fa(p)))rotate(dir(p)==dir(fa(p))?fa(p):p);

			rotate(p);

		}

	}

	void access(int p){

		for(int y=0;p;y=p,p=fa(p)){

			splay(p),rs(p)=y;

			pu(p);

		}

	}

	void makert(int p){//p -> tree rt & splay rt

		access(p),splay(p);

		rev(p);

	}

	int findrt(int p){//find tree rt; p -> splay rt

		access(p),splay(p);

		while(ls(p))pd(p),p=ls(p);

        splay(p); //不加会tle... 不知道为什么

		return p;

	}

	bool iscon(int x,int y){return findrt(x)==findrt(y);}

	void split(int x,int y){//x -> tree rt; y -> splay rt

		makert(x);

		access(y);

		splay(y);

	}

	void link(int x,int y){

		makert(x);

		if(findrt(y)!=x)fa(x)=y;

	}

    void cut(int x,int y){

        split(x,y);

        if(fa(x)==y&&rs(x)==0)

            fa(x)=ls(y)=0,pu(y);

    }

	void pr(){

		rep(i,1,n)printf("nd=%d fa=%d ls=%d rs=%d sum=%d rv=%d\n",i,fa(i),ls(i),rs(i),tree[i].sum,tree[i].rv);

	}

}lct;

//init

rep(i,1,n)tree[i].sum=val[i];

//query a chain

	lct.split(b,c);

	ans=lct.tree[c].sum;

//modify one point

	lct.makert(b);

	val[b]=c;

	lct.pu(b);

相关文章