[数据结构] 划分树

介绍

划分树,一种数据结构,和线段树很像,常用来解决求区间第 $ k $ 小的问题,支持在线,但不支持修改,时间复杂度:建树 $ \Theta(n \log n) $ + 单次查询 $ \Theta(\log n) $,空间复杂度 $ \Theta(n \log n) $,在这种问题及其扩展问题上具有优良的性能,但其它问题就凸显出其局限性;

思想

划分树主体思想是快排 + 线段树,可以说把它俩揉一块就成了划分树;

类似线段树,划分树也是每次将区间分成左右两个子区间,这样就方便了我们递归求解;

划分树,顾名思义,就是把原序列不断划分的一种数据结构,对于其需要解决的求区间第 $ k $ 小的问题,它的解决方法是:对于每个树上的节点,存储其管辖范围内(不妨设为 $ [L, R] $)所有的元素,这些元素的特点是:顺序和原数组的输入顺序相同,但这些元素都出现在,且只能出现在原数组排好序后的 $ [L, R] $ 中(就是第 $ L $ 小到第 $ R $ 小);

这样就保证了不会更改原序列的位置,从而方便查询;

具体实现

需要维护的东西:

设当前节点所管辖的范围是 $ [L, R] $, $ mid = \lfloor \frac{L + R}{2} \rfloor $;

  1. $ tr[lev][i] $ :用于存储树的结构,第一维是级数(也就是现在递归到的层数),从 $ 0 $ 开始,第二维保存了当前层的元素(和上面说的一样),特殊的,当层数为 $ 0 $ 时,保存的是原序列(未排序的);

  2. $ tole[lev][i] $ :表示在 $ [L, i] $ 这段区间中,被分到左子区间的数有多少(这是为了查询而维护的)。可以发现,这本质上是一个 $ DP $ 数组,可以用 $ DP $ 的思想去维护一下;

  3. $ a[i] $ :表示原数组排好序的数组;

以这道题为例:POJ 2761 Feed the dogs

也可以从 $ Luogu $ 上找到(链接 $ from $ hzoi_ShadowLuogu P1533 可怜的狗狗

但貌似Luogu的题解区里很少有划分树的做法呢

求区间第 $ k $ 小;

首先,进行输入与排序;

cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> tr[0][i];
		a[i] = tr[0][i];
	}
	sort(a + 1, a + 1 + n);

然后是建树操作;

对于建树,根据前面的思想,我们要让左子区间的所有数非严格小于右子区间的所有数,显然我们要让小于中位数的数去左区间,大于中位数的数去右区间,对于中位数本身,我们根据左子区间的区间长度以及现有的数的个数分类讨论;

怎样找中位数呢?

别忘了我们有一个排好序的数组 $ a $,那么中位数其实就是 $ a[mid] $;

有了这些,建树就好办了;

对于具体过程,我们可以从左到右扫一遍整个区间,如有小于中位数的,下放到左子区间,同时更新 $ tole $ 数组($ tole[lev][i]++ $) ,大于中位数的,下放到右子区间,等于中位数的,判断一下左子区间还有没有位置,如有,则放到左子区间,否则放到右子区间;

最后如果到叶子节点,回溯即可;

完事,时间复杂度 $ T(n) = 2T( \frac{n}{2} ) + \Theta(n) = \Theta(n \log n) $ (貌似是这么分析,今天刚跟学长学的。。。)

建树部分的代码:

void bt(int lev, int l, int r) {
	if (l == r) return;
	int mid = (l + r) >> 1;
	int midl = mid - l + 1; //代表现在左子区间还有多少空位置能放数,初始化为左子区间长度;
	for (int i = l; i <= r; i++) {
		if (tr[lev][i] < a[mid]) midl--;
	}
	int subl = l;
	int subr = mid + 1;
	for (int i = l; i <= r; i++) {
		if (i == l) tole[lev][i] = 0;
		else tole[lev][i] = tole[lev][i - 1]; //继承上一步的结果;
		if (tr[lev][i] < a[mid] || tr[lev][i] == a[mid] && midl > 0) {
			tr[lev + 1][subl++] = tr[lev][i]; //给左子区间;
			tole[lev][i]++;
			if (tr[lev][i] == a[mid]) midl--;
		} else {
			tr[lev + 1][subr++] = tr[lev][i]; //给右子区间;
		}
	}
	bt(lev + 1, l, mid);
	bt(lev + 1, mid + 1, r);
}

然后是查询操作;

设查询的区间为 $ [l, r] $;

对于查询,采用递归,如果 $ k $ 在左子区间,则递归左子区间,否则递归右子区间,最后到叶子节点返回答案;

这时候,我们维护的 $ tole $ 数组就派上用场了;

具体地,在当前节点时,我们要判断下一步到底是递归左边还是右边,那么我们就判断 $ tole[lev][r] - tole[lev][l - 1] $ (其实就是 $ [l, r] $ 中被分到左子区间的元素个数,不妨记为 $ tolef $)与 $ k $ 的大小关系,若后者比前者大,则递归右区间,否则递归左区间;

明确了递归区间后,我们要考虑询问区间和 $ k $ 的值是否会改变;

  1. 递归到了左子区间;

设 $ [L, l - 1] $ 中放到左子区间的数的个数为 $ lef $,其值为 $ tole[lev][l - 1] $,那么现在我们的询问区间就变成了:

左端点:为 $ L + lef $;

右端点:为 $ L + lef + tolef - 1 $;

$ k $ 不变,直接递归即可;

  1. 递归到了右子区间;

$ lef $ 和 $ tolef $ 的定义不变,那么现在我们的询问区间就变成了:

左端点:为 $ mid + 1 $ + $ [L, l - 1] $ 中进入右子区间的数的个数;

$ [L, l - 1] $ 中进入右子区间的数的个数为这段区间的长度 - 进入左子区间的数的个数,即为 $ l - 1 - L + 1 - lef = l - L - lef $;

所以左端点即为:$ mid + l - L - lef + 1 $;

右端点:为 $ mid + 1 $ + $ [L, r] $ 中进入右子区间的数的个数 - $ 1 $;

$ [L, r] $ 中进入右子区间的数的个数为这段区间的长度 - 进入左子区间的数的个数,即为 $ r - L + 1 - lef - tolef $;

所以右端点即为:$ mid + r - L - lef - tolef + 1 $;

此时 $ k $ 变成了 $ k - tolef $,然后递归即可;

这样,查询就完事了;

int ask(int lev, int l, int r, int L, int R, int k) { //定义和上面写的一样;
	if (l == r) return tr[lev][l];
	int mid = (L + R) >> 1;
	int lef, tolef;
	if (l == L) {
		lef = 0;
		tolef = tole[lev][r];
	} else {
		lef = tole[lev][l - 1];
		tolef = tole[lev][r] - lef;
	}
	if (k <= tolef) {
		int newl = L + lef;
		int newr = L + lef + tolef - 1;
		return ask(lev + 1, newl, newr, L, mid, k);
	} else {
		int newl = mid + l - L - lef + 1;
		int newr = mid + r - L + 1 - lef - tolef;
		return ask(lev + 1, newl, newr, mid + 1, R, k - tolef);
	}
}

解决这道题的代码:

点击查看代码
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n, m;
int tr[35][200005];
int tole[35][200005];
int a[200005];
namespace divtr{
	void bt(int lev, int l, int r) {
		if (l == r) return;
		int mid = (l + r) >> 1;
		int midl = mid - l + 1;
		for (int i = l; i <= r; i++) {
			if (tr[lev][i] < a[mid]) midl--;
		}
		int subl = l;
		int subr = mid + 1;
		for (int i = l; i <= r; i++) {
			if (i == l) tole[lev][i] = 0;
			else tole[lev][i] = tole[lev][i - 1];
			if (tr[lev][i] < a[mid] || tr[lev][i] == a[mid] && midl > 0) {
				tr[lev + 1][subl++] = tr[lev][i];
				tole[lev][i]++;
				if (tr[lev][i] == a[mid]) midl--;
			} else {
				tr[lev + 1][subr++] = tr[lev][i];
			}
		}
		bt(lev + 1, l, mid);
		bt(lev + 1, mid + 1, r);
	}
	int ask(int lev, int l, int r, int L, int R, int k) {
		if (l == r) return tr[lev][l];
		int mid = (L + R) >> 1;
		int lef, tolef;
		if (l == L) {
			lef = 0;
			tolef = tole[lev][r];
		} else {
			lef = tole[lev][l - 1];
			tolef = tole[lev][r] - lef;
		}
		if (k <= tolef) {
			int newl = L + lef;
			int newr = L + lef + tolef - 1;
			return ask(lev + 1, newl, newr, L, mid, k);
		} else {
			int newl = mid + l - L - lef + 1;
			int newr = mid + r - L + 1 - lef - tolef;
			return ask(lev + 1, newl, newr, mid + 1, R, k - tolef);
		}
	}
}
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> tr[0][i];
		a[i] = tr[0][i];
	}
	sort(a + 1, a + 1 + n);
	divtr::bt(0, 1, n);
	int l, r, k;
	for (int i = 1; i <= m; i++) {
		cin >> l >> r >> k;
		cout << divtr::ask(0, l, r, 1, n, k) << endl;
	}
	return 0;
}

感觉这东西貌似没啥用,但还是学了。。。

热门相关:医门宗师   超级英雄   美女总裁之贴身高手   强宠头号鲜妻:陆少,滚!   都市之九天大帝