替罪羊樹

平衡樹的一種。其特點是采用 “摧毀—重建” 的方法維護(hù) BST 的平衡。

具體而言，當(dāng)我們發(fā)現(xiàn)樹上有一棵子樹不平衡了，就摧毀它，然后重新建一棵平衡的子樹。

不平衡率

我們定義不平衡率 \(\alpha\in[0.5,1]\) 為：一棵以 \(u\) 為根的子樹，若其左子樹或右子樹占比大于 \(\alpha\)，就認(rèn)為不平衡。

顯然，當(dāng) \(\alpha=0.5\) 時，BST 是絕對平衡的；當(dāng) \(\alpha=1\) 時，BST 表現(xiàn)為一條鏈。

替罪羊樹復(fù)雜度的關(guān)鍵就在于 \(\alpha\) 的設(shè)定。根據(jù)某 OIer_Automation 的經(jīng)驗，有修改時，\(\alpha=0.75\) 最優(yōu)；無修改時，\(\alpha=0.85\) 最優(yōu)。但是特殊地，在替罪羊樹套某些其他數(shù)據(jù)結(jié)構(gòu)時，應(yīng)當(dāng)盡量減少重構(gòu)的次數(shù)，即 \(\alpha\) 應(yīng)盡量取大。

基本操作

重構(gòu)

判斷是否需要重構(gòu)，只需判斷最大的一個兒子的大小是否大于當(dāng)前子樹的大小 \(\times\alpha\) 即可。

bool nbl(int u){
    return max(t[lu].sm,t[ru].sm)>=alpha*t[u].sm;
}

然后重構(gòu)的時候，先把當(dāng)前子樹拍平，然后按照拍平后的數(shù)組建樹即可。

void flatten(int u){
    if(!u) return;
    flatten(lu);
    if(t[u].cnt) ord[++cnt]=u;
    flatten(ru);
}
void build(int l,int r,int&u){
    if(l>r) return u=0,void();
    int mid=(l+r)>>1;
    u=ord[mid];
    build(l,mid-1,lu),build(mid+1,r,ru);
    update(u);
}
void redo(int&u){
    cnt=0;
    flatten(u);
    build(1,cnt,u);
}

重構(gòu)時的代碼就是

if(nbl(u)) redo(u);

插入

替罪羊樹上的一個節(jié)點保存一個當(dāng)前點的數(shù)的數(shù)量。插入時從根往下走，如果沒有新建節(jié)點就新建一個，否則按照大小關(guān)系遞歸即可。

void ins(int&u,int x){
    if(!u) return t[u=++tot]={0,0,x,1,1,1,1},void();
    if(x==t[u].val) t[u].cnt++;
    else if(x<t[u].val) ins(lu,x);
    else ins(ru,x);
    update(u);
    if(nbl(u)) redo(u);
}

刪除

也是同理的。

void del(int&u,int x){
    if(t[u].val==x) t[u].cnt--;
    else if(x<t[u].val) del(lu,x);
    else del(ru,x);
    update(u);
    if(nbl(u)) redo(u);
}

其余操作和一般的平衡樹寫法無異。

模板

P3369 【模板】普通平衡樹。

constexpr int MAXN=1e5+5;
constexpr double alpha=0.75;
int rt;
struct{
	#define lu t[u].ls
	#define ru t[u].rs
	struct ScapeGoatTree{
		int ls,rs,val,cnt,s,sd,siz;
	}t[MAXN];
	int ord[MAXN],cnt;
	int tot;
	void flatten(int u){
		if(!u) return;
		flatten(lu);
		if(t[u].cnt) ord[++cnt]=u;
		flatten(ru);
	}
	void update(int u){
		t[u].s=t[lu].s+t[ru].s+1;
		t[u].sd=t[lu].sd+t[ru].sd+(t[u].cnt!=0);
		t[u].siz=t[lu].siz+t[ru].siz+t[u].cnt;
	}
	void build(int l,int r,int&u){
		if(l>r) return u=0,void();
		int mid=(l+r)>>1;
		u=ord[mid];
		build(l,mid-1,lu),build(mid+1,r,ru);
		update(u);
	}
	void redo(int&u){
		cnt=0;
		flatten(u);
		build(1,cnt,u);
	}
	bool nbl(int u){
		return max(t[lu].s,t[ru].s)>=alpha*t[u].s||alpha*t[u].s>=t[u].sd;
	}
	void ins(int&u,int x){
		if(!u) return t[u=++tot]={0,0,x,1,1,1,1},void();
		if(x==t[u].val) t[u].cnt++;
		else if(x<t[u].val) ins(lu,x);
		else ins(ru,x);
		update(u);
		if(nbl(u)) redo(u);
	}
	void del(int&u,int x){
		if(t[u].val==x) t[u].cnt--;
		else if(x<t[u].val) del(lu,x);
		else del(ru,x);
		update(u);
		if(nbl(u)) redo(u);
	}
	int rnk(int u,int x){
		if(!u) return 0;
		if(t[u].val==x&&t[u].cnt) return t[lu].siz;
		else if(t[u].val<x) return t[lu].siz+t[u].cnt+rnk(ru,x);
		else return rnk(lu,x);
	}
	int kth(int u,int k){
		if(!u) return 0;
		if(t[lu].siz<k&&k<=t[lu].siz+t[u].cnt) return t[u].val;
		else if(k<=t[lu].siz) return kth(lu,k);
		else return kth(ru,k-t[lu].siz-t[u].cnt);
	}
	int pre(int u,int x){
		return kth(u,rnk(u,x));
	}
	int nxt(int u,int x){
		return kth(u,rnk(u,x+1)+1);
	}
}T;

int main(){
	int n=read();
	while(n--){
		int opt=read(),x=read();
		switch(opt){
			case 1: T.ins(rt,x);break;
			case 2: T.del(rt,x);break;
			case 3: write(T.rnk(rt,x)+1);break;
			case 4: write(T.kth(rt,x));break;
			case 5: write(T.pre(rt,x));break;
			default:write(T.nxt(rt,x));break;
		}
	}
	return fw,0;
}

典型應(yīng)用

P3920 [WC2014] 紫荊花之戀

點分樹套替罪羊樹，又稱動態(tài)點分樹。

點分樹可以很方便地求解帶修處理樹上路徑問題，但是在這道題中這棵樹的形態(tài)還在發(fā)生變化，為了保證樹高為 \(\log n\)，我們需要不斷地重構(gòu)點分樹，而這樣做顯然不優(yōu)。

于是我們采取替罪羊樹的思想：對于一棵子樹，如果它超出了我們設(shè)定的不平衡率，我們就重構(gòu)它。這樣做就可以在一個 \(O(n\log^2n)\) 的時間內(nèi)實現(xiàn)點分樹的動態(tài)插入了。

然后對應(yīng)到本道題，既然支持了動態(tài)插入，考慮去做 \(\text{dist}(i,j)\le r_i+r_j\) 的計數(shù)。那這個問題就很經(jīng)典了，對于當(dāng)前子樹的根 \(p\)，轉(zhuǎn)化為 \(\text{dist}(i,p)+\text{dist}(p,j)\le r_i+r_j\)，移項得 \(\text{dist}(i,p)-r_i\le r_j-\text{dist}(p,j)\)，按照套路對每個節(jié)點維護(hù) \(\rm SG\) 和 \(\rm CH\) 兩棵平衡樹，分別維護(hù)子樹內(nèi)所有點的 \(\text{dist}(i,p)-r_i\) 的值和 \(\text{dist}(i,\text{fa}(p))-r_i\) 的值，查詢時直接查排名即可。