划分树 Partition Tree

http://baike.baidu.com/view/4199603.htm
划分树是一种基于线段树的数据结构。主要用于快速求出(在log(n)的时间复杂度内）序列区间的第k大值。
http://yueyue1105.blog.163.com/blog/static/431117682010716111425892/
同样以1 5 2 6 3 7为例：
根据中位数mid，将区间划分成左子树中的数小于等于mid，右子树中的数大于等于mid，得到这样一棵划分树：
        [1 5 2 6 3 7]
     [1 2 3]      [5 6 7]
   [1 2]  [3]    [5 6] [7]
  [1] [2]        [5] [6] 
注意要保持下标的先后顺序不变
对每一个区间，用sum[i]记录区间的左端点left到i有几个进入了左子树，即有几个数小于等于mid
用对应的下标区间建线段树：（这里下标区间对应的是排序后的数列）
            [1 6]
     [1 3]      [4 6]
  [1 2] [3]   [4 5][6]
  [1][2]      [4][5]
每次查找[l r]区间的第k大数时，先查看当前区间[left right]下的sum[r] - sum[l - 1]是否小于等于k，如果是，则递归到左子树，并继续在[left + sum[l - 1], left + sum[r] - 1]中找第k大数；
否则，进入右子树，继续在[mid + l - left + 1 - sum[l - 1], mid + r - left + 1 - sum[r]]找第k - sum[r] + sum[l - 1]大数
这样一次查询只要logn的复杂度

对于建划分树的方法，我一开始是先建完一层，再往下递归，过了PKU2104后，交HDU2665WA，后来发现对于0 0 -1这样的数据，下一层本应该是-1 0 0，而我的程序还是0 0 -1，原因就是会有很多相同的元素等于mid。于是我就找什么是唯一的，很容易想到数组的下标，仔细观察，如果从划分树叶子回溯，相当于在对数组下标进行归并排序，于是我的问题就解决了~
http://java-mans.iteye.com/blog/1644583

归并树是在建树的过程中保存归并排序。

划分树是在建树的过程中保存快速排序。

其中归并树适合解决一个数在某个区间的名次。

划分树适合解决某个区间的K大数。

POJ这题是找K大数，归并树也可做，二分答案，再由归并树找出这个数的名次。划分树更快。

1. struct Node{  
2.     int left,right,mid;  
3. }tree[N*4];  
4. int sa[N],num[20][N],cnt[20][N]; //sa中是排序后的，num记录每一层的排序结果，cnt[deep][i]表示第deep层，前i个数中有多少个进入左子树  
5. int n,q;  
6. void debug(int d){  
7.     for(int i=1;i<=n;i++)  
8.         printf("%d ",num[d][i]);  
9.     printf("\n");  
10. }  
11. void bulid(int step,int l,int r,int deep){  
12.     tree[step].left=l;  
13.     tree[step].right=r;  
14.     tree[step].mid=(l+r)>>1;  
15.     if(l==r)  
16.         return;  
17.     int mid=(l+r)>>1;  
18.     int mid_val=sa[mid],lsum=mid-l+1;;  
19.     for(int i=l;i<=r;i++)  
20.         if(num[deep][i]<mid_val)  
21.             lsum--;    //lsum表示左子树中还需要多少个中值  
22.     int L=l,R=mid+1;  
23.     for(int i=l;i<=r;i++){  
24.         if(i==l)  
25.             cnt[deep][i]=0;  
26.         else  
27.             cnt[deep][i]=cnt[deep][i-1];  
28.         if(num[deep][i]<mid_val||(num[deep][i]==mid_val&&lsum>0)){  //左子树  
29.             num[deep+1][L++]=num[deep][i];  
30.             cnt[deep][i]++;  
31.             if(num[deep][i]==mid_val)  
32.                 lsum--;  
33.         }  
34.         else  
35.             num[deep+1][R++]=num[deep][i];  
36.     }  
37. //  debug(deep);  
38.     bulid(2*step,l,mid,deep+1);  
39.     bulid(2*step+1,mid+1,r,deep+1);  
40. }  
41. int query(int step,int l,int r,int k,int deep){  
42.     if(l==r)  
43.         return num[deep][l];  
44.     int s1,s2;   //s1为[tree[step].left,l-1]中分到左子树的个数  
45.     if(tree[step].left==l)  
46.         s1=0;  
47.     else  
48.         s1=cnt[deep][l-1];  
49.     s2=cnt[deep][r]-s1;   //s2为[l,r]中分到左子树的个数  
50.     if(k<=s2)   //左子树的数量大于k,递归左子树  
51.         return query(2*step,tree[step].left+s1,tree[step].left+s1+s2-1,k,deep+1);  
52.     int b1=l-1-tree[step].left+1-s1;  //b1为[tree[step].left,l-1]中分到右子树的个数  
53.     int b2=r-l+1-s2;   //b2为[l,r]中分到右子树的个数  
54.     return query(2*step+1,tree[step].mid+1+b1,tree[step].mid+1+b1+b2-1,k-s2,deep+1);  
55. }  
56. int main(){;  
57.     while(scanf("%d%d",&n,&q)!=EOF){          
58.         for(int i=1;i<=n;i++){  
59.             scanf("%d",&num[1][i]);  
60.             sa[i]=num[1][i];  
61.         }  
62.         sort(sa+1,sa+n+1);  
63.         bulid(1,1,n,1);  
64.         while(q--){  
65.             int l,r,k;  
66.             scanf("%d%d%d",&l,&r,&k);  
67.             printf("%d\n",query(1,l,r,k,1));  
68.         }  
69.     }  
70.     return 0;  
71. } 

http://sbp810050504.blog.51cto.com/2799422/1008930

https://github.com/zsc1993916/AcmTemplate/blob/master/Datastructure/%E5%88%92%E5%88%86%E6%A0%91%E6%B1%82%E5%8C%BA%E9%97%B4k%E5%A4%A7%E6%95%B0.cpp

http://java-mans.iteye.com/blog/1644582