划分树是一种基于线段树的数据结构。主要用于快速求出（在log(n)的时间复杂度内）序列区间的第k大值。

查找整序列的第k大值往往采用。然而此方法会破坏原序列，并且需要O(n)的时间复杂度。抑或使用二叉平衡树进行维护，此方法每次查找时间复杂度仅为O(logn)。然而此方法丢失了原序列的顺序信息，无法查找出某区间内的第k大值。

划分树的基本思想就是对于某个区间，把它划分成两个子区间，左边区间的数小于右边区间的数。查找的时候通过记录进入左子树的数的个数，确定下一个查找区间，最后范围缩小到1，就找到了。

建树的过程比较简单，对于区间[l,r]，首先通过对原数组的排序找到这个区间的中位数a[mid]，小于a[mid]的数划入他的左子树[l,mid-1]，大于它的划入右子树[mid,r]。同时，对于第i个数，记录在[l,i]区间内有多少数被划入左子树。最后，对它的左子树区间[l,mid-1]和右子树区间[mid,r]递归的继续建树就可以了。

建树的时候要注意对于被分到同一子树的元素，元素间的相对位置不能改变。

查找的过程中主要问题就是确定将要查找的区间。这个问题有些麻烦。

先看一下查找过程tree_find.他的定义如下：

查找深度为h，在大区间[st,ed]中找小区间[s,e]中的第k元素。

再看看他是如何工作的。我们的想法是，先判断[s,e]中第k元素在[st,ed]的哪个子树中，然后找出对应的小区间和k，递归的进行查找，直到小区间的s=e为止。

那如何解决这个问题呢？这时候前面记录的进入左子树的元素个数就派上用场了。通过之前的记录可以知道，在区间[st,s-1]中有el[h,s-1]进入左子树，记它为l。同理区间[st,e]中有el[h,e]个数进去左子树，记它为r。所以，我们知道区间小区间[s,e]中有(r-l)个数进入左子树。那么如果(r-l) ≥k，那么就在左子树中继续查找，否则就在右子树中继续查找。

接着解决查找的小区间的问题。如果接下来要查找的是左子树，那么小区间应该是[st+([st,s-1]区间进入左子树的个数),st+([st,e]区间内进入左子树的个数)-1]，即区间[st+l,st+r-1]。显然，这里k不用变。

如果接下来要查找的是右子树，那么小区间应该是[mid+([st,s-1]区间中进入右子树的个数),mid+([st,e]区间进入右子树的个数)-1]。即区间[mid+(s-st-l),mid+(e-st-r)]。显然，这里k要减去区间里已经进入左子树的个数，即k变为k-(r-l)。于是递归继续查找直到s=e即可。

pascal源代码：

c++源代码