Java教程

数据结构专题-专项训练：平衡树

本文主要是介绍数据结构专题-专项训练：平衡树，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

@

目录
  • 1. 回顾
  • 2. 例题
  • 3. 总结

1. 回顾

在这两篇博文中：

  1. 平衡树算法总结&专题训练1（无旋平衡树：替罪羊树，FHQ Treap）
  2. 平衡树算法总结&专题训练2（有旋平衡树：AVL 树，Splay）

我们重点学习了 4 种平衡树。

当然考虑到在 OI 的实用性以及思维性，我个人认为：

  1. FHQ Treap 和 Splay 一定要掌握！
  2. 替罪羊树的思想也非常重要，在某些题目当中有重大的作用。
  3. AVL 树......其实在 OI 中不学也没有多大问题。

那么接下来我们看几道例题，看看平衡树在实战中的应用。

2. 例题

题单：

  • P3850 [TJOI2007]书架
  • P1486 [NOI2004] 郁闷的出纳员
  • P2234 [HNOI2002]营业额统计

P3850 [TJOI2007]书架

FHQ Treap 按照大小分裂的模板题，直接做就可以了。

更具体的，在第 \(i\) 个位置插入字符串 \(s\) 的时候，我们将树按照 \(i - 1\) 的大小分裂，然后合并即可。

查询？也差不多。

代码：

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int MAXN = 2e5 + 10;
int n, m, cnt, root, q;
struct node
{
	string val;
	int l, r, key, size;
}tree[MAXN];

int read()
{
	int sum = 0, fh = 1; char ch = getchar();
	while (ch < '0' || ch > '9') {if (ch == '-') fh = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {sum = (sum << 3) + (sum << 1) + (ch ^ 48); ch = getchar();}
	return sum * fh;
}

void update(int now) {tree[now].size = tree[tree[now].l].size + tree[tree[now].r].size + 1;}
int Make_Node(string val)
{
	int now = ++cnt; tree[cnt].val = val;
	tree[cnt].key = rand(); tree[cnt].size = 1;
	return now;
}

void split(int now, int val, int &x, int &y)
{
	if (now == 0) x = y = 0;
	else
	{
		if (tree[tree[now].l].size < val)
		{
			x = now;
			split(tree[now].r, val - tree[tree[now].l].size - 1, tree[now].r, y);
		}
		else
		{
			y = now;
			split(tree[now].l, val, x, tree[now].l);
		}
		update(now);
	}
}

int merge(int x, int y)
{
	if (!x || !y) return x + y;
	if (tree[x].key < tree[y].key)
	{
		tree[x].r = merge(tree[x].r, y);
		update(x); return x;
	}
	else
	{
		tree[y].l = merge(x, tree[y].l);
		update(y); return y;
	}
}

void Insert(int pos, string val)
{
	int x, y;
	split(root, pos - 1, x, y);
	root = merge(merge(x, Make_Node(val)), y);
}

string ask(int pos)
{
	int x, y, z;
	split(root, pos, y, z);
	split(y, pos - 1, x, y);
	string str = tree[y].val;
	root = merge(merge(x, y), z);
	return str;
}

int main()
{
	srand(time(0));
	n = read();
	for (int i = 1; i <= n; ++i)
	{
		string str; cin >> str;
		Insert(i, str);
	}
	m = read();
	for (int i = 1; i <= m; ++i)
	{
		string str; int pos;
		cin >> str; pos = read();
		Insert(pos + 1, str);
	}
	q = read();
	for (int i = 1; i <= q; ++i)
	{
		int pos = read();
		cout << ask(pos + 1) << "\n";
	}
	return 0;
}

P1486 [NOI2004] 郁闷的出纳员

这道题我们首先需要记录工资变化量 \(delta\)。

使用 FHQ Treap。

插入操作：

老生常谈，注意初始工资要减去 \(delta\)，然后插入。不要忘记特判。

加减工资：

直接修改 \(delta\) 即可。

找第 \(k\) 大：

老生常谈。注意可能第 \(k\) 大不存在。

注意：在每一次操作后，我们都需要将工资小于 \(min - delta\)（\(min\) 为初始工资下界）的人删除，这个直接 FHQ Treap 分裂出来舍弃掉就好了。

代码：

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 3e5 + 10;
int n, minn, cnt, root, ans, delta;
struct node
{
	int l, r, val, size, key;
}tree[MAXN];

int read()
{
	int sum = 0, fh = 1; char ch = getchar();
	while (ch < '0' || ch > '9') {if (ch == '-') fh = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {sum = (sum << 3) + (sum << 1) + (ch ^ 48); ch = getchar();}
	return sum * fh;
}

int Make_Node(int val)
{
	++cnt; tree[cnt].val = val;
	tree[cnt].size = 1;
	tree[cnt].key = rand();
	return cnt;
}

void update(int now) {tree[now].size = tree[tree[now].l].size + tree[tree[now].r].size + 1;}

void split(int now, int val, int &x, int &y)
{
	if (!now) x = y = 0;
	else
	{
		if (tree[now].val <= val)
		{
			x = now;
			split(tree[now].r, val, tree[now].r, y);
		}
		else
		{
			y = now;
			split(tree[now].l, val, x, tree[now].l);
		}
		update(now);
	}
}

int merge(int x, int y)
{
	if (!x || !y) return x + y;
	else
	{
		if (tree[x].key > tree[y].key)
		{
			tree[x].r = merge(tree[x].r, y);
			update(x); return x;
		}
		else
		{
			tree[y].l = merge(x, tree[y].l);
			update(y); return y;
		}
	}
}

void Insert(int val)
{
	int x, y; split(root, val, x, y);
	root = merge(merge(x, Make_Node(val)), y);
}

void Find_kth(int val)
{
	int now = root;
	while (now)
	{
		if (tree[tree[now].r].size + 1 == val) break;
		if (tree[tree[now].r].size >= val) now = tree[now].r;
		else {val -= tree[tree[now].r].size + 1; now = tree[now].l;}
	}
	printf("%d\n", tree[now].val + delta);
}

void deal(int val)
{
	int x, y; split(root, val - 1, x, y);
	ans += tree[x].size;
	root = y;
}

int main()
{
	srand(time(0));
	n = read(); minn = read();
	for (int i = 1; i <= n; ++i)
	{
		char ch; cin >> ch;
		int k = read();
		switch(ch)
		{
			case 'I':
				if (k < minn) break;
				Insert(k - delta); break;
			case 'A':
				delta += k; break;
			case 'S':
				delta -= k; break;
			case 'F':
				if (k > cnt - ans) printf("-1\n");
				else Find_kth(k);
				break;
		}
		deal(minn - delta);
	}
	printf("%d\n", ans);
	return 0;
}

P2234 [HNOI2002]营业额统计

更简单。直接找前驱就可以了。

特别需要注意第一天的最小波动值！

还要注意没有前驱的数！

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int MAXN = 32767 + 10;
int n, cnt, root;
LL ans;
struct node
{
	int l, r, size, val, key;
}tree[MAXN];

LL read()
{
	LL sum = 0, fh = 1; char ch = getchar();
	while (ch < '0' || ch > '9') {if (ch == '-') fh = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {sum = (sum << 3) + (sum << 1) + (ch ^ 48); ch = getchar();}
	return sum * fh;
}

int Make_Node(int val)
{
	++cnt;
	tree[cnt].size = 1;
	tree[cnt].val = val;
	tree[cnt].key = rand();
	return cnt;
}

void update(int now) {tree[now].size = tree[tree[now].l].size + tree[tree[now].r].size + 1;}

void split(int now, int val, int &x, int &y)
{
	if (!now) x = y = 0;
	else
	{
		if (tree[now].val <= val) {x = now; split(tree[now].r, val, tree[now].r, y);}
		else {y = now; split(tree[now].l, val, x, tree[now].l);}
		update(now);
	}
}

int merge(int x, int y)
{
	if (!x || !y) return x + y;
	if (tree[x].key > tree[y].key)
	{
		tree[x].r = merge(tree[x].r, y);
		update(x); return x;
	}
	else
	{
		tree[y].l = merge(x, tree[y].l);
		update(y); return y;
	}
}

void Insert(int val)
{
	int x, y; split(root, val, x, y);
	root = merge(merge(x, Make_Node(val)), y);
}

int main()
{
	srand(time(0));
	n = read(); int t = read();
	ans = t; Insert(t);
	for (int i = 2; i <= n; ++i)
	{
		t = read();
		Insert(t);
		int x, y, z, sum = 0x7f7f7f7f;
		split(root, t - 1, x, y);
		split(y, t, y, z);
		if (tree[y].size > 1) {root = merge(merge(x, y), z); continue;}
		else
		{
			if (x != 0)
			{
				int now = x;
				while (tree[now].r) now = tree[now].r;
				sum = min(sum, abs(tree[now].val - t));
			}
			if (z != 0)
			{
				int now = z;
				while (tree[now].l) now = tree[now].l;
				sum = min(sum, abs(tree[now].val - t));
			}
		}
		ans += sum;
		root = merge(merge(x, y), z);
	}
	printf("%lld\n", ans);
	return 0;
}

3. 总结

或许您已经发现了，这几道题都是针对单点操作的。

的确，平衡树的入门题都是针对单点操作，而后面的题目涉及到区间操作时就要使用线段树的 lazy_tag-懒标记 思想了。

具体后面再看。

为什么都是 FHQ Treap？因为它码量短啊。

当然区间问题 Splay 有时会表现得更好。

这篇关于数据结构专题-专项训练：平衡树的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航