二叉搜索树 & 平衡树

参考资料

• 二叉搜索树 & 平衡树 - OI Wiki

__gnu_pbds::tree

151 Bcpp

#include <bits/extc++.h>
using namespace __gnu_pbds;
tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update> T;

笛卡尔树

137 Bcpp

int top=0;
s[++top]=0;
for(int i=1;i<=n;i++)
{
	while(top&&a[s[top]]>a[i])son[i][0]=s[top--];
	if(s[top])son[s[top]][1]=i;
	s[++top]=i;
}

例题

洛谷 P3369 【模板】普通平衡树

你需要写一种数据结构，来维护一些数，并且提供以下操作：

1. 插入一个数 $x$。
2. 删除一个数 $x$（若有多个相同的数，应只删除一个）。
3. 定义排名为比当前数小的数的个数 $+1$。查询 $x$ 的排名。
4. 查询数据结构中排名为 $x$ 的数。
5. 求 $x$ 的前驱（前驱定义为小于 $x$，且最大的数）。
6. 求 $x$ 的后继（后继定义为大于 $x$，且最小的数）。

洛谷 P6136 【模板】普通平衡树（数据加强版）

您需要动态地维护一个可重集合 $M$，并且提供以下操作：

1. 向 $M$ 中插入一个数 $x$。
2. 从 $M$ 中删除一个数 $x$（若有多个相同的数，应只删除一个）。
3. 查询 $M$ 中有多少个数比 $x$ 小，并且将得到的答案加一。
4. 查询如果将 $M$ 从小到大排列后，排名位于第 $x$ 位的数。
5. 查询 $M$ 中 $x$ 的前驱（前驱定义为小于 $x$，且最大的数）。
6. 查询 $M$ 中 $x$ 的后继（后继定义为大于 $x$，且最小的数）。

本题强制在线，保证所有操作合法（操作 $2$ 保证存在至少一个 $x$，操作 $4,5,6$ 保证存在答案）。

洛谷 P5854 【模板】笛卡尔树

给定一个 $1 \sim n$ 的排列 $p$，构建其笛卡尔树。

即构建一棵二叉树，满足：

1. 每个节点的编号满足二叉搜索树的性质。
2. 节点 $i$ 的权值为 $p_i$，每个节点的权值满足小根堆的性质。