划分树
划分树
划分树是一种基于线段树的数据结构。主要用于快速求出(在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源代码：
const
maxn=100000;
type
rec=record
mid,left,right:longint;
end;
var
n,m,lt,rt:Longint;
b:array [0..maxn+10] of longint;
tree:array [0..maxn*5] of rec;
lnum:array [0..20,0..maxn+10] of longint;
g:array [0..20,0..maxn+10] of longint;
procedure init;
var i:longint;
begin
readln(n,m);
for I:=1 to n do
begin
read(g[0,i]);
b[i]:=g[0,i];
end;
end;
procedure qsort(l,r:longint);
var i,j,k:Longint;
begin
if l>=r then exit;
i:=l; j:=r; k:=b[random(r-l+1)+l];
repeat
while k>b[i] do inc(i);
while k<b[j] do dec(j);
if i<=j
then begin
b[0]:=b[i]; b[i]:=b[j]; b[j]:=b[0];
inc(i); dec(j);
end;
until i>j;
qsort(l,j);
qsort(i,r);
end;
procedure setup(x,l,r,dep:longint);
var i:Longint;
begin
with tree[x] do
begin
left:=l; right:=r; mid:=(l+r) div 2;
if l=r then exit;
lt:=l-1; rt:=mid;
for i:=l to r do
if (g[dep-1,i]<=b[mid]) and (lt<mid)
then begin
inc(lt); g[dep,lt]:=g[dep-1,i];
if i-1<l
then lnum[dep,i]:=1
else lnum[dep,i]:=lnum[dep,i-1]+1;
end
else begin
inc(rt); g[dep,rt]:=g[dep-1,i];
if i-1<l
then lnum[dep,i]:=0
else lnum[dep,i]:=lnum[dep,i-1];
end;
setup(x*2,l,mid,dep+1);
setup(x*2+1,mid+1,r,dep+1);
end;
end;
function find(x,l,r,kth,dep:longint):longint;
var tlnum,t1,t2,ll,rr:longint;
begin
if (l=tree[x].left) and (r=tree[x].right)
then begin
find:=b[l-1+kth];
exit;
end;
t1:=lnum[dep,r];
if l-1<tree[x].left then t2:=0 else t2:=lnum[dep,l-1];
tlnum:=t1-t2;
if kth<=tlnum
then begin
ll:=tree[x].left+t2;
rr:=ll+tlnum-1;
find:=find(x*2,ll,rr,kth,dep+1)
end
else begin
ll:=tree[x].mid+1+l-tree[x].left-t2;
rr:=ll+r-l-tlnum;
find:=find(x*2+1,ll,rr,kth-tlnum,dep+1);
end;
end;
procedure main;
var i,x,y,z:Longint;
begin
for i:=1 to m do
begin
readln(x,y,z);
writeln(find(1,x,y,z,1));
end;
end;
begin
assign(input,inf); reset(input);
assign(output,ouf); rewrite(output);
init;
randomize;
qsort(1,n);
setup(1,1,n,1);
main;
close(input); close(output);
end.