简介

建树

查找

算法实现

划分树是一种基于线段树的数据结构。主要用于快速求出(在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.