划分树

const int maxn = 100020;
 int Left[20][maxn], sorted[maxn], tree[20][maxn];
 //left[i][j]表示第i层前j个数中有几个被分到左子树中
 //sorted表示排好序的
 //tree[i][j]记录第i层第j个元素
 
 void build_tree( int L, int R, int v )
 {
  int i;
     int mid = ( L + R ) /2;
     if( L == R ) return;
     int m = sorted[mid];
     int same = mid - L + 1;     // same表示和m = sorted[mid] 相等且分到左边的
     for( i = L; i <= R; i++ )
         if( tree[v][i] < m ) same--;
     int lpos = L;
     int rpos = mid+1;
     int ss = 0;
     for( i = L; i <= R; i++ )
     {
         if( i == L ) Left[v][i] = 0;
         else Left[v][i] = Left[v][i-1];
         if( tree[v][i] < m )
         {
             tree[v+1][lpos++] = tree[v][i];
             Left[v][i]++;
         }
         else if( tree[v][i] > m )
         {
             tree[v+1][rpos++] = tree[v][i];
         }
         else
         {
             if( ss < same )
             {
                 tree[v+1][lpos++] = tree[v][i];
                 Left[v][i]++;
                 ss++;
             }
             else tree[v+1][rpos++] = tree[v][i];
         }
     }
     build_tree( L, mid, v + 1 );
     build_tree( mid + 1, R, v + 1 );
 }
 
 int query( int L, int R, int l, int r, int k, int v )
 {
     int mid = ( L + R ) /2 ;
     if( l == r ) return tree[v][l];
     int off;      // off表示 [ L, l-1 ]有多少个分到左边
     int cnt;      // cnt表示 [ l, r ]有多少个分到左边
     if( l == L )
     {
         off = 0;
        cnt = Left[v][r];
     }
     else
     {
         off = Left[v][l-1];
         cnt = Left[v][r] - Left[v][l-1];
     }
     if( cnt >= k ) //有多于k个分到左边,显然去左儿子区间找第k个
     {
         int lnew = L + off;
         int rnew = lnew + cnt - 1;
         return query( L, mid, lnew, rnew, k, v + 1 );
     }
     else
     {
         off = l - L - off;      // off表示 [ L, l-1 ]有多少个分到右边
         k = k - cnt;
        cnt = r - l + 1 - cnt;  // cnt表示 [ l, r ]有多少个分到右边
         int lnew = mid + 1 + off;
         int rnew = lnew + cnt - 1;
         return query( mid + 1, R, lnew, rnew, k, v + 1 );
     }
 }
 

 

 

 

最近在学划分树。。。。

 

 

 划分树给我的感觉就是貌似除了求序列区间的第几大值之外，好像没什么用处了。。

划分树是一种基于线段树的数据结构。主要用于快速求出(在log(n)的时间复杂度内）序列区间的第k大值。

 

划分树就是把一个区间分成左，右两个区间。首先将原数组排序，比中间值小的进入左区间，比中值大的进入右区间，最后根据条件查询。。

 

第一步：

建树：

学过线段树的童靴应该很容易建树，没学过的建议去看一下。。。

 其实建树很简单的，将输入的数组排序，在进行二分递归建树。。。

 

 

第二步：

查询：

先给出一个例子，8个数字分别为{6 3 7 2 4 1 8 5}，于是我们的根为：

6 3 7 2  4 1 8 5

之后选出前4小的作为左子树，选出后4大的作为右子树。

3 2 4 1 | 6 7 8 5

但是在左子树和右子树中数字的顺利依然按照原序列中的顺序。

考察询问[3,7]中第2小的数字，那么对应根中：

6 3 7 2  4 1 8 5

我们发现红色区域中有3个数字{2,4,1}都属于左子树，那么说明红色区间中前3小的数字都在左子树：

3 2 4 1 | 6 7 8 5

于是下一步我们只需要在左子树中查找第2小的数字就可以了。

我们令操作Find(l,r,s,t,k,deep)表示在第deep层的[l,r]区间中查找[s,t]区间中的第k值。那么例子中的操作为Find(1,8,3,7,2,0)，而第二次在左子树中的操作就是Find(1,4,2,4,3,1)。

那么如何才能确定子树中的操作Find(l’,r’,s’,t’,k’,deep+1)呢？对于结点，我们记录suml[i]记录当前区间中前i个数字有几个被分配到左子树。那么cnt=suml[t]-suml[s-1]就是查询区间[s,t]中到左子树的个数。

如果cnt>=k，那么下一次的查找必然在左子树中，s’和t’分别为l+sum[s]-sum[l-1]和l+sum[t]-sum[l-1]，k’=k，而[l’,r’]=[l,mid]。

如果cnt<k，那么下一次查找必然在右子树总，s’和t’分别为mid+s-(sum[s]-sum[l-1])和mid+s-(sum[t]-sum[l-1])，k=k-cnt，而[l’,r’]=[mid+1,r]。

直到区间[l,r]满足l=r，那么返回原序列中第l个数字。

 

 

这是小弟第一次写的微博，引用了某位大神的说法，求各位路过的大神指点我这个小小小菜鸟。。。