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