划分树详解 结合例题hdu4251

参考博客：

http://www.notonlysuccess.com/index.php/divide-tree/#more-142

http://blog.csdn.net/fp_hzq/article/details/7993364

http://www.cnblogs.com/pony1993/archive/2012/07/17/2594544.html

本文出自 “每天进步一点点” 博客，请务必保留此出处http://sbp810050504.blog.51cto.com/2799422/1008930

用划分树来解决选定区间内的第K大值，其实也就两步！一步是建树，另一步则是查询。

先说我对建树的理解吧！

建树的过程很简单：两步就OK了！

第一步：找到序列的中位数，把大于中位数的扔到中位数的左边，小于中位数的扔到数的右边。这样整个序列就被分成了两个区间。

第二步：对每个子区间，也分别执行第一步操作，直到序列中只有一个元素为止。

可以看出，建树是一个递归的过程，与线段树的建树有相似之处。

划分树的建树需要注意以下几点：

第一：建树是分层的，所以代码中用的是二维数组tree[20][M]。一般10W级别的数据，20层已经够了。

第二：建树划分的标准是中位数，所以需要排序。而且只排一次序就OK了，为什么只排一次就OK了，我很久都没明白这一点。其实是这样的：对于任意序列： 划分后，左边的数据永远不会大于右边的数据。那么对左边数据单独排序与整体排序的结果是一样的，所以排一次序就OK了！

第三：划分树划分好的数据永远在存放在下一层。比如数据：

tree[0][M]=1 5 2 6 3 7 4

排序后为：1 2 3 4 5 6 7

中位数为：4

划分后的结果为：tree[1][M]=1 2 3 4 5 6 7(这组数据有点特殊，划分后来就已经是排好序的了)红黑色字体都仍按原未排顺序排列

（红色表示划分到中位数的左边，黑色表示划分到中位数的右边）

接着划分：tree[2][M]=1 2 3 4 5 6 7

再接着分：tree[3][M]=1 2 3 4 5 6 0

到这里已经分完了，为什么最后是0呢？在第2层（tree[2][M]）,7已经分完了，所以不用再分

第四：划分到最后，实际上已经对序列进行排序了。

划分的时候还有一点需要处理：如果有多个数据相同怎么办呢？通过一种特殊的处理：尽量使左右两边平均分配相同的数。这个特殊处理是这样的：

在没分之前，先假设中位数左边的数据suppose都已经分到左边了，所以suppose=mid-left+1;然后如果真的分在左边，即if(tree[level][i]<sorted[mid])

suppose--；suppose就减一！到最后，如果suppos=1，则说明中位数左边的数都小于中位数，如果有等于中位数的，则suppose大于1。

最后分配的时候，把suppose个数，分到左边就可以了，剩下的分到右边！因为suppose的初值是mid-left+1,这样就能保证中位数左边和右边的数平衡了！

第五：划分的过程，需要把每层的数据记录：toLeft[20][M]。toLeft[i][j]定义为：第i层[1,j]之间有多

Problem DescriptionInputOutputSample InputSample Output//在[left,right]数据中查询[qleft,qright]中第k大的数据int query(int level,int left,int right,int qleft,int qright,int k){    //在大区间内查询小区间的第k大的数    if( qleft==qright)        return tree[level][qleft];    int s;//代表[left,qleft)之间有多个个元素被分到左边    int ss;//[qleft, qright]内将被划分到左子树的元素数目    int mid=(left+right)>>1;    if(left==qleft){        s=0;        ss=toLeft[level][qright];    }else{        s=toLeft[level][qleft-1];        ss=toLeft[level][qright]-s;    }    int newl,newr;    if(k<=ss){//查询左边  缩小小区间继续在本区间查找第k个不用改变k的大小        newl=left+s;        newr=left+s+ss-1;        return query(level+1,left,mid,newl,newr,k);    }else{//查询右边 显然这里k要减去区间里已经进入左子树的个数ss        newl=mid-left+1+qleft-s;        newr=mid-left+1+qright-s-ss;        return query(level+1,mid+1,right,newl, newr,k-ss);    }}