查找整序列的第k大值往往采用快速查找法。然而此方法会破坏原序列，并且需要O(n)的时间复杂度。抑或使用二叉平衡树进行维护，此方法每次查找时间复杂度仅为O(logn)。然而此方法丢失了原序列的顺序信息，无法查找出某区间内的第k大值。
划分树的基本思想就是对于某个区间，把它划分成两个子区间，左边区间的数小于右边区间的数。查找的时候通过记录进入左子树的数的个数，确定下一个查找区间，最后范围缩小到1，就找到了。
划分树
百科内容来自于：
简介
建树
查找
查找的过程中主要问题就是确定将要查找的区间。这个问题有些麻烦。
先看一下查找过程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.
c++源代码
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 100500
#define MID ((l+r)>>1)
int a[N],s[N],t[20][N],num[20][N],n,m;
void Build(int c,int l,int r)
{
int lm=MID-l+1,lp=l,rp=MID+1;
for(int i=l;i<=MID;i++)
lm-=s[i]<s[MID];
for(int i=l;i<=r;i++)
{
if( i==l )
num[c][i]=0;
else
num[c][i]=num[c][i-1];
if( t[c][i]==s[MID] )
{
if( lm )
{
lm--;
num[c][i]++;
t[c+1][lp++]=t[c][i];
}
else
t[c+1][rp++]=t[c][i];
}
else if( t[c][i]<s[MID] )
{
num[c][i]++;
t[c+1][lp++]=t[c][i];
}
else
t[c+1][rp++]=t[c][i];
}
if( l<r )
Build(c+1,l,MID),Build(c+1,MID+1,r);
}
int Query(int c,int l,int r,int ql,int qr,int k)
{
if( l==r )
return t[c][l];
int s,ss;
if( l==ql )
s=0,ss=num[c][qr];
else
s=num[c][ql-1],ss=num[c][qr]-num[c][ql-1];
if( k<=ss )
return Query(c+1,l,MID,l+s,l+s+ss-1,k);
else
return Query(c+1,MID+1,r,MID+1+ql-l-s,MID+1+qr-l-s-ss,k-ss);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
s[i]=t[0][i]=a[i];
}
sort(s+1,s+1+n);
Build(0,1,n);
while( m-- )
{
int l,r,k;
scanf("%d%d%d",&l,&r,&k);
printf("%d\n",Query(0,1,n,l,r,k));
}
return 0;
}
$firstVoiceSent
- 来自原声例句