複製鏈接
請複製以下鏈接發送給好友
https://baike.baidu.hk/item/劃分樹/10600781
複製
複製成功

劃分樹

鎖定
劃分樹是一種基於線段樹的數據結構。主要用於快速求出（在log(n)的時間複雜度內）序列區間的第k大值。
中文名
劃分樹
性    質
數據結構
前    身
線段樹
應    用
快速查找法

目錄

  1. 1 簡介
  2. 2 建樹
  3. 3 查找
  4. 4 算法實現

劃分樹簡介

查找整序列的第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; 
}