划分树学习笔记

参考链接：http://blog.renren.com/blog/367737224/728617495

http://www.cppblog.com/MatoNo1/archive/2011/06/27/149604.aspx

在你看这篇文章之前，我认为你已经学习过线段树了。。。

（1）划分树是干什么的？给出一个长度为n的数列a:a[1],a[2]……a[n]。划分树是求一个给定区间[L,R]中的第K小的数。

比如n=10:0 5 2 7 5 4 3 8 7 7,L=2,R=6,K=2,则应输出4。

（2）划分树的建立：划分树采用递归建树，设当前建立数组a的[L,R]区间，在建立的过程中记录一个数组tot[dep][i]，表示在第dep层，在[L,i]区间的数中，分到当前层(就是第dep层)的左子树的数的个数。建立时，首先将[L,R]区间的数升序排序，找到中位数mid=(L+R)>>1，则左子树的数字个数为Lnum=mid-L+1,右子树的数字个数为Rnum=R-mid。扫描排序后的区间，小于中位数的分到左子树，大于中位数的分到右子树，等于中位数的看左子树放满没（即放够Lnum个没），没有满放到左子树，否则放到右子树。接着递归建立子树，L=R时返回。

（3）查找：在大区间[a,b]中查找小区间[L,R]中的第K大数，设当前层为dep，x=tot[dep][L-1],y=tot[dep][R]-tt[dep][L-1],xx=L-a-x,yy=R-L+1-y，则x,y表示区间[a,L-1]和[L,R]中分到左子树的数的个数，xx,yy表示区间[a,L-1]和[L,R]中分到右子树的数的个数。若y>=K，则在左子树中递归查找,L=a+x,R=a+x+y-1,K不变;否则在右子树中递归查找L=mid+1+xx,R=mid+1+xx+yy-1,K=K-y。L=R时返回。

 1  const int MAX=100005;
 2  
 3  struct Node
 4  {
 5      int L,R;
 6  };
 7  
 8  struct HuaFen_tree
 9  {
10      Node a[MAX<<2];
11      int s[MAX],t[35][MAX],tot[35][MAX];
12  
13      void input(int n)
14      {
15          int i;
16          for(i=1;i<=n;i++)
17          {
18              scanf("%d",&s[i]);
19              t[1][i]=s[i];
20          }
21          sort(s+1,s+n+1);
22      }
23      void build(int dep,int u,int L,int R)
24      {
25          a[u].L=L;
26          a[u].R=R;
27          if(L==R) return;
28          int i,mid=(L+R)>>1;
29          int sameNum=mid-L+1;
30          for(i=L;i<=R;i++) if(t[dep][i]<s[mid]) sameNum--;
31          int LL=L,LR=mid,RL=mid+1,RR=R;
32          int Lnum=0,Rnum=0;
33          for(i=L;i<=R;i++)
34          {
35              if(i==L) tot[dep][i]=0;
36              else tot[dep][i]=tot[dep][i-1];
37              if(t[dep][i]<s[mid])
38              {
39                  tot[dep][i]++;
40                  t[dep+1][LL+Lnum]=t[dep][i];
41                  Lnum++;
42              }
43              else if(t[dep][i]>s[mid])
44              {
45                  t[dep+1][RL+Rnum]=t[dep][i];
46                  Rnum++;
47              }
48              else
49              {
50                  if(sameNum>0)
51                  {
52                      sameNum--;
53                      tot[dep][i]++;
54                      t[dep+1][LL+Lnum]=t[dep][i];
55                      Lnum++;
56                  }
57                  else
58                  {
59                      t[dep+1][RL+Rnum]=t[dep][i];
60                      Rnum++;
61                  }
62              }
63          }
64          build(dep+1,u<<1,LL,LR);
65          build(dep+1,u<<1|1,RL,RR);
66      }
67  
68      //在区间[a[u].L,a[u].R]这个区间中查找[L,R]中的第K大值
69      int query(int dep,int u,int L,int R,int K)
70      {
71          if(L==R) return t[dep][L];
72          int x,y,xx,yy,_L,_R,mid=(a[u].L+a[u].R)>>1;
73          if(L==a[u].L) x=0;
74          else x=tot[dep][L-1]; //x为[a[u].L,L-1]中分到左边的
75          y=tot[dep][R]-x;      //y为[L,R]中分到左边的
76          if(y>=K)
77          {
78              _L=a[u].L+x;
79              _R=a[u].L+x+y-1;
80              return query(dep+1,u<<1,_L,_R,K);
81          }
82          else
83          {
84              xx=L-a[u].L-x;  //xx是[a[u].L,L-1]中分到右边的
85              yy=R-L+1-y;     //yy是[L,R]中分到右边的
86              _L=mid+1+xx;
87              _R=mid+1+xx+yy-1;
88              return query(dep+1,u<<1|1,_L,_R,K-y);
89          }
90      }
91  };
92