您的位置: 首页  >  文章  >  划分树讲解

划分树讲解

分类: 文章 • 2024-11-30 15:45:28

搜索关于划分树的讲解，竟然搜到了郑大媛学姐的博文，不是这篇

原博文有错误，我就不给出原链接了

划分树讲解

用划分树来解决选定区间内的第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层[l,j]之间有多个数据被分到了左边（注意这里用的是闭区间）

模板：

[cpp] view plain copy
 print?
  1. #include<stdio.h>    
  2. #include<algorithm>    
  3. using namespace std;    
  4. #define M 100005    
  5. int tree[20][M],sorted[M];    
  6. int toLeft[20][M];    
  7. void build(int level,int left,int right){    
  8.     if(left==right)return ;    
  9.     int mid=(left+right)>>1;    
  10.     int i;        
  11.     int suppose;//假设在中位数sorted[mid]左边的数都全部小于sorted[mid]    
  12.     suppose=mid-left+1;    
  13.     for(i=left;i<=right;i++){    
  14.         if(tree[level][i]<sorted[mid]){    
  15.             suppose--;    
  16.         }    
  17.     }    
  18. /*如果suppose==1，则说明数组中值为sorted[mid]只有一个数。 
  19.     比如序列：1 3 4 5 6，sorted[mid]=4   
  20. */   
  21. /*如果suppose>1，则说明数组中左半边值为sorted[mid]的不止一个数,为mid-suppose。 
  22.     比如序列：1 4 4 4 6，sorted[mid]=4  
  23. */    
  24.     int lpos=left,rpos=mid+1;    
  25.     for(i=left;i<=right;i++){    
  26.         if(i==left){//这里是预处理，相当与初始化    
  27.             toLeft[level][i]=0;    
  28.         }  
  29.         else{    
  30.             toLeft[level][i]=toLeft[level][i-1];    
  31.         }    
  32.         if(tree[level][i]<sorted[mid]){//划分到中位数左边    
  33.             toLeft[level][i]++;    
  34.             tree[level+1][lpos++]=tree[level][i];    
  35.         }  
  36.         else if(tree[level][i]>sorted[mid]){//划分到中位数右边    
  37.             tree[level+1][rpos++]=tree[level][i];    
  38.         }  
  39.         else{//这里，suppose大于0的数划分到中位数的左边    
  40.             if(suppose!=0){//这里的处理太巧妙了！帅气！    
  41.                 suppose--;    
  42.                 toLeft[level][i]++;    
  43.                 tree[level+1][lpos++]=tree[level][i];    
  44.             }  
  45.             else{//表示    
  46.                 tree[level+1][rpos++]=tree[level][i];    
  47.             }    
  48.         }    
  49.     }    
  50.     build(level+1,left,mid);    
  51.     build(level+1,mid+1,right);    
  52. }    
  53. //在[left,right]数据中查询[qleft,qright]中第k大的数据    
  54. int query(int level,int left,int right,int qleft,int qright,int k){    
  55.     if( left==right)    
  56.         return tree[level][left];    
  57.     int s;//代表[left,qleft)之间有多个个元素被分到左边    
  58.     int ss;//[qleft, qright]内将被划分到左子树的元素数目    
  59.     int mid=(left+right)>>1;    
  60.     if(left==qleft){    
  61.         s=0;    
  62.         ss=toLeft[level][qright];    
  63.     }else{    
  64.         s=toLeft[level][qleft-1];    
  65.         ss=toLeft[level][qright]-s;    
  66.     }    
  67.     int newl,newr;    
  68.     if(k<=ss){//查询左边    
  69.         newl=left+s;    
  70.         newr=left+s+ss-1;    
  71.         return query(level+1,left,mid,newl,newr,k);    
  72.     }  
  73.     else{//查询右边    
  74.         newl=mid-left+1+qleft-s;    
  75.         newr=mid-left+1+qright-s-ss;    
  76.         return query(level+1,mid+1,right,newl, newr,k - ss);    
  77.     }    
  78. }    
  79. int main(){    
  80.     int n,m;    
  81.     while(scanf("%d %d",&n,&m)!=EOF) {    
  82.         int i;    
  83.         for(i=1;i<=n;i++){    
  84.             scanf("%d",&tree[0][i]);    
  85.             sorted[i]=tree[0][i];    
  86.         }    
  87.         sort(sorted+1,sorted+n+1);    
  88.         build(0,1,n);    
  89.         int ql,qr,k;    
  90.         for(i=0;i<m;i++){    
  91.             scanf("%d %d %d",&ql,&qr,&k);    
  92.             printf("%d\n",query(0,1,n,ql,qr,k));    
  93.         }    
  94.     }    
  95.     return 0;    
  96. }  

相关推荐