现在的位置: 首页 > 综合 > 正文

归并树与划分树 My归并树，划分树模板。划分树学习（poj 2104，hdu 3473）

2017年12月13日 ⁄ 综合 ⁄ 共 12091字 ⁄ 字号 小 中 大 ⁄ 评论关闭

归并树与划分树  

2010-08-16 23:24:40|  分类： ACM|字号 订阅

据说最近挺热门的，想起寒假学过归并树，结果现在什么都不记得了，模拟了下归并排序终于想起来了
归并树
以1 5 2 6 3 7为例：
把归并排序递归过程记录下来即是一棵归并树：
        [1 2 3 5 6 7]
    [1 2 5]      [3 6 7]
   [1 5] [2]    [6 3] [7] 
  [1][5]        [6][3]
用对应的下标区间建线段树：（这里下标区间对应的是原数列）
            [1 6]
     [1 3]      [4 6]
  [1 2] [3]   [4 5][6]
  [1][2]      [4][5]
每次查找[l r]区间的第k大数时，在[1 2 3 4 5 6 7]这个有序的序列中二分所要找的数x，然后对应到线段树中去找[l r]中比x小的数有几个，即x的rank。由于线段树中任意区间对应到归并树中是有序的，所以在线段树中的某个区间查找比x小的数的个数也可以用二分在对应的归并树中找。这样一次查询的时间复杂度是log(n)^2。
要注意的是，多个x有相同的rank时，应该取最大的一个。

划分树
同样以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。于是我就找什么是唯一的，很容易想到数组的下标，仔细观察，如果从划分树叶子回溯，相当于在对数组下标进行归并排序，于是我的问题就解决了~

思考：划分树可以求逆序数吗，划分树中如何求一个数在某个区间的rank

 

My归并树，划分树模板。

分类： 线段树 树状数组 数据结构2011-08-11
13:23 787人阅读 评论(8) 收藏 举报
buildtreeclass

POJ 2104 寻找区间第K数

划分树，时间复杂度O(MlogN)，归并树，时间复杂度O(Mlog^3N)。

归并树

[cpp] view
plaincopy

  1. #include <queue>  
  2. #include <stack>  
  3. #include <math.h>  
  4. #include <stdio.h>  
  5. #include <stdlib.h>  
  6. #include <iostream>  
  7. #include <limits.h>  
  8. #include <string.h>  
  9. #include <string>  
  10. #include <algorithm>  
  11. #define MID(x,y) ( ( x + y ) >> 1 )  
  12. #define L(x) ( x << 1 )  
  13. #define R(x) ( x << 1 | 1 )  
  14. #define BUG puts("here!!!")  
  15.   
  16. using namespace std;  
  17.   
  18. const int MAX = 100010;  
  19. class Merger_tree{  
  20. public :  
  21.     class Tnode{  
  22.     public :  
  23.         int l,r;  
  24.         int len() { return r - l;}  
  25.         int mid() { return MID(l,r);}  
  26.         bool in(int ll,int rr) { return l >= ll && r <= rr; }  
  27.         void lr(int ll,int rr){ l = ll; r = rr;}  
  28.     };  
  29.     Tnode node[MAX<<2];  
  30.     int seg[20][MAX],a[MAX],n;  
  31.     void init()  
  32.     {  
  33.         memset(seg,0,sizeof(seg));  
  34.         memset(node,0,sizeof(node));  
  35.     }  
  36.     void build(int s,int t){ n = t; Merger_build(1,s,t,1); }  
  37.     int find(int x,int y,int k) { return find_rank(n,x,y,k); };  
  38.     void Merger_build(int t,int l,int r,int deep)  
  39.     {  
  40.         node[t].lr(l, r);  
  41.         if( node[t].len() == 0 )  
  42.         {  
  43.             seg[deep][l] = a[l];  
  44.             return ;  
  45.         }  
  46.         int mid = MID(l, r);  
  47.         Merger_build(L(t), l, mid, deep+1);  
  48.         Merger_build(R(t), mid+1, r, deep+1);  
  49.         int k = l,i = l,j = mid+1;  
  50.         while( i <= mid && j <= r )  
  51.             if( seg[deep+1][i] < seg[deep+1][j] )  
  52.                 seg[deep][k++] = seg[deep+1][i++];  
  53.             else  
  54.                 seg[deep][k++] = seg[deep+1][j++];  
  55.         while( i <= mid )  
  56.             seg[deep][k++] = seg[deep+1][i++];  
  57.           
  58.         while( j <= r )  
  59.             seg[deep][k++] = seg[deep+1][j++];  
  60.               
  61.     }  
  62.     int find_k(int t,int l,int r,int deep,int val)  
  63.     {  
  64.         if( node[t].in(l,r) )  
  65.         {  
  66.             int ll = node[t].l, rr = node[t].r;  
  67.             while( ll < rr )  
  68.             {  
  69.                 int mid = MID(ll, rr);  
  70.                 if( seg[deep][mid] < val )  
  71.                     ll = mid + 1;  
  72.                 else  
  73.                     rr = mid;  
  74.             }  
  75.             if( seg[deep][ll] <= val )  
  76.                 return ll - node[t].l + 1;  
  77.             else  
  78.                 return ll - node[t].l;  
  79.         }  
  80.         if( node[t].len() == 0 ) return 0;  
  81.         int ans = 0;  
  82.         int mid = node[t].mid();  
  83.         if( l <= mid ) ans += find_k(L(t), l, r, deep+1, val);  
  84.         if( r >= mid ) ans += find_k(R(t), l, r, deep+1, val);  
  85.         return ans;  
  86.     }         
  87.     int find_rank(int n,int x,int y,int k)  
  88.     {  
  89.         int l = 1,r = n;  
  90.         while( l < r )  
  91.         {  
  92.             int mid = MID(l, r);  
  93.             if( find_k(1, x, y, 1, seg[1][mid]) < k )  
  94.                 l = mid + 1;  
  95.             else  
  96.                 r = mid;  
  97.         }  
  98.         return seg[1][l];  
  99.     }  
  100. };  
  101.   
  102. Merger_tree t;   
  103. int main()  
  104. {  
  105.     int n,m,x,y,k;  
  106.     while( ~scanf("%d%d",&n,&m) )  
  107.     {  
  108.         t.init();  
  109.         for(int i=1; i<=n; i++)  
  110.             scanf("%d",&t.a[i]);  
  111.           
  112.         t.build(1,n);  
  113.         while( m-- )  
  114.         {  
  115.             scanf("%d%d%d",&x,&y,&k);  
  116.             int ans = t.find(x,y,k);  
  117.             printf("%d\n",ans);  
  118.         }  
  119.     }  
  120.   
  121. return 0;  
  122. }  

划分树

[cpp] view
plaincopy

  1. #include <queue>  
  2. #include <stack>  
  3. #include <math.h>  
  4. #include <stdio.h>  
  5. #include <stdlib.h>  
  6. #include <iostream>  
  7. #include <limits.h>  
  8. #include <string.h>  
  9. #include <string>  
  10. #include <algorithm>  
  11. #define MID(x,y) ( ( x + y ) >> 1 )  
  12. #define L(x) ( x << 1 )  
  13. #define R(x) ( x << 1 | 1 )  
  14. #define BUG puts("here!!!")  
  15.   
  16. using namespace std;  
  17.   
  18. const int MAX = 100010;  
  19. class Parti_tree{  
  20. public :   
  21.     class Tnode{  
  22.     public :  
  23.         int l,r;  
  24.         int len() { return r - l;}  
  25.         int mid() { return MID(l,r);}  
  26.         bool in(int ll,int rr) { return l >= ll && r <= rr; }  
  27.         void lr(int ll,int rr){ l = ll; r = rr;}  
  28.     };  
  29.     Tnode node[MAX<<2];  
  30.     int Left[20][MAX], seg[20][MAX], sa[MAX];  
  31.     void init()  
  32.     {  
  33.         memset(Left,0,sizeof(Left));  
  34.         memset(node,0,sizeof(node));  
  35.     }  
  36.     void build(int s,int t){ sort(sa+1,sa+t+1); Parti_build(1,s,t,1); }  
  37.     int find(int s,int t,int k){ return find_rank(1,s,t,1,k); }  
  38.     void Parti_build(int t,int l,int r,int d)  
  39.     {  
  40.         node[t].lr(l, r);  
  41.         if( node[t].len() == 0 ) return ;  
  42.         int mid = MID(l, r), lsame = mid - l + 1;  
  43.         for(int i=l; i<=r; i++)  
  44.             if( seg[d][i] < sa[mid] )  
  45.                 lsame--;  
  46.         int lpos = l,rpos = mid+1,same = 0;  
  47.         for(int i=l; i<=r; i++)  
  48.         {  
  49.             if( i == l )  
  50.                 Left[d][i] = 0;  
  51.             else  
  52.                 Left[d][i] = Left[d][i-1];  
  53.             if( seg[d][i] < sa[mid] )  
  54.             {  
  55.                 Left[d][i]++;  
  56.                 seg[d+1][lpos++] = seg[d][i];  
  57.             }  
  58.             if( seg[d][i] > sa[mid] )  
  59.                 seg[d+1][rpos++] = seg[d][i];  
  60.             if( seg[d][i] == sa[mid] )  
  61.                 if( same < lsame )     
  62.                 {  
  63.                     same++;  
  64.                     Left[d][i]++;  
  65.                     seg[d+1][lpos++] = seg[d][i];  
  66.                 }  
  67.                 else  
  68.                     seg[d+1][rpos++] = seg[d][i];  
  69.         }  
  70.         Parti_build(L(t), l, mid, d+1);  
  71.         Parti_build(R(t), mid+1, r, d+1);         
  72.     }  
  73.     int find_rank(int t,int l,int r,int d,int val)  
  74.     {  
  75.         if( node[t].len() == 0 )  
  76.             return seg[d][l];  
  77.         int s,ss;  
  78.         if( l == node[t].l )  
  79.         {  
  80.             s = Left[d][r];  
  81.             ss = 0;  
  82.         }  
  83.         else  
  84.         {  
  85.             s = Left[d][r] - Left[d][l-1];  
  86.             ss = Left[d][l-1];  
  87.         }  
  88.         if( s >= val )  
  89.             return find_rank(L(t), node[t].l+ss, node[t].l+ss+s-1, d+1, val);  
  90.         else  
  91.         {  
  92.             int mid = node[t].mid();  
  93.             int bb = l - node[t].l - ss;  
  94.             int b = r - l + 1 - s;  
  95.             return find_rank(R(t), mid+bb+1, mid+bb+b,d+1,val-s);  
  96.         }  
  97.     }  
  98. };  
  99.   
  100. Parti_tree t;  
  101. int main()  
  102. {  
  103.     int n,m,x,y,k;  
  104.       
  105.     while( ~scanf("%d%d",&n,&m) )  
  106.     {  
  107.         t.init();  
  108.         for(int i=1; i<=n; i++)  
  109.         {  
  110.             scanf("%d",&t.sa[i]);  
  111.             t.seg[1][i] = t.sa[i];  
  112.         }  
  113.         t.build(1,n);  
  114.         while( m-- )  
  115.         {  
  116.             scanf("%d%d%d",&x,&y,&k);  
  117.             int ans = t.find(x, y, k);  
  118.             printf("%d\n",ans);  
  119.         }  
  120.     }  
  121.   
  122. return 0;  
  123. }  

 

划分树学习（poj 2104，hdu 3473）

分类： hdu poj 线段树
树状数组 数据结构 知识就是力量！2011-08-12
11:11 4835人阅读 评论(9) 收藏 举报
buildtreeclassquery

线段树一维的刷差不多了，求区间第K数一直卡着。

划分树和归并树都可以求，比较了一下时间效率，划分树比归并树快了很多，而且POJ有个求区间第K数的题用归并树居然过不去。

鉴于时间短，我决定把划分树给弄明白= =。。借用下小HH的图。

划分树和归并树都是用线段树作为辅助的，原理是基于 快排 和 归并排序 的。

划分树的建树过程基本就是模拟快排过程，取一个已经排过序的区间中值，然后把小于中值的点放左边，大于的放右边。并且记录d层第i个数之前（包括i）小于中值的放在左边的数。具体看下面代码注释。

关键是询问过程，具体见图。CSDN现在上传图片质量好差啊啊啊啊啊啊 。



hdu3473是求中位数的（可以证得，差值和最小的一定是中位数（如果是偶数个的话，中间两个任意以一个均可）），但是涉及求和，涉及求得在区间[l,r]中，中位数之前元素的和（排好序后）。这样的话，在建树过程增加一个二维数组，第d层下标<=i之前元素的和。然后找的时候，求区间差值和即可。

附，poj2104代码，买一赠一，poj2761和2104基本一样

[cpp] view
plaincopy

  1. #include <queue>  
  2. #include <stack>  
  3. #include <math.h>  
  4. #include <stdio.h>  
  5. #include <stdlib.h>  
  6. #include <iostream>  
  7. #include <limits.h>  
  8. #include <string.h>  
  9. #include <string>  
  10. #include <algorithm>  
  11. #define MID(x,y) ( ( x + y ) >> 1 )  
  12. #define L(x) ( x << 1 )  
  13. #define R(x) ( x << 1 | 1 )  
  14. #define BUG puts("here!!!")  
  15. #define LL long long  
  16. using namespace std;  
  17.   
  18. const int MAX = 100010;  
  19. LL s[MAX];  
  20. class Parti_tree{  
  21. public :   
  22.     class Tnode{                            // 我的一维线段树定义   
  23.     public :  
  24.         int l,r;  
  25.         int len() { return r - l;}  
  26.         int mid() { return MID(l,r);}  
  27.         bool in(int ll,int rr) { return l >= ll && r <= rr; }  
  28.         void lr(int ll,int rr){ l = ll; r = rr;}  
  29.     };  
  30.     Tnode node[MAX<<2];                     
  31.     int num_left[20][MAX], seg[20][MAX],sa[MAX];//sa数组存sort后的结果  
  32.                         //seg数组存的是d层划分后的数字 （类似快排Partation （d-1）次后的结果）   
  33.                         //num_left存的是d层在i之前(包括i)小于 sa[mid] 的数的数目   
  34.     void init()  
  35.     {  
  36.         memset(seg,0,sizeof(seg));   
  37.         memset(num_left,0,sizeof(num_left));  
  38.         memset(node,0,sizeof(node));  
  39.     }  
  40.     void build(int s,int t)  
  41.     {  
  42.         sort(sa+s,sa+t+s);  
  43.         Parti_build(1,s,t,1);  
  44.     }  
  45.     int query(int s,int t,int k)  
  46.     {  
  47.         return find_rank(1,s,t,1,k);  
  48.     }  
  49.     void Parti_build(int t,int l,int r,int d)  
  50.     {  
  51.         node[t].lr(l, r);  
  52.         if( node[t].len() == 0 ) return ;  
  53.         int mid = MID(l, r), lsame = mid - l + 1;  
  54.         for(int i=l; i<=r; i++)//首先确定分到每一侧的数的数目   
  55.             if( seg[d][i] < sa[mid] )//因为相同的元素可能被分到两侧   
  56.                 lsame--;   
  57.         int lpos = l,rpos = mid+1;  
  58.         for(int i=l; i<=r; i++)  
  59.         {  
  60.             if( i == l )  
  61.                 num_left[d][i] = 0;  
  62.             else  
  63.                 num_left[d][i] = num_left[d][i-1];  
  64.             if( seg[d][i] < sa[mid] )  
  65.             {  
  66.                 num_left[d][i]++;  
  67.                 seg[d+1][lpos++] = seg[d][i];  
  68.             }  
  69.             if( seg[d][i] > sa[mid] )  
  70.                 seg[d+1][rpos++] = seg[d][i];  
  71.             if( seg[d][i] == sa[mid] )  
  72.                 if( lsame > 0 )  // 如果大于0，说明左侧可以分和sa[mid]相同的数字   
  73.                 {         
  74.                     lsame--;  
  75.                     num_left[d][i]++;  
  76.                     seg[d+1][lpos++] = seg[d][i];  
  77.                 }  
  78.                 else            //反之，说明左侧数字已经分满了，就分到右边去   
  79.                     seg[d+1][rpos++] = seg[d][i];  
  80.         }  
  81.         Parti_build(L(t), l, mid, d+1);  
  82.         Parti_build(R(t), mid+1, r, d+1);     
  83.     }  
  84.     int find_rank(int t,int l,int r,int d,int val)  
  85.     {  
  86.         if( node[t].len() == 0 ) return seg[d][l];  
  87.         int s,ss;               //s表示区间[l,r]有多少个小于sa[mid]的数被分到左边   
  88.         if( l == node[t].l )  
  89.             ss = 0;  
  90.         else  
  91.             ss = num_left[d][l-1];  
  92.         s = num_left[d][r] - ss;//ss表示从当前区间的L到l-1有多少个小于sa[mid]的数被分到左边   
  93.         if( s >= val )  
  94.             return find_rank(L(t), node[t].l+ss, node[t].l+ss+s-1, d+1, val);  
  95.         else  
  96.         {  
  97.             int mid = node[t].mid();  
  98.             int bb = l - node[t].l - ss;    //表示从当前区间L到l-1有多少个分到右边   
  99.             int b = r - l + 1 - s;          //表示[l,r]有多少个分到右边   
  100.             return find_rank(R(t), mid+bb+1, mid+bb+b,d+1,val-s);  
  101.         }  
  102.     }  
  103. };  
  104.    
  105. Parti_tree t;  
  106. int main()  
  107. {  
  108.     int n,m,x,y,k;  
  109.       
  110.     while( ~scanf("%d%d",&n,&m) )  
  111.     {  
  112.         t.init();  
  113.         for(int i=1; i<=n; i++)  
  114.         {  
  115.             scanf("%d",&t.sa[i]);  
  116.             t.seg[1][i] = t.sa[i];  
  117.         }  
  118.         t.build(1,n);  
  119.         while( m-- )  
  120.         {  
  121.             scanf("%d%d%d",&x,&y,&k);  
  122.             int ans = t.query(x, y, k);  
  123.             printf("%d\n",ans);  
  124.         }  
  125.     }  
  126.   
  127. return 0;  
  128. }
     

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞