介绍
划分树，一种数据结构，和线段树很像，常用来解决求区间第 $ 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 $；
-
$ tr[lev][i] $ ：用于存储树的结构，第一维是级数（也就是现在递归到的层数），从 $ 0 $ 开始，第二维保存了当前层的元素（和上面说的一样），特殊的，当层数为 $ 0 $ 时，保存的是原序列（未排序的）；
-
$ tole[lev][i] $ ：表示在 $ [L, i] $ 这段区间中，被分到左子区间的数有多少（这是为了查询而维护的）。可以发现，这本质上是一个 $ DP $ 数组，可以用 $ DP $ 的思想去维护一下；
-
$ 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 $ 的值是否会改变；
- 递归到了左子区间；
设 $ [L, l - 1] $ 中放到左子区间的数的个数为 $ lef $，其值为 $ tole[lev][l - 1] $，那么现在我们的询问区间就变成了：
左端点：为 $ L + lef $；
右端点：为 $ L + lef + tolef - 1 $；
$ k $ 不变，直接递归即可；
- 递归到了右子区间；
$ 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;
}
感觉这东西貌似没啥用，但还是学了。。。