簡介
查找整序列的第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原始碼：
c++原始碼
