可以用平衡树解决的问题

[[ slider_text ]]

[[ item.c ]]

可以用平衡树解决的问题

发布时间 2023-09-24 作者：fogsail 来源：算法小站

线段树 dp fhq-treap 平衡树

## 平衡树常见问题
### ZJOI2006 书架
**[ZJOI2006 书架](https://www.luogu.com.cn/problem/P2596)**
平衡树，需要支持`5`个操作，分别是
* `Top s`，将元素`s`置顶
*  `Bottom s`，将元素`s`置底
*  `Insert s t`，如果编号为`s`的书上面有`x`本书，放回这本书时它上面应该有`x+t`本书
*  `ask s`，询问`s`的排名
*  `query s`，根据排名`s`来查询书的编号

**算法分析**
先看怎么构建**无旋 treap**，构造函数
```bash
explicit Treap(const vector<S> &a, int n, map<S, int> &idx) : _n(n) {
	// 可以直接将值映射到，树中某个节点的编号

tot = root = 0;
	nodes = vector<node> (_n+1, node());
	for (int i = 1; i <= n; i++) {
		// 依次有 idx = [1, 2, .., n]，单调递增
		idx[ a[i] ] = newnode(a[i]);
		root = merge(root, idx[ a[i] ]);
	}
}
```
可以考虑 `root = merge(root, idx[ a[i] ])` 来构造无旋 treap，其中 `a[i] -> idx[ a[i] ]`,
将数组的值映射到 treap 中的节点编号
其中，`root = merge(root, merge(a1, a2)...)`，这样可以保证先后顺序

**无旋 treap**的`merge(a, b)`一定是要保证**有序的**，即$$a < b$$，根据这一点可以执行很多操作。

> 如何执行**Top**操作

`Top x`，实际上是将数组值为`x`的节点放到最前面，那么值为`x`的点在**树中的位置**在哪里呢？
节点`x`对应树中`info = idx[x]`的节点，考虑`p = get_pos( idx[x] )`获取**节点位置**
节点位置实际上就是这个点的 **rank**（实际上就是先后顺序，从前往后数第`p`个）

需要先`split(root, p-1)`把树分成`t1, t2`两个部分，那么所要求的点，是`t2`的排名第一的元素
需要将`t2`二次分裂，`auto [now, r] = split(t2, 1)`，这样就得到了`now`这个数了
> 怎么把它放在第一个呢？

用**merge**操作，`merge(merge(now, t1), r)`，这样就可以了，注意`t1`我们没有二次分裂
分裂后的树，按相对顺序再粘回去

> **Bottom**操作大同小异，**Ask**和**Query**操作也不难
  `Ask x`实际上就是询问数组值为`x`的点，它的**rank**是多少？`get_pos(idx[x])`即可解决
  `Query x`是询问**rank = x**的节点，它的`info`是多少
  只需要`auto[t1, t2] = split(root, x-1), auto [now, r] = split(t2, 1)`即可得到`now`，返回其`info`即可
  
> 比较复杂的是**Insert**操作，`Insert (x, -1)`需要找到`x`的**前驱**`pre`，然后交换`pre`和`x`的位置

怎么找前驱？还是用`split, merge`操作，首先需要分裂出`x`对应的节点`now`，
此时它的位置是`p = get_pos( idx[x] )`

*  `auto [t1, t2] = split(root, p-1)`，然后对`t2`**二次分裂**，
    `auto [now, r] = split(t2, 1)`，这样就得到了`now`

*  那么`pre`怎么获取？`pre`一定在`t1`中，对`t1`进行**二次分裂**，
    `auto [l, pre] = split(t1, p-2)`
	
然后按修改后的顺序**粘回去**，`merge(merge(merge(l, now), pre), r)`

### TJOI2007 书架
**[TJOI2007书架](https://www.luogu.com.cn/problem/P3850)**
**问题描述**
一开始有$$n$$本书，现在给你$$m$$本书，要求把$$m$$本书插入这$$n$$本书中间，
这$$m$$本书用`name p`给出，表示将`name`这本书插入`p`这个位置。
给定$$q$$个询问，每个询问用一个数$$p$$表示，查询$$p$$这个位置的书名

**算法分析**
平衡树模版，难点在于怎么实现`pos_ins(const string &str, int p)`
即在`p`位置插入`str`

**注意**，如果有初始化操作，`Treap`构造函数中，数组要开$$O(n+m)$$大小（把插入元素要算进去）

需要按`p-1`分裂为`[l, r]`两棵子树，然后考虑新建节点`nd`，最后按顺序合并
`merge(t1, merge(nd, t2))`

```bash
auto pos_ins = [&](const string &str, int p) -> void {
	auto [t1, t2] = tr.split(tr.root, p-1);
	int nd = tr.newnode(str);
	tr.root = tr.merge(t1, tr.merge(nd, t2));
};
```
其他部分大同小异

### ZJOI2007 报表统计
**[ZJOI2007报表统计](https://www.luogu.com.cn/problem/P1110)**
**问题描述**
给定一个长度为$$n$$的整数序列$$a$$，有三种操作
*  `Insert i k`，在原序列第$$i$$个元素后面添加一个新元素$$k$$
   如果原序列第$$i$$个元素之后已经添加了若干元素，那么将$$k$$添加在这些元素之后

*  `Min_gap`，查询相邻元素差值绝对值的最小值

*  `Min_sort_gap`，查询所有元素中最接近的两个元素差值（绝对值）

**算法分析**

首先考虑`Insert`操作，可以用$$d_i$$维护$$i$$后面加入了多少个元素，实际上`Insert i`相当于在$$p = i + d_i$$位置执行插入

但本问题是要求相邻元素差值最小，需要知道在某个位置$$p$$插入的元素**具体是哪些**
考虑用$$V_p$$表示在$$p$$位置插入的元素集合（没插入过就令其为空）

> 首先考虑 `Min_sort_gap` 怎么求，考虑平衡树 `tr`

如果我们把原序列和插入的**所有数**都保存下来，用**平衡树维护**，当考虑一个数`x`时，
在平衡树中找$$x$$的前驱$$xl$$，后继$$xr$$，然后和`minsv`取一个$$\min$$
即$$minsv = \min (|x-xl|, |x-xr|)$$，然后再执行插入 `tr.insert(x)`，这样就维护了`minsv`

**特别注意**，这里可能会出现**重复元素**，找$$x$$前驱的时候要按$$x$$分裂，
这样左子树中的元素$$\leqslant x$$，就考虑到了重复的情况

>  相邻差值 `Min_gap` 怎么求？

一般来说，序列问题，有序区间最值，可以考虑**线段树**，至于本例中还涉及到 `Insert`操作
考虑怎么把问题转换成**线段树单点修改**

不难想到，初始化的时候，线段树维护序列 $$v\_i = |a\_i - a\_{i-1}|$$，考虑在$$p$$位置插入$$x$$，$$v\_p$$会怎么变？

假设$$p$$位置已经插入了一些元素$$x_1\cdots x_k$$，那么再在$$p$$处插入$$x$$，
它是接在$$x_k$$之后的，也就是说，它和$$p$$位置**最后插入的元素**是多少有关

$$p$$位置第一个插入的元素实际上就是$$a_p$$，最后一个插入元素记为$$last_p$$，那么

需要求的就是$$min(|x-last\_p|, |x-a\_{p+1}|)$$，注意到$$|a\_{p+1} - a\_{p}|$$已经用线段树维护了
所以$$|x-a\_{p+1}|$$可以考虑用线段树维护，对$$p+1$$位置单点修改，
那么$$|x-last_p|$$部分可以暴力维护，用`minv`来存

具体来说，在$$p$$处插入$$x$$，考虑线段树单点修改，$$p+1$$处改成值$$|a\_{p+1} - x|$$
同时呢，维护$$minv = min(|x-last_p|), \ last_p = x$$

`Min_gap`的值实际上就是`min(all_prod(), minv)`

>  这样看来，`Insert p x` 就很简单了

执行上述的单点修改，同时在平衡树中找前驱后继，维护`Min_sort_gap`即可

### TJOI2013 最长上升子序列
**[TJOI2013最长上升子序列](https://www.luogu.com.cn/problem/P4309)**
**问题描述**
给定一个序列，初始为空，给定$$n$$个数，第$$k$$个数是$$x_k$$
表示需要在**位置**$$x_k$$处插入$$k$$
输出$$n$$行，第$$i$$行表示$$i$$这个数被插入之后，最长上升子序列的长度

**算法分析**
> 先考虑静态怎么做？给定一个序列$$a$$，怎么维护 LIS ？

这个问题不难
```math
\displaystyle
dp_i = \left( \max_{j < i, \ a_j < a_i} dp_j \right) + 1
```
考虑位置$$i$$的时候，先区间查询最大值，线段树查$$[1, a_i - 1]$$，得到`maxv`
然后单点修改，`set(a[i], maxv + 1)`

>  动态版本呢？本题要考虑的是，下标$$p$$可能反复插入很多数$$x_1, \cdots x_m$$

**一个位置反复插入**，这种问题可以考虑平衡树，在$$p$$位置插入$$x$$，可以考虑**按下标分裂**
```bash
void pos_ins(int p, S val) {
      auto [tl, tr] = split(root, p);
      int now = newnode(val);
      root = merge(tl, merge(now, tr));
}
```
>  考虑如何动态维护 LIS

注意到，平衡树维护完成之后，从小到大的数依次是$$(a_1, a_2, \cdots, a_n)$$，
它构成了一个$$1 \sim n$$的**排列**，不妨设$$n = 5$$，那么最后可能的序列是
$$(4, 5, 2, \textcolor{red}{1}, 3)$$，而假设我们需要求$$i = 1$$时的答案

考虑$$dp(i) = \max dp(j) + 1$$，这里的$$i, j$$都是**下标**，而我们平衡树中考虑的$$i = 1$$（红色字体），
实际上是**值（值域）**，怎么办呢？

注意到序列是**排列**，并且 $$\displaystyle dp(i) = \left( \max_{j <i,\ a_j < a_i } dp(j) \right) + 1$$

其中 $$j <i, a_j <a_i$$ 这两个条件是**对称的**，所以**逆映射**$$i \to a_i,  \  a_i \to i$$ 并不影响结果
交换$$i, a_i$$，令`ai = tr.kth(root, i)`，`a[ai] = i` 并不影响结果，还原$$a$$数组后计算 LIS 即可

### TJOI2019 甲苯先生的滚榜
**[TJOI2019甲苯先生的滚榜](https://www.luogu.com.cn/problem/P5338)**
**问题描述**
实现一个 OJ，通过题目的数量不相等，则通过题目数量多的人排名靠前，通过题目数量相同的话，
罚时更少的人排名靠前。

给定$$m, n, \text{seed}$$，随机生成数据，$$m$$表示参赛总人数，
$$n$$表示一共有$$n$$次 AC，假设 AC 已经去重，一个提交用$$(u, v)$$描述，$$u$$表示选手编号，
实际上，这表示 `a[u].cnt++,  a[u].tim += v`，$$(u, v)$$ 都是随机生成的

现在问，对于每一个 AC，选手$$u$$想知道排在他前面的有几个人？

**算法分析**
很标准的平衡树问题，求选手$$u$$的排名，只需要查询`Rank( a[u] ) - 1`即可
那么对于一个 AC，怎么去修改选手的罚时呢？

一开始将所有选手都插入平衡树中，平衡树保存选手**初始状态**，即$$(cnt, tim) = (0, 0)$$
对于一个 AC，`del( a[u] )` 之后，令 `a[u].cnt += 1, a[u].tim += v`，
然后再插入 `Insert( a[u] )`，并查询 `a[u]` 的 `Rank` 即可

**注意**，如果平衡树涉及插入和删除操作，树的大小不能开到`n`，而应该把树大小开到$$O(m+n)$$范围才比较合适

## 懒标记
### 银河英雄传说V2
**[银河英雄传说V2](https://www.luogu.com.cn/problem/P4847)**
**问题描述**
给定$$n$$个长度为$$1$$的序列，第$$i$$个序列中有一个元素，值为$$a_i$$，接下来有$$3$$种操作

*  `M x y`，把$$x$$所在的序列放到$$y$$所在的序列之后，如果已经在同一个序列了，不进行操作

*  `D x`，把$$x$$所在的序列，从$$x$$处断开，把$$x$$以及$$x$$之后的元素单独取出来作为一个序列

*  `Q x y`，询问$$x, y$$之间（包括$$x, y$$）所有元素值的和，如果$$x, y$$不在一个序列，输出$$-1$$

**算法分析**
对于`D x`操作，不难发现它和`FHQ-treap`的`split`操作类似，那么如何判断`x, y`是否在同一个序列？
类似并查集的思想，`x`和`y`都跳到根，看一下是不是同一个根节点
`Q x y`只需要跳到根去检查即可。

至于`M x y`，将`x, y`分别跳到根之后，再执行`merge`操作即可

**特别注意**，跳到根之后，$$x \to fa_x, \ y \to fa_y$$，如果他们属于同一个序列，怎么计算元素和？

实际上，计算排名，将$$[rk_x, rk_y]$$这一段分裂出来，然后计算子树根节点的`sum`即可
`sum`信息可以用**平衡树**来维护

> 另外，怎么完成`D x`的分裂操作呢？

假设分裂之后我们得到二元组`(t1, t2)`，即分裂后的两棵树的**树根**
此时需要将`t1, t2`都连到**哨兵节点**中（在并查集中，**哨兵节点**就是$$0$$）
即 `t[t1].fa = 0, t[t2].fa = 0`

###  郁闷的出纳员
**[郁闷的出纳员](https://www.luogu.com.cn/problem/P1486)**
**问题描述**
给定两个整数$$n, minv$$，写一种数据结构，维护$$n$$个操作

* `I k`，输入$$k$$，如果$$k \geqslant minv$$，插入$$k$$

* `A k`，将每个数都加上`k`

* `S k`，将每个数都减去$$k$$，并删除所有$$< minv$$的数

*  `F k`，查询第$$k$$大的数

**算法分析**
需要了解对于这几种操作，`FHQ-treap`需要做哪些事情？
注意到本问题是**对所有数加**，可以不使用懒标记，而用全局变量

记工资增加的数为$$\Delta$$，平衡树中只维护**初始工资数目**，假设节点初始工资为$$x$$
那么实际工资是$$x_2 \leftarrow x + \Delta$$，这样的话，$$4$$种操作就对应

`A k`实际上就是$$\Delta = \Delta + k$$，`S k`对应$$\Delta = \Delta - k$$
同时还要看看实际工资是否满足 $$x + \Delta < minv$$，也就是说，要删除**原数据**$$< minv - \Delta$$的所有点
按$$minv- \Delta - 1$$分裂成`[t1, t2]`，扔掉`t1`，让`root = t2`即可

`I val`实际上对应插入，插入的人**实际工资**是$$val$$，但可能插入之前，全员**调整过工资**了
所以，$$x + \Delta = val$$，那么$$val - \Delta$$才对应**初始工资**
平衡树应该维护这个初始工资

`F k`是找区间第$$k$$大，也就是找$$rank = \text{size}(root) - k + 1$$的节点

### 序列终结者
**[序列终结者](https://www.luogu.com.cn/problem/P4146)**
**问题描述**
给定一个长度为$$n$$的整数序列，支持三种操作

*  将$$[L, R]$$区间内的所有数都加上$$V$$

*  翻转$$[L, R]$$区间

*  求$$[L, R]$$区间的最大值

**算法分析**
区间最值，一开始可能会想到用线段树，但是线段树很难处理**翻转操作**，考虑平衡树解决区间问题

注意到本问题存在两种修改操作，`lazy`标记用`array<int, 2>`来封装，二元组`(tag1, tag2)`
其中`tag1 = {0, 1}`，表示是否需要翻转，修改的时候用`^= 1`即可
`tag2`表示区间的值要增加多少？修改的时候令 `tag2 += v`

同时，平衡树需要维护**原始值，整棵子树的最小值**，在`maintain`中修改即可
`info`信息同样用**二元组**封装`(val, minv)`，`maintain(u)`实际上就是
`t[u].minv = min( t[u].minv, ls.minv, rs.minv )`，其中`ls, rs`分别表示左右儿子

询问的时候，记得**下传懒标记**即可

> 懒标记怎么复合的呢？$$f(g())$$

实际上，新的标记是一个二元组 `( f[0]^g[0],  f[1]+g[1] )`

>  最后，`mapping`操作怎么写呢？假设需要对`nd`节点`mapping`

翻转操作很简单，文艺平衡树这道例题写过翻转操作
如果节点`nd`存在翻转标记，令`swap( nd.cld[0], nd.cld[1] )`
如果有增加标记`tag2`，那么节点的值`nd.info[0] += tag2, nd.info[1] += tag2`
其中`info[0] = 初始值, info[1] = 子树的 minv`

**特别注意**，区间翻转的懒标记`tag1`和区间加的懒标记`tag2`**不能直接复合**
需要分开来维护
**对于懒标记无法直接复合的情况**，可以这样来维护`mapping`

```bash
inline void push(int u) {
	if (t[u].lazy == id()) return;

auto f = t[u].lazy;

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

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

// mapping 中用一个 flag 标签，表示某个操作应该映射哪一个懒标记

void mapping(Arr f, Node<Arr, Arr, id> &nd, int fl) {
    auto [tg1, tg2] = f;

if (fl == 0) {
        if (!tg1) return;
        swap(nd.cld[0], nd.cld[1]);
    }
    else {
        if (!tg2) return;
        nd.info[0] += tg2, nd.info[1] += tg2;
    }
}
```

### 贫穷
**[贫穷](https://www.luogu.com.cn/problem/P5217)**
**问题描述**
实现一个文本编辑器，支持以下操作

*  `I x c`，在第$$x$$个字母后面插入$$c$$

*  `D x`，删除第$$x$$个字母

*  `R x y`，翻转文本区间$$[x, y]$$

*  `P x`，输出**初始文本**中第$$x$$个字母在当前文本中的位置，特别地，不存在输出$$0$$

*  `T x`，输出当前文本中第$$x$$个字母

*  `Q x y`，输出当前文本中$$[x, y]$$内出现的字母的种类数

**算法分析**
> 怎么区分初始文本位置和当前文本位置？

当前文本位置可以直接根据**平衡树**得出，平衡树的`Find( idx )`操作
可以直接返回初始编号为`idx`的节点，最后的下标是多少

对于`P x`，需要在一开始初始化序列的时候，维护`p = idx(j)`
即初始序列下标为`j`的节点，映射到平衡树中**编号是`p`**的树节点，
这样 `P x` 的操作，对应返回 `Find( idx[x] )`即可

另外，因为存在**删除**操作，这里采用**懒惰删除**，用`is_del(p)`表示**树中编号**为`p`的节点是否被删除
如果`is_del( idx[x] ) = true`，那么直接输出`0`即可

>  怎么表示区间字母出现的种类数？

实际上可以用**状态压缩**，如果`c`出现了，那么就令 `sta |= ( 1 << (c-'a') )`即可
`maintain`的时候，节点 `ls.sta ｜ rs.sta` 即可

为了方便，平衡树中的节点，`info`信息还需要维护**节点编号**对应的**字符**，
`tr.t[ idx ] = c` 表示树节点`idx`存的是字符`c`
如果`idx`节点已经被删除了，就令`info = -1`（这样可以不需要`is_del`标记了）

> 特别需要注意的问题

*  在`insert`和`delete`的时候，注意是按照`key`来`split`还是按照`size`来`split`
   调用`splitKey`还是调用`split`，很重要
   
*  `Find(idx)`函数，往父节点找，如果父节点有延迟标记，要先下传

```bash
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;
}

void push_fa(int x) {
	if (t[x].fa) push_fa(t[x].fa);
	push(x);
}
```

上一篇：FHQ Treap 一种常用的平衡树下一篇：图的连通性，有向图强连通分量

看完文章有啥想法