劃分樹是一種基於線段樹的數據結構。主要用於快速求出（在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.
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;
}
