小男孩‘自慰网亚洲一区二区,亚洲一级在线播放毛片,亚洲中文字幕av每天更新,黄aⅴ永久免费无码,91成人午夜在线精品,色网站免费在线观看,亚洲欧洲wwwww在线观看

搜索
分享

劃分樹

 strangedbly 2016-09-23

劃分樹，從網(wǎng)上看到的代碼的風格主要有兩種。

下面的介紹直接是從網(wǎng)上找的看的懂的貼了份過來，其中有些修改。

劃分樹的定義

         劃分樹定義為，它的每一個節(jié)點保存區(qū)間[lft,rht]所有元素，元素順序與原數(shù)組（輸入）相同，但是，兩個子樹的元素為該節(jié)點所有元素排序后(rht-lft+1)/2個進入左子樹，其余的到右子樹，同時維護一個num域，num[i]表示lft->i這個點有多少個進入了左子樹。

 

劃分樹的Sample

 

   如果由下而上看這個圖，我們就會發(fā)現(xiàn)它和歸并排序的（歸并樹）的過程很類似，或者說正好相反。歸并樹是由下而上的排序，而它確實是由上而下的排序（觀察’4’的運動軌跡，我們可以猜到，劃分樹的排序也是一種穩(wěn)定的排序方法，這里不是說明的重點，不予證明），但這正是它可以用來解決第k大元素的理由所在。（具體的理由，寫完再補）

l  劃分樹的存儲結構（采用層次存儲結構（由下而上，由左到右，每層兩個孩子，見上圖））

  1. constint N=1e5+5;  
  2. int sorted[N];            //對原來集合中的元素排序后的值  
  3. struct node  
  4. {  
  5.          int valu[N];       //val記錄第k層當前位置元素的值  
  6.          int num[N];                //num記錄元素所在區(qū)間的當前位置之前進入左孩子的個數(shù)  
  7.          LL sum[N];        //sum記錄比當前元素小的元素的和  
  8. }t[20];  

l  劃分樹的建立build

劃分樹的建立和普通的二叉樹的建立過程差不多，仍然采取中序的過程（先根節(jié)點，然后左右孩子）。

樹的建立相對比較簡單，我們依據(jù)的是已經(jīng)排好序的位置進行建樹，所以先用快排將原集合還序。要維護每個節(jié)點的num域。
版本一：

  1. void build(int lft,int rht,int ind)  
  2. {  
  3.     if(lft==rht) return;  
  4.     int mid=lft+(rht-lft)>>1;  
  5.     int isame=mid-lft+1,same=0;  
  6.     /* isame用來標記和中間值val_mid相等的，且分到左孩子的數(shù)的個數(shù)  
  7.        初始時，假定當前區(qū)間[lft,rht]有mid-lft+1個和valu_mid相等。 
  8.        先踢掉中間值小的，剩下的就是要插入到左邊的 
  9.      */  
  10.     for(int i=lft;i<=rht;i++)  
  11.         if(t[ind].valu[i]<sorted[mid]) isame--;  
  12.     int ln=lft,rn=mid+1;  
  13.     for(int i=lft;i<=rht;i++)  
  14.     {  
  15.         if(i==lft)      //初始一個子樹  
  16.         {  
  17.             t[p].num[i]=0;  
  18.             t[p].sum[i]=0;  
  19.         }  
  20.         else            //初始區(qū)間下一個節(jié)點  
  21.         {  
  22.             t[p].num[i]=t[p].num[i-1];  
  23.             t[p].sum[i]=t[p].sum[i-1];  
  24.         }  
  25.         /* 如果大于，肯定進入右孩子，否則判斷是否還有相等的應該進入左孩子的， 
  26.            沒有，直接進入右孩子，否則進入左孩子，同時更新節(jié)點的sum域和num域 
  27.          */  
  28.         if(t[p].val[i]<sorted[mid])  
  29.         {  
  30.             t[p].num[i]++;  
  31.             t[p].sum[i]+=t[p].valu[i];  
  32.             t[p+1].valu[ln++]=t[p].valu[i];  
  33.         }  
  34.         else if(t[p].valu[i]>sorted[mid])  
  35.             t[p+1].valu[rn++]=t[p].valu[i];  
  36.         else   
  37.         {  
  38.             if(same<isame)  
  39.             {  
  40.                 same++;  
  41.                 t[p].num[i]++;  
  42.                 t[p].sum[i]+=t[p].valu[i];  
  43.                 t[p+1].valu[ln++]=t[p].valu[i];  
  44.             }  
  45.             else   
  46.             {  
  47.                 t[p+1].valu[rn++]=t[p].valu[i];  
  48.             }  
  49.         }  
  50.     }  
  51.     build(lft,mid,ind+1);  
  52.     build(mid+1,rht,ind+1);  
  53. }  
可以看出在版本一里，每個區(qū)間的起點的num[ind][lft]和sum[ind][lft]都會被賦值為0。另一種方式在建立這棵樹的時候，并沒有這么做，而是在前面的基礎上繼續(xù)。也就是說只有將num[ind][0]和sum[ind][0]賦值為0。另外這個版本里我將排序后的數(shù)組是order而不是sorted

版本二：

  1. void build(int lft,int rht,int ind)  
  2. {  
  3.     if(lft==rht) return;  
  4.     int mid=MID(lft,rht);  
  5.     int same=mid-lft+1,ln=lft,rn=mid+1;  
  6.     for(int i=lft;i<=rht;i++)  
  7.         if(valu[ind][i]<order[mid]) same--;  
  8.     for(int i=lft;i<=rht;i++)  
  9.     {  
  10.         int flag=0;  
  11.         if((valu[ind][i]<order[mid])||valu[ind][i]==order[mid]&&same>0)  
  12.         {  
  13.             flag=1;  
  14.             valu[ind+1][ln++]=valu[ind][i];  
  15.             if(valu[ind][i]==order[mid]) same--;  
  16.             lsum[ind][i]=lsum[ind][i-1]+valu[ind][i];  
  17.         }  
  18.         else  
  19.         {  
  20.             lsum[ind][i]=lsum[ind][i-1];  
  21.             valu[ind+1][rn++]=valu[ind][i];  
  22.         }  
  23.         toLft[ind][i]=toLft[ind][i-1]+flag;  
  24.     }  
  25.     build(lft,mid,ind+1);  
  26.     build(mid+1,rht,ind+1);  
  27. }  

l  劃分樹的查找

在區(qū)間[a,b]上查找第k大的元素，同時返回它的位置和區(qū)間小于[a,b]的所有數(shù)的和。

1.      如果t[p].num[b]-t[p].num[a-1]>=k，即，進入左孩子的個數(shù)已經(jīng)超過k個，那么就往左孩子里面查找，同時更新[a,b]=>[lft+t[p].num[a-1]，lft+t[p].num[b]-1]

2.      如果t[p].num[b]-t[p].num[a-1]<k，即，進入p的左孩子的個數(shù)小于k個，那么就要往右孩子查找第k-s(s表示進入左孩子的個數(shù))個元素。同時更新sum域，因而這樣求出的sum只是嚴格小于在[a,b]區(qū)間中第k大的數(shù)的和。

詳細過程見代碼和注釋：
/*在區(qū)間[a,b]上查找第k大元素，同時sum返回區(qū)間[a,b]中小于第k大元素的和*/

  1. int query(int a,int b,int k,int p,int lft,int rht)  
  2. {  
  3.     if(lft==rht) return t[p].valu[a];  
  4.     /*到達葉子結點就找到該元素，返回 
  5.     S 記錄區(qū)間[a,b]中進入左孩子的元素的個數(shù) 
  6.     SS 記錄區(qū)間[lft,a-1]中進入左孩子的元素的個數(shù) 
  7.     SSS 記錄區(qū)間[a,b]中小于第k大的元素的值和 
  8.     B2 表示[lft,a-1]中分到右孩子的個數(shù) 
  9.     BB 表示[a,b]中分到右孩子的個數(shù) 
  10. */  
  11.     int s,ss,b2,bb,mid=lft+(rht-lft)/2;  
  12.     double sss=0;  
  13.     if(a==lft)//端點重合的情況，單獨考慮  
  14.     {  
  15.         s = t[p].num[b];   
  16.         ss = 0;   
  17.         sss = t[p].sum[b];  
  18.     }  
  19.     else   
  20.     {  
  21.         s = t[p].num[b] - t[p].num[a-1];  
  22.         ss = t[p].num[a-1];   
  23.         sss = t[p].sum[b] - t[p].sum[a-1];  
  24.     }  
  25.     if(s>=k) //進入左孩子，同時更新區(qū)間端點值。  
  26.     {  
  27.         a = lft + ss;//   
  28.         b = lft + ss + s - 1;   
  29.         return query(a, b, k, p+1, lft, mid);  
  30.     }  
  31.     else   
  32.     {  
  33.         bb = a - lft - ss;  
  34.         b2 = b - a - 1 - s;   
  35.         a = mid + bb + 1;   
  36.         b = mid + bb + b2;   
  37.         sum += sss;  
  38.         return query(a,b,k-s,p+1,mid+1,rht);  
  39.     }  
  40. }  
版本二：

  1. int query(int st,int ed,int k,int lft,int rht,int ind)  
  2. {  
  3.     if(lft==rht) return valu[ind][lft];  
  4.     /* 
  5.         lx表示從lft到st-1這段區(qū)間內(nèi)有多少個數(shù)進入左子樹 
  6.         ly表示從st到ed這段區(qū)間內(nèi)有多少個數(shù)進入左子樹 
  7.         rx表示從lft到st-1這段區(qū)間內(nèi)有多少個數(shù)進入右子樹 
  8.         ry表示從st到ed這段區(qū)間內(nèi)有多少個數(shù)進入右子樹 
  9.      */  
  10.     int mid=MID(lft,rht);  
  11.     int lx=toLft[ind][st-1]-toLft[ind][lft-1];  
  12.     int ly=toLft[ind][ed]-toLft[ind][st-1];  
  13.     int rx=st-1-lft+1-lx;  
  14.     int ry=ed-st+1-ly;  
  15.     if(ly>=k) return query(lft+lx,lft+lx+ly-1,k,lft,mid,ind+1);  
  16.     else  
  17.     {  
  18.         isum+=lsum[ind][ed]-lsum[ind][st-1];  
  19.         st=mid+1+rx;  
  20.         ed=mid+1+rx+ry-1;  
  21.         return query(st,ed,k-ly,mid+1,rht,ind+1);  
  22.     }  
  23. }  


下面給出POJ  2104 K-th Number的兩種風格的代碼。

風格一：

  1. #include <iostream>  
  2. #include <cstdio>  
  3. #include <cstring>  
  4. #include <algorithm>  
  5. using namespace std;  
  6. #define MID(a,b) (a+((b-a)>>1))  
  7. const int N=1e5+5;  
  8. struct node  
  9. {  
  10.     int valu[N],num[N];  
  11. };  
  12. struct P_Tree  
  13. {  
  14.     int n,order[N];  
  15.     node t[20];  
  16.     void init(int len)  
  17.     {  
  18.         n=len;  
  19.         for(int i=1;i<=n;i++)  
  20.         {  
  21.             scanf("%d",&order[i]);  
  22.             t[0].valu[i]=order[i];  
  23.         }  
  24.         sort(order+1,order+1+n);  
  25.         build(1,n,0);  
  26.     }  
  27.     void build(int lft,int rht,int ind)  
  28.     {  
  29.         //cout<<lft<<" "<<rht<<endl;  
  30.         if(lft==rht) return;  
  31.         int mid=MID(lft,rht);  
  32.         int lsame=mid-lft+1,same=0,ln=lft,rn=mid+1;  
  33.         for(int i=lft;i<=rht;i++)  
  34.             if(t[ind].valu[i]<order[mid]) lsame--;  
  35.         for(int i=lft;i<=rht;i++)  
  36.         {  
  37.             if(i==lft) t[ind].num[i]=0;  
  38.             else t[ind].num[i]+=t[ind].num[i-1];  
  39.   
  40.             if(t[ind].valu[i]<order[mid])  
  41.                 t[ind].num[i]++,t[ind+1].valu[ln++]=t[ind].valu[i];  
  42.             else if(t[ind].valu[i]>order[mid])  
  43.                 t[ind+1].valu[rn++]=t[ind].valu[i];  
  44.             else  
  45.             {  
  46.                 same++;  
  47.                 if(lsame>=same)  
  48.                     t[ind].num[i]++,t[ind+1].valu[ln++]=t[ind].valu[i];  
  49.                 else t[ind+1].valu[rn++]=t[ind].valu[i];  
  50.             }  
  51.         }  
  52.         build(lft,mid,ind+1);  
  53.         build(mid+1,rht,ind+1);  
  54.     }  
  55.     int query(int st,int ed,int k,int lft,int rht,int ind)  
  56.     {  
  57.         if(lft==rht) return t[ind].valu[lft];  
  58.         int lx,ly,rx,ry,mid=MID(lft,rht);  
  59.         if(st==lft) lx=0,ly=t[ind].num[ed];  
  60.         else lx=t[ind].num[st-1],ly=t[ind].num[ed]-t[ind].num[st-1];  
  61.         if(ly>=k)  
  62.         {  
  63.             st=lft+lx;  
  64.             ed=lft+lx+ly-1;  
  65.             return query(st,ed,k,lft,mid,ind+1);  
  66.         }  
  67.         else  
  68.         {  
  69.             rx=st-1-lft+1-lx;  
  70.             ry=ed-st+1-ly;  
  71.             st=mid+1+rx;  
  72.             ed=mid+1+rx+ry-1;  
  73.             return query(st,ed,k-ly,mid+1,rht,ind+1);  
  74.         }  
  75.     }  
  76. }tree;  
  77. int main()  
  78. {  
  79.     int n,m;  
  80.     while(scanf("%d%d",&n,&m)!=EOF)  
  81.     {  
  82.         tree.init(n);  
  83.         for(int i=0;i<m;i++)  
  84.         {  
  85.             int a,b,c;  
  86.             scanf("%d%d%d",&a,&b,&c);  
  87.             int res=tree.query(a,b,c,1,n,0);  
  88.             printf("%d\n",res);  
  89.         }  
  90.     }  
  91.     return 0;  
  92. }  

風格二：

  1. #include <iostream>  
  2. #include <cstdio>  
  3. #include <cstring>  
  4. #include <algorithm>  
  5. using namespace std;  
  6. #define MID(a,b) (a+((b-a)>>1))  
  7. typedef long long LL;  
  8. const int N=1e5+5;  
  9. struct P_Tree  
  10. {  
  11.     int n,order[N];  
  12.     int valu[20][N],num[20][N];  
  13.     LL sum[N],lsum[20][N],isum;  
  14.     void init(int len)  
  15.     {  
  16.         n=len;  sum[0]=0;  
  17.         for(int i=0;i<20;i++) valu[i][0]=0,num[i][0]=0,lsum[i][0]=0;  
  18.         for(int i=1;i<=n;i++)  
  19.         {  
  20.             scanf("%d",&order[i]);  
  21.             valu[0][i]=order[i];  
  22.             sum[i]=sum[i-1]+order[i];  
  23.         }  
  24.         sort(order+1,order+1+n);  
  25.         build(1,n,0);  
  26.     }  
  27.     void build(int lft,int rht,int ind)  
  28.     {  
  29.         if(lft==rht) return;  
  30.   
  31.         int mid=MID(lft,rht);  
  32.         int same=mid-lft+1,ln=lft,rn=mid+1;  
  33.         for(int i=lft;i<=rht;i++)  
  34.             if(valu[ind][i]<order[mid]) same--;  
  35.         for(int i=lft;i<=rht;i++)  
  36.         {  
  37.             int flag=0;  
  38.             if((valu[ind][i]<order[mid])||(valu[ind][i]==order[mid]&&same))  
  39.             {  
  40.                 flag=1;  
  41.                 valu[ind+1][ln++]=valu[ind][i];  
  42.                 lsum[ind][i]=lsum[ind][i-1]+valu[ind][i];  
  43.                 if(valu[ind][i]==order[mid]) same--;  
  44.             }  
  45.             else   
  46.             {  
  47.                 valu[ind+1][rn++]=valu[ind][i];  
  48.                 lsum[ind][i]=lsum[ind][i-1];  
  49.             }  
  50.             num[ind][i]=num[ind][i-1]+flag;  
  51.         }  
  52.         build(lft,mid,ind+1);  
  53.         build(mid+1,rht,ind+1);  
  54.     }  
  55.     int query(int st,int ed,int k,int lft,int rht,int ind)  
  56.     {  
  57.         if(lft==rht) return valu[ind][lft];  
  58.   
  59.         int mid=MID(lft,rht);  
  60.         int lx=num[ind][st-1]-num[ind][lft-1];  
  61.         int ly=num[ind][ed]-num[ind][st-1];  
  62.         int rx=st-1-lft+1-lx;  
  63.         int ry=ed-st+1-ly;  
  64.         if(ly>=k) return query(lft+lx,lft+lx+ly-1,k,lft,mid,ind+1);  
  65.         else   
  66.         {  
  67.             isum+=lsum[ind][ed]-lsum[ind][st-1];  
  68.             st=mid+1+rx;  
  69.             ed=mid+1+rx+ry-1;  
  70.             return query(st,ed,k-ly,mid+1,rht,ind+1);  
  71.         }  
  72.     }  
  73. }tree;  
  74. int main()  
  75. {  
  76.     int n,m;  
  77.     while(scanf("%d%d",&n,&m)!=EOF)  
  78.     {  
  79.         tree.init(n);  
  80.         for(int i=0;i<m;i++)  
  81.         {  
  82.             int a,b,c;  
  83.             scanf("%d%d%d",&a,&b,&c);  
  84.             int res=tree.query(a,b,c,1,n,0);  
  85.             printf("%d\n",res);  
  86.         }  
  87.     }  
  88.     return 0;  
  89. }  

昨天的杭電多校聯(lián)合訓練熱身賽的一道題，求區(qū)間的中位數(shù)，快排會超時，劃分樹的模版題。。 

 

劃分樹是一種基于線段樹的數(shù)據(jù)結構。主要用于快速求出(在log(n)的時間復雜度內(nèi)）序列區(qū)間的第k大值 。

劃分樹和歸并樹都是用線段樹作為輔助的，原理是基于快排 和歸并排序 的。

劃分樹的建樹過程基本就是模擬快排過程，取一個已經(jīng)排過序的區(qū)間中值，然后把小于中值的點放左邊，大于的放右邊。并且記錄d層第i個數(shù)之前（包括i）小于中值的放在左邊的數(shù)。具體看下面代碼注釋。


查找其實是關鍵，因為再因查找[l,r]需要到某一點的左右孩子時需要把[l,r]更新。具體分如下幾種情況討論：
假設要在區(qū)間[l,r]中查找第k大元素，t為當前節(jié)點，lch，rch為左右孩子，left，mid為節(jié)點t左邊界和中間點。
1、sum[r]-sum[l-1]>=k，查找lch[t],區(qū)間對應為[ left+sum[l-1] , left+sum[r]-1 ]
2、sum[r]-sum[l-1]<k,查找rch[t]，區(qū)間對應為[ mid+1+l-left-sum[l-1] , mid+1+r-left-sum[r] ]

上面兩個關系在紙上可以推出來，對著上圖更容易理解關系式


POJ 2104 劃分樹模板    http:///problem?id=2104


復制代碼
 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 using namespace std;
 5 #define N 100005
 6 int a[N], as[N];//原數(shù)組，排序后數(shù)組
 7 int n, m;
 8 int sum[20][N];//記錄第i層的1~j劃分到左子樹的元素個數(shù)(包括j)
 9 int tree[20][N];//記錄第i層元素序列
10 void build(int c, int l, int r){
11     int i, mid = (l + r) >> 1, lm = mid - l + 1, lp = l, rp = mid + 1;
12     for (i = l; i <= mid; i++){
13         if (as[i] < as[mid]){
14             lm--;//先假設左邊的(mid - l + 1)個數(shù)都等于as[mid],然后把實際上小于as[mid]的減去
15         }
16     }
17     for (i = l; i <= r; i++){
18         if (i == l){
19             sum[c][i] = 0;//sum[i]表示[l, i]內(nèi)有多少個數(shù)分到左邊，用DP來維護
20         }else{
21             sum[c][i] = sum[c][i - 1];
22         }
23         if (tree[c][i] == as[mid]){
24             if (lm){
25                 lm--;
26                 sum[c][i]++;
27                 tree[c + 1][lp++] = tree[c][i];
28             }else
29                 tree[c + 1][rp++] = tree[c][i];
30         } else if (tree[c][i] < as[mid]){
31             sum[c][i]++;
32             tree[c + 1][lp++] = tree[c][i];
33         } else{
34             tree[c + 1][rp++] = tree[c][i];
35         }
36     }
37     if (l == r)return;
38     build(c + 1, l, mid);
39     build(c + 1, mid + 1, r);
40 }
41 int query(int c, int l, int r, int ql, int qr, int k){
42     int s;//[l, ql)內(nèi)將被劃分到左子樹的元素數(shù)目
43     int ss;//[ql, qr]內(nèi)將被劃分到左子樹的元素數(shù)目
44     int mid = (l + r) >> 1;
45     if (l == r){
46         return tree[c][l];
47     }
48     if (l == ql){//這里要特殊處理！
49     s = 0;
50     ss = sum[c][qr];
51     }else{
52         s = sum[c][ql - 1];
53         ss = sum[c][qr] - s;
54     }//假設要在區(qū)間[l,r]中查找第k大元素，t為當前節(jié)點，lch，rch為左右孩子，left，mid為節(jié)點t左邊界和中間點。
55     if (k <= ss){//sum[r]-sum[l-1]>=k，查找lch[t],區(qū)間對應為[ left+sum[l-1], left+sum[r]-1 ]
56         return query(c + 1, l, mid, l + s, l + s + ss - 1, k);
57     }else{//sum[r]-sum[l-1]<k,查找rch[t]，區(qū)間對應為[ mid+1+l-left-sum[l-1], mid+1+r-left-sum[r] ]
58         return query(c + 1, mid + 1, r, mid - l + 1 + ql - s, mid - l + 1 + qr - s - ss,k - ss);
59     }
60 }
61 int main(){
62     int i, j, k;
63     while(~scanf("%d%d", &n, &m)){
64         for (i = 1; i <= n; i++){
65             scanf("%d", &a[i]);
66             tree[0][i] = as[i] = a[i];
67         }
68         sort(as + 1, as + 1 + n);
69         build(0, 1, n);
70         while(m--){
71             scanf("%d%d%d",&i,&j,&k);// i,j分別為區(qū)間起始點，k為該區(qū)間第k大的數(shù)。
72             printf("%d\n", query(0, 1, n, i, j, k));
73         }
74     }
75     return 0;
復制代碼

76 }

 

    本站是提供個人知識管理的網(wǎng)絡存儲空間，所有內(nèi)容均由用戶發(fā)布，不代表本站觀點。請注意甄別內(nèi)容中的聯(lián)系方式、誘導購買等信息，謹防詐騙。如發(fā)現(xiàn)有害或侵權內(nèi)容，請點擊一鍵舉報。
    轉藏 分享 獻花（0）

    0條評論

    發(fā)表

    請遵守用戶 評論公約

    類似文章 更多