瓜瓜头条

[数据结构] 划分树

2024-08-09 11:11 由 Peppa_Even_Pig 发表于 #其他

介绍

划分树，一种数据结构，和线段树很像，常用来解决求区间第 $ 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_Shadow） Luogu 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;
}

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

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