526互联

【学习笔记】(13) 平衡树——记住不的板子

发布时间 2023-10-06 22:37:42作者: Aurora-JC

Treap

Splay

无旋Treap——fhq treap

简介

就是没有旋转操作的 Treap，一些性质什么的都跟 Treap 类似。

算法介绍

(1)merge(x,y)

将两棵“有序”（x中元素的权值最大值小于 y 中元素权值最小值）的Treap合并成一棵。


int ch[N][2], sz[N], pri[N], val[N];
//val 为权值，pri 为优先级，sz 为子树大小 
int merge(int x, int y){
		if(!x || !y) return x + y;
		//若 x 的优先级小，则它应该新树的根 
		//由于 x 中元素都小于 y 中元素权值，所以合并 x 的右子树和 y 
		if(pri[x] < pri[y]) return ch[x][1] = merge(ch[x][1], y), modify(x), x;
		//另一种情况 
		else return ch[y][0] = merge(x, ch[y][0]), modify(y), y;
	}

(2.1) Split(u, v, x, y)

根据权值 v 将 u 这棵 Treap 分为两棵平衡树 x ,y,其中 x 中元素权值均小于等于 v, y 中元素权值均大于 v。

void split(int u, int v, int &x, int &y){
	if(!u) return x = y = 0, void();
	if(val[u] <= v) x = u, split(ch[u][1], v, ch[u][1], y); //u 的权值比 v 小，说明 u 以及 u 的左子树都属于 x, 所以递归划分 u 的右子树  
	else y = u, split(ch[u][0], v, x, ch[u][0]); //另一种情况 
	modify(u);
}

(2.2) Split(u, kth, x, y)

跟据子树大小将树 u 分成两棵树 x, y。 x 的大小为 k ,他包含树 u 中权值前 k 小的元素。

void split(int u, int k, int &x, int &y){
	if(!u) return x = y = 0, void();
	if(k <= sz[ch[u][0]]) y = u, split(ch[u][0], k, x, ch[u][0]); //左子树大小大于 k ，说明 u 以及 u 的右子树都在 y 中， 递归划分左子树 
	else x = u, split(ch[u][1], k - sz[ch[u][0]] - 1, ch[u][1], y);
	modify(u);
}

(3) insert

int newnode(int v){ // 新建一个权值为 v 的节点 
	sz[++tot] = 1, pri[tot] = rnd(), val[tot] = v;
	return tot;
}
void insert(int k, int v){ //在以 rt 为根的 Treap 中 k 的位置插入一个值为 v 的元素 
	split(rt, k, r1, r2); //根据排名分 
	rt = merge(r1, merge(newnode(v), r2));
}
void insert(int &u, int v){ //在以 u 为根的 Treap 中插入一个值为 v 的元素
	split(u, v, r1, r2); //根据权值分 
	u = merge(r1, merge(newnode(v), r2));
}
//上面两个 split 是不一样的

(4) delte(u,v)

删除 u 为根的 Treap 中权值为 v 的所有元素。

void del(int &u, int v){
	int L, R, p, q; 
	split(u, v, L, R); //调用 (2.1) 对应代码 
	split(L, v - 1, p, q);
	u = merge(L, merge(p, q));
}

注意：此操作会将所有权值为 v 的元素都删除掉，若只删除一个，则需要求出 v 的排名，在调用 split(u,k,x,y) 以便实现删除一个元素。

(5) modify(u,l,r)

对区间 \([l,r]\) 进行操作，例如区间加、区间翻转等。

void modify(int &u, int l, int r){
	int L, R, p, q; 
	split(u, l - 1, L, R); //调用 (2.2) 对应代码 
	split(R, r - l + 1, p, q);
	solve(p);
	u = merge(L, merge(p, q));
}

Merge(x, y)

合并两个 “乱序” Treap （即 \(x\) 中的元素并不全小于 \(y\) 中的元素），也就是合并任意两个 Treap。
复杂度 \(O(n\log & n)\)

void Merge(int x, int y){
	if(!x || !y) return x + y;
	if(pri[x] > pri[y]) swap(x, y);
	int L, R;
	split(v, val[u], L, R); //调用 (2.1) 对应代码 
	ch[x][0] = Merge(ch[x][0], L);
	ch[x][1] = Merge(ch[x][1], R);
}

其他操作

1.删除

删除一个数 \(v\)：先用 \(v\) 按照权值分裂成两棵树 \(x,z\)，再用 \(v−1\) 按照权值将 \(x\) 分裂成两棵树 \(x,y\)。此时 \(y\) 的所有节点的权值就都是 \(v\)。但是我们只能删一个，因此可以将 \(y\) 的左右节点合并起来，这样 \(y\) 的节点个数就少了一个。最后再合并回来即可。

void del(int v){
	int x, y, z;
	split(rt, v, x, z), split(x, v - 1, x, y);
	y = merge(ch[y][0], ch[y][1]);
	rt = merge(merge(x, y), z); 
}

2.第 \(k\) 大

查找第 \(k\) 大的数：假设当前遍历到节点 \(u\)。若 \(k≤sz_{ls_u}\) 则向左儿子递归；若 \(k=sz_{ls_u}+1\) 则直接返回 \(val_u\)；否则向右儿子递归。

int kth(int u, int k){
	while(1){
		if(k <= sz[ch[u][0]]) u = ch[u][0];
		else if(k == sz[ch[u][0]] + 1) return u;
		else k -= sz[ch[u][0]] + 1, u = ch[u][1]; 
	}
}

3. 前缀/后继

查找 \(v\) 的前驱：用 \(v−1\) 按照权值分裂成 \(x,y\)，再找 \(x\) 的最大值即可（即 \(x\) 的第 \(sz_x\) 大值）。后继同理。

//前驱 
split(rt, v - 1, x, y);
printf("%d\n", val[kth(x, sz[x])]);
rt = merge(x, y);

//后继 
split(rt, v, x, y);
printf("%d\n", val[tr.kth(y, 1)]);
rt = tr.merge(x, y);

4. 排名

查询 \(v\) 的排名：用 \(v−1\) 按照权值分裂成 \(x,T\)，那么答案即为 \(sz_x+1\)。最后合并。

split(rt, v - 1, x, y);
printf("%d\n", sz[x] + 1);
rt = merge(x, y);

例题

Ⅰ. P3369 【模板】普通平衡树

模板，操作上面都讲过。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 67;
int read(){
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
	while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
	return x * f;
}

bool _u;

mt19937 rnd((unsigned)time(0));
int n, tot, rt;
int ch[N][2], sz[N], pri[N], val[N];

struct FHQ{
	void modify(int x){sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + 1;}
	int new_node(int v){sz[++tot] = 1, val[tot] = v, pri[tot] = rnd(); return tot;}
	int merge(int x, int y){
		if(!x || !y) return x + y;
		if(pri[x] < pri[y]) return ch[x][1] = merge(ch[x][1], y), modify(x), x;
		else return ch[y][0] = merge(x, ch[y][0]), modify(y), y;
	} 
	void split(int u, int v, int &x, int &y){
		if(!u) return x = y = 0, void();
		if(val[u] <= v) x = u, split(ch[u][1], v, ch[u][1], y);
		else y = u, split(ch[u][0], v, x, ch[u][0]);
		modify(u);
	}
	int kth(int u, int k){
		while(1){
			if(k <= sz[ch[u][0]]) u = ch[u][0];
			else if(k == sz[ch[u][0]] + 1) return u;
			else k -= sz[ch[u][0]] + 1, u = ch[u][1]; 
		}
	}
}tr;

bool _v;

int main(){
	cerr << abs(&_u - &_v) / 1048576.0 << " MB\n";

	n = read();
	while(n--){
		int opt = read(), v = read(), x, y, z;
		if(opt == 1){
			tr.split(rt, v, x, y);
			rt = tr.merge(tr.merge(x, tr.new_node(v)), y);
		} else if(opt == 2){
			tr.split(rt, v, x, z), tr.split(x, v - 1, x, y);
			y = tr.merge(ch[y][0], ch[y][1]);
			rt = tr.merge(tr.merge(x, y), z); 
		} else if(opt == 3){
			tr.split(rt, v - 1, x, y);
			printf("%d\n", sz[x] + 1);
			rt = tr.merge(x, y);
		} else if(opt == 4){
			printf("%d\n", val[tr.kth(rt, v)]);
		} else if(opt == 5){
			tr.split(rt, v - 1, x, y);
			printf("%d\n", val[tr.kth(x, sz[x])]);
			rt = tr.merge(x, y);
		} else{
			tr.split(rt, v, x, y);
			printf("%d\n", val[tr.kth(y, 1)]);
			rt = tr.merge(x, y);
		}
	}
	return 0;
}

Ⅱ. P4146 序列终结者

为了写这篇博客，终于把6个月前没过的代码调出来了。

对于区间反转与区间加，直接打标记就行了。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 51;
int read(){
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
    while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
    return x * f;   
}
mt19937 rnd((unsigned)time(0));
int n, m, rt, r1, r2, tot;
int maxn[N], val[N], add[N], sz[N];
int ch[N][2], pri[N];
bool lazy[N];
int newnode(int v){
    sz[++tot] = 1, pri[tot] = rnd(), val[tot] = v;
    maxn[tot] = v, add[tot] = 0, lazy[tot] = 0;
    return tot;
}
void pushup(int u){
    sz[u] = sz[ch[u][1]] + sz[ch[u][0]] + 1;
    maxn[u] = val[u];
    if(ch[u][1]) maxn[u] = max(maxn[u], maxn[ch[u][1]]);
    if(ch[u][0]) maxn[u] = max(maxn[u], maxn[ch[u][0]]);
}
void pushdown(int x){
    if(lazy[x]){
        lazy[ch[x][1]] ^= 1, lazy[ch[x][0]] ^= 1;
        swap(ch[x][1], ch[x][0]);
        lazy[x] = 0;
    }
    if(add[x]){
        add[ch[x][1]] += add[x], add[ch[x][0]] += add[x];
        val[ch[x][1]] += add[x], val[ch[x][0]] += add[x];
        maxn[ch[x][1]] += add[x], maxn[ch[x][0]] += add[x];
        add[x] = 0;
    }
}
int merge(int x, int y){
    pushdown(x), pushdown(y);
    if(!x || !y) return x + y;
    int u;
    if(pri[x] < pri[y]) u = x, ch[x][1] = merge(ch[x][1], y);
    else u = y, ch[y][0] = merge(x, ch[y][0]);
    pushup(u);
    return u;
}
void split(int u, int k, int &x, int &y){
    if(!u) return x = y = 0, void();
    pushdown(u);
    if(sz[ch[u][0]] >= k) y = u, split(ch[u][0], k, x, ch[u][0]);
    else x = u, split(ch[u][1], k - sz[ch[u][0]] - 1, ch[u][1], y);
    pushup(u);
}
void insert(int k, int v){
    split(rt, k, r1, r2), rt = merge(r1, merge(newnode(v), r2));
}
int main(){
    n = read(), m = read();
    for(int i = 1; i <= n; ++i) insert(i - 1, 0);
    while(m--){
    	int opt = read(), l = read(), r = read(), v;
    	int x, y, z;
        if(opt == 1){
            v = read();
            split(rt, l - 1, x, y);
            split(y, r - l + 1, y, z);
            val[y] += v, maxn[y] += v, add[y] += v;
            rt = merge(x, merge(y, z));
        }else if(opt == 2){
            split(rt, l - 1, x, y);
            split(y, r - l + 1, y, z);
            lazy[y] ^= 1;
            rt = merge(x, merge(y, z));
        }else{
            split(rt, l - 1, x, y);
            split(y, r - l + 1, y, z);
            printf("%d\n", maxn[y]);
            rt = merge(x, merge(y, z));
        }
    }
    return 0;
}

重量平衡树