FHQ Treap 一种常用的平衡树

[[ slider_text ]]

[[ item.c ]]

FHQ Treap 一种常用的平衡树

发布时间 2023-08-26 作者：zhangminchen 来源：算法小站

fhq-treap 平衡树

## 无旋 treap
FHQ Treap 又称无旋 treap，它是 `tree + heap`结合的数据结构，`priority`的值是随机的，
Treap 必须满足堆的性质，一般来说是小根堆，根节点的`priority`小于子树中的节点，
此外还必须满足二叉搜索树的性质，左子树所有节点的`val`值小于根节点的`val`，
右子树所有节点的`val`大于根节点的`val`

## 基本的维护

维护包括**新建节点，信息维护等等**
```bash
inline int newnode(S info) {
	t[++tot].info = info;
	t[tot].cld[0] = t[tot].cld[1] = t[tot].fa = 0;

t[tot].prio = mrand();
	t[tot].siz = t[tot].cnt = 1;
	t[tot].lazy = id();
	return tot;
}

inline void maintain(int u) {
	#define ls(u) t[u].cld[0]
	#define rs(u) t[u].cld[1]

t[u].siz = t[u].cnt;
	if (t[u].cld[0]) t[u].siz += t[ t[u].cld[0] ].siz, t[ t[u].cld[0] ].fa = u;
	if (t[u].cld[1]) t[u].siz += t[ t[u].cld[1] ].siz, t[ t[u].cld[1] ].fa = u;
}
```

### 分裂 Split
#### 按值分裂
```bash
// 按键值分裂，<= key and > key
pair<int, int> splitKey(int cur, S key)

// 按下标分裂，左边下标 <= k, 右边 > k，下标不会有重复的
pair<int, int> split(int cur, int k)
```

当前的树可能需要**调整平衡性**，需要分裂，接受两个参数，根指针$$cur$$，关键值$$key$$
分裂返回两个子 treap 的根指针

*  $$key < cur$$，此时$$cur$$及其右子树都应该大于$$key$$，属于第二个 treap
   左子树呢？可能一部分更靠右的左子树也 $$> key$$，左子树递归地分裂
   对于大于$$key$$的那部分左子树，作为$$cur$$的左子树

*  $$key \geqslant cur$$，那么$$cur$$及其整个左子树都$$\leqslant key$$，属于第一个 treap
   右子树呢？右子树中更靠左的部分也有可能$$\leqslant key$$，右子树递归分裂
   把$$\leqslant key$$的部分作为$$cur$$的右子树
   
```bash
pair<int, int> splitKey(int cur, S key) {
	if (!cur) return {0, 0};

push(cur);

if (t[cur].info <= key) {
		auto [tl, tr] = splitKey(t[cur].cld[1], key);
		t[cur].cld[1] = tl;
		maintain(cur);
		return {cur, tr};
	}
	else {
		auto [tl, tr] = splitKey(t[cur].cld[0], key);
		t[cur].cld[0] = tr;
		maintain(cur);
		return {tl, cur};
	}
}
```

#### 按排名分裂
某个节点的排名，是树中所有小于此节点值的节点数量$$+1$$
接受两个参数，节点指针$$cur$$和排名$$rk$$，返回分裂后的$$2$$个 treap

其中，第一个 treap 每个节点的排名都 $$\leqslant rk$$
第二个 treap 每个节点的排名 $$> rk$$

*  如果 $$t[ls(u)].siz \geqslant k$$，那么**左子树还要继续递归分裂**
   分裂出的结果假设是`[tl, tr]`，那么`tl`中的所有节点就是我们需要的，他们的排名都$$\leqslant rk$$
   而`tr`肯定是$$> rk$$的，将`t[cur].cld[0] = tr`，左子树置为`tr`，这样`cur`整棵树所有节点排名$$> rk$$

* 否则的话，右子树有一部分可能还会满足，需要在右子树分裂出排名
  满足 $$\leqslant rk - t[ls(u)].siz - 1$$的部分，得到`[tl, tr]`，`tr`肯定是满足排名$$> rk$$的
  `tl`连到`cur`的右子树中，这样`cur`一整棵树，所有节点排名都$$\leqslant rk$$

```bash
// 按下标分裂，左边下标 <= k, 右边 > k，下标不会有重复的
pair<int, int> split(int cur, int k) {
	if (!cur) return {0, 0};

push(cur);

if (k <= t[t[cur].cld[0]].siz) {
		auto [tl, tr] = split(t[cur].cld[0], k);
		t[cur].cld[0] = tr;
		maintain(cur);
		return {tl, cur};            
	}
	else {
		auto [tl, tr] = split(t[cur].cld[1], k - t[t[cur].cld[0]].siz - 1);
		t[cur].cld[1] = tl;
		maintain(cur);
		return {cur, tr};
	}
}
```

### 合并（merge）
合并接受两个参数，左 treap 的指针`u`，右 treap 的指针`v`
必须满足`u`中所有节点的值 $$\leqslant$$ `v`中所有节点的值

`merge(u, v)`必须**有序**

一般来说，合并的两个 Treap 是从原来的 Treap 中分裂出去的，二叉搜索树的性质已经符合
`u`内所有节点值，一般来说是满足$$\leqslant$$`v`中所有节点的值

现在只需要考虑维护`priority`满足堆的性质，普通 Treap 是用旋转操作来维护，那么这里我们用合并

此时`u`内所有节点的值，默认$$\leqslant$$`v`中所有节点，这里用小根堆，那么
*  如果$$prio(u) < prio(v)$$，那么$$u$$应该作为**新的根节点**，并且$$v$$的值大于$$u$$
   所以$$v$$还应该和$$u$$的右子树合并

*  反之，$$v$$作为新的根节点，$$u$$的值比$$v$$小，和$$v$$的左子树合并

```bash
int merge(int x, int y) {
	// x <= y，小根堆
	if (x == 0 || y == 0) return x+y;

push(x), push(y);
	if (t[x].prio < t[y].prio) {
		t[x].cld[1] = merge(t[x].cld[1], y);
		maintain(x);
		return x;
	}
	else {
		t[y].cld[0] = merge(x, t[y].cld[0]);
		maintain(y);
		return y;
	}
}
```

### 插入和删除
#### 插入
假设要插入值为`val`这个点，可以根据`val`分裂当前这个 treap，假设分裂成两棵树，并且
$$T_1 \leqslant val, \quad T_2 > val$$

新开一个节点，然后按顺序粘贴回去即可
合并的时候，**第一棵树所有节点的值必须小于第二棵**

```bash
void insert(S val) {
	auto [tl, tr] = splitKey(root, val);
	int now = newnode(val);
	root = merge(merge(tl, now), tr);
}
```

当然，有时候题目要求所有节点的值**不能相同**，如果相同，那么**计数器**`+1`，这也不难
按照`val`分裂出`[t1, t2]`，子树`t1`再继续按`val-1`分裂，分裂出`[l, now]`

如果`now = 0`，那么就新建一个节点
否则的话，就说明值为`val`的节点已经存在，且它一定是`t[now]`，将其计数器`+1`即可

```bash
void insert(int val) {
    auto [t1, t2] = split(root, val);
    auto [l, now] = split(t1, val-1);

if (now == 0) {
        now = newnode(val);
    }
    else {
        t[now].cnt += 1;
        maintain(now);
    }

root = merge(merge(l, now), t2);
}
```

#### 删除
删除操作也是类似的，插入和删除的核心
都是围绕着$$T1_{right}$$**这个子树（实际上它一般只有一个节点，或者是空）**进行的

但是，注意到$$T1_{right}.cnt \leqslant 1$$的情况中，有可能整个$$T1$$只有这一个节点

一般来说，最后不需要动的是$$T1_{left}, T2$$

```bash
void del(int val) {
    auto [t1, t2] = split(root, val);
    auto [l, now] = split(t1, val-1);

if (t[now].cnt > 1) {
        t[now].cnt --;
        maintain(now);
        root = merge(merge(l, now), t2);
    }
    else {
		now = merge(t[now].cld[0], t[now].cld[1]);
		root = merge(merge(l, now), t2);
    }
}
```

**如果不考虑点的权值重复情况**
```bash
void del(S val) {
	auto [tl, tr] = splitKey(root, val);
	auto [l, r] = splitKey(tl, val-1);

r = merge(t[r].cld[0], t[r].cld[1]);
	root = merge(merge(l, r), tr);
}
```

### 根据值查询排名
要求排名，实际上就是求值比$$val$$**严格小**的数量$$+1$$，只需要根据$$val-1$$来分裂树
分裂后的第一个树满足$$T_1 \leqslant val-1$$
如果树的值和$$val$$都是整数，那么$$T_1$$就包含了所有值$$< val$$的节点
```bash
// 查询 x 的排名
int Rank(S x) {
	// <= x-1 and >= x
	auto [tl, tr] = splitKey(root, x-1);
	int res = t[tl].siz + 1;
	root = merge(tl, tr);
	return res;
}
```

### 根据排名查询值
如果`rk = t[ ls(u) ].siz + 1`，那么当前节点`u`即为所求
如果左子树的`siz >= rk`，那么去左子树中找，否则去右子树中找排名为`rk - t[ls(u)].siz - 1`的点

```bash
S kth(int u, int k) {
	if (k == t[t[u].cld[0]].siz + 1) return t[u].info;

push(u);
	if (k <= t[t[u].cld[0]].siz) return kth(t[u].cld[0], k);
	else return kth(t[u].cld[1], k - t[t[u].cld[0]].siz - 1);
}
```

### 查询编号为idx的节点当前排名
有时候树的操作可能会将**节点顺序打乱**，我们要找出初始编号是`idx`的树中节点，
在若干次操作之后，它的排名是多少

```bash
// 有时候平衡树维护序列并非有序，需要查询特定节点的排名
void push_fa(int x) {
	if (t[x].fa) push_fa(t[x].fa);
	push(x);
}

int Find(int idx) {
	push_fa(idx);

int res = t[t[idx].cld[0]].siz + t[idx].cnt;
	while (t[idx].fa) {
		if (idx == t[t[idx].fa].cld[1]) {
			res += t[ t[t[idx].fa].cld[0] ].siz + t[t[idx].fa].cnt;
		}
		idx = t[idx].fa;
	}
	return res;
}
```

代码不难理解，如果点在右链上，要把左链和父亲的`siz`也叠加上去

> 特别注意

有时候可能涉及到懒标记，这个时候，要先检查父亲`x -> t[x].fa`及其祖先有没有懒标记
如果有，先要**自顶向下**把懒标记压下去，再处理，否则会出错。

### 查找第一个比 val 小的节点
实际上，就是在比$$val$$小的所有节点中，找出排名最大的那个。
根据$$val-1$$来分裂这个 treap，返回的第一个 treap `t1` 中所有的节点都$$< val$$
接着调用`kth`找出排名是`t1.size`的节点即可
```bash
S pre(S val) {
	auto [tl, tr] = splitKey(root, val-1);
	S res = kth(tl, t[tl].siz);
	root = merge(tl, tr);
	return res;
}
```

### 查找第一个比 val 大的节点
等价于，在比$$val$$大的所有节点中，找出排名最小的，那么根据$$val$$分裂，
返回的第二个 treap 中的所有节点的值都$$> val$$，只需要在这个树中查询排名为$$1$$的节点即可
```bash
S nxt(S val) {
	auto [tl, tr] = splitKey(root, val);
	S res = kth(tr, 1);
	root = merge(tl, tr);
	return res;
}
```

### 建树（build）
#### 方法一
一开始令根节点的指针 `tr->root = nullptr`，然后依次遍历数组元素
`for (auto x : a) tr.insert(x)`
这种方法的时间复杂度是$$O(\log n)$$

#### 方法二，单调栈建树
由于`treap`树，单从随机的`priority`来看，是符合**笛卡尔树**的特征的
可以像笛卡尔树那样，根据单调栈来建树，**难点**是多了一个`upd_size()`的操作

对于笛卡尔树而言，左链是相对不会变的，建树的时候需要维护**右链**`priority`单调递增
也就是说，考虑插入节点`x`，如果 `stk.top().prio > x.prio`，那么`top`应该**弹出**，
同时，`top`指向的子树，将作为`x`的**左子树**（不再存在于右链中）
后续插入的节点只会影响到右链，并不会影响到这个子树
所以，在每一次弹出元素的时候，执行`stk.top()->upd_size()`即可

最后，需要**自底向上**更新一遍右链的`size`，因为这部分都可能受到影响。
好在用单调栈**依次弹出并修改**，就恰好能够做到
```bash
    explicit Treap(const vector<S> &v, int n) : _n(n) {
        // 下标从 1 开始，单调栈构造 treap，维护右链单调递增
        tot = root = 0;
        t = vector<node> (_n+1, node());

for (int i = 1; i <= n; i++) newnode(v[i]);

stack<int> stk;
        for (int i = 1; i <= _n; i++) {
            int last = 0;

while (!stk.empty() && t[stk.top()].prio > t[i].prio) {
                t[i].cld[0] = stk.top();
                maintain(stk.top());
                stk.pop();
            }
            if (!stk.empty()) t[stk.top()].cld[1] = i;
            stk.push(i);
        }

while (stk.size()) {
            root = stk.top();
            maintain(stk.top());
            stk.pop();
        }
    }
```

## 无旋 treap 的区间操作
**[文艺平衡树](https://loj.ac/p/105)**
**问题描述**
写一种数据结构维护一个序列，需要提供如下操作
翻转一个区间，例如原来的有序序列是`5 4 3 2 1`，翻转`[2, 4]`，得到`[5 2 3 4 1]`

**算法分析 怎么执行区间翻转**
![](/media/content_img/fhq-treap-flip.jpg)

翻转实际上是把区间内子树的每一个左右子节点交换位置，如果每一个$$[l, r]$$都依次反转
那么时间复杂度是$$O(n \log n)$$的

但是，我们并不需要知道翻转的中间结果，只需要知道操作完之后的结果，所以并不需要每次都真的去交换。
可以采用**懒标记**的思想，在某个节点打上标记，代表这个子树下的每个左右节点都需要交换。

**具体来说**
一个节点打上懒标记，表示这个节点**已经被修改，但是标记尚未下传**

```bash
// 先执行映射，然后再复合标记

mapping(1, tr.t[now]);
tr.t[now].lazy = comp(1, tr.t[now].lazy);
```

那怎么找到区间`[x, y]`呢，很简单，还是分裂
```bash
auto [t1, t2] = tr.split(tr.root, y);
auto [l, now] = tr.split(t1, x-1);

// 此时 t[now] 及其子树，就代表 [x, y] 这个区间
```

> 什么时候需要下传懒标记？

注意到懒标记是传给儿子节点的，更改儿子前就应该把懒标记传下去了。
也就是说，**树的结构发生变化（分裂或者合并）的时候**，就需要下放懒标记。

**下传标记**
此时需要翻转当前节点的两个子节点
```bash
    inline void push(int u) {
        if (t[u].lazy == id()) return;

auto f = t[u].lazy;
        if (t[u].cld[0])  mapping(f, t[t[u].cld[0]]), t[t[u].cld[0]].lazy = comp(f, t[t[u].cld[0]].lazy);
        if (t[u].cld[1])  mapping(f, t[t[u].cld[1]]), t[t[u].cld[1]].lazy = comp(f, t[t[u].cld[1]].lazy);

t[u].lazy = id();
    }
```

**分裂**
注意到，存在翻转操作，所以 treap 的$$val$$不一定符合二叉搜索树的性质，所以不能直接根据左右子树来递归。
但是，一个$$val$$的**相对排名**是确定的，而排名又和左右子树的大小相关

分裂返回两个 treap，第一个 treap 中节点的排名都$$\leqslant sz$$，第二个 treap 中节点排名全部$$> sz$$
我们称，树中节点排名都$$\leqslant sz$$的子树为**被需要的**

* 如果`t[ls(cur)].siz >= sz`，那么所需要的排名$$\leqslant sz$$的节点一定在`cur`的左子树中
  `cur`的左子树不一定全部都满足“节点排名$$\leqslant sz$$”，但是`cur`的**右子树一定不满足**
  
  还需要继续递归分裂左子树`t[cur].cld[0]`，分裂得到的右子树也**不被需要**，将其作为`cur`的**左子树**
  这样就保证了`cur`所有点的排名都$$> sz$$
  
*  否则的话，左子树全部都是被需要的，右子树一部分被需要
   递归分裂**右子树**，得到$$T_1, T_2$$，其中$$T_1$$也是被需要的，将其作为`cur`的右子树
   这样也恰好能保证`cur`所有节点排名$$\leqslant sz$$

```bash
    // 按下标分裂，左边下标 <= k, 右边 > k，下标不会有重复的
    pair<int, int> split(int cur, int k) {
        if (!cur) return {0, 0};

push(cur);

if (k <= t[t[cur].cld[0]].siz) {
            auto [tl, tr] = split(t[cur].cld[0], k);
            t[cur].cld[0] = tr;
            maintain(cur);
            return {tl, cur};            
        }
        else {
            auto [tl, tr] = split(t[cur].cld[1], k - t[t[cur].cld[0]].siz - 1);
            t[cur].cld[1] = tl;
            maintain(cur);
            return {cur, tr};
        }
    }
```

**合并**
合并和之前的没有什么不同，需要注意的是在合并前下传懒标记

**区间翻转**
抽出区间$$[x, y]$$，做映射变换，再打标记
```bash
auto [t1, t2] = tr.split(tr.root, y);
auto [l, now] = tr.split(t1, x-1);

mapping(1, tr.t[now]), tr.t[now].lazy = comp(1, tr.t[now].lazy);

tr.root = tr.merge(tr.merge(l, now), t2);

// 其中，mapping和comp需要自己定义
// 区间翻转问题，定义如下
void mapping(int f, Node<Arr, int, id> &nd) {
    if (f == 0) return;
    swap(nd.cld[0], nd.cld[1]);
}

int comp(int f, int g) {
    return f ^ g;
}
```

**返回结果**
注意需要在返回的时候，检查是否存在标记，中序遍历返回
```bash
void dfs(int u) {
	if (u == 0) return;

push(u);
	dfs(t[u].cld[0]);
	printf("%d ", t[u].info);
	dfs(t[u].cld[1]);
}
```

上一篇：codeforces数据结构专题（五）下一篇：可以用平衡树解决的问题

看完文章有啥想法