跳到主要内容

二叉搜索树 & 平衡树

参考资料​

__gnu_pbds::tree​

#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;

笛卡尔树​

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 【模板】普通平衡树​

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

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

  1. 插入一个数 xx。
  2. 删除一个数 xx（若有多个相同的数，应只删除一个）。
  3. 定义排名为比当前数小的数的个数 +1+1。查询 xx 的排名。
  4. 查询数据结构中排名为 xx 的数。
  5. 求 xx 的前驱（前驱定义为小于 xx，且最大的数）。
  6. 求 xx 的后继（后继定义为大于 xx，且最小的数）。
代码（1）
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;

tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update> T;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin>>n;
	int cnt=0;
	while(n--)
	{
		int op,x;
		cin>>op>>x;
		if(op==1)T.insert({x,++cnt});
		else if(op==2)T.erase(T.lower_bound({x,0}));
		else if(op==3)cout<<T.order_of_key({x,0})+1<<'\n';
		else if(op==4)cout<<T.find_by_order(x-1)->first<<'\n';
		else if(op==5)cout<<prev(T.lower_bound({x,0}))->first<<'\n';
		else if(op==6)cout<<T.lower_bound({x+1,0})->first<<'\n';
	}
	return 0;
}

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

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

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

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

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

代码（1）
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;

tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update> T;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		T.insert({x,++cnt});
	}
	int ans=0,last=0;
	while(m--)
	{
		int op,x;
		cin>>op>>x;
		x^=last;
		if(op==1)T.insert({x,++cnt});
		if(op==2)T.erase(T.lower_bound({x,0}));
		if(op==3)ans^=last=T.order_of_key({x,0})+1;
		if(op==4)ans^=last=T.find_by_order(x-1)->first;
		if(op==5)ans^=last=prev(T.lower_bound({x,0}))->first;
		if(op==6)ans^=last=T.lower_bound({x+1,0})->first;
	}
	cout<<ans<<'\n';
	return 0;
}

洛谷 P5854 【模板】笛卡尔树​

洛谷 P5854 【模板】笛卡尔树

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

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

  1. 每个节点的编号满足二叉搜索树的性质。
  2. 节点 ii 的权值为 pip_i，每个节点的权值满足小根堆的性质。
代码（1）
#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=10000005;
int a[N],s[N],son[N][2];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	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;
	}
	ll ans1=0,ans2=0;
	for(int i=1;i<=n;i++)
	{
		ans1^=i*(son[i][0]+1ll);
		ans2^=i*(son[i][1]+1ll);
	}
	cout<<ans1<<' '<<ans2<<'\n';
	return 0;
}