划分树

定义

划分树是一种基于线段树的数据结构。主要用于快速求出序列区间的第k大值。

划分树的根节点存储原数列
每个节点的左子节点存储它元素中较小的一半，右子节点存储它元素中较大的一半
并且同一个节点中元素的排列和原数列一样

例如1，5，3，4，2构成的划分树如下图所示

具体操作

• 建树

  我们发现每层所有节点的元素个数和都是原数列长度
  所以我们可以用数组按层存储

  我们用partition_tree[i][j]存储第i层的第j个元素,用num[i][j]表示在第i层的第j个元素之前有多少节点进入了它所在节点的左子树(包括它自己)
  由于每个子节点建立要用到父节点的元素,所以我们可以递归按中序建树

  void build(int deep,int l,int r){//构造第deep层,区间为[l,r]的子节点 
      if(l==r)return;
      int mid=(l+r)>>1,x=1;//x记录有多少和sorted[mid](当前节点元素的中位数)一样大的数进入左子节点 
      for(int i=mid-1;i>=l;i--,x++){
          if(sorted[i]<sorted[mid])break;//sorted是排好序的数组 
      }
      for(int i=l,j=l,k=mid+1;i<=r;i++){
          num[deep][i]=(i==l)?0:num[deep][i-1];
          if(partition_tree[deep][i]<sorted[mid]||(partition_tree[deep][i]==sorted[mid]&&(x--)>0)){//进入左子节点 
              partition_tree[deep+1][j++]=partition_tree[deep][i],num[deep][i]++;
          }
          else partition_tree[deep+1][k++]=partition_tree[deep][i];//进入右子节点 
      } 
      build(deep+1,l,mid);//构建子节点 
      build(deep+1,mid+1,r);
  }

• 查询（区间第k大）

  我们如果要查找某一层[l,r]的第k大
  首先我们可以求出l之前有多少个数进入了左子节点x1=num[deep][l-1]
  和[l,r]中有多少个数进入了左子节点x2=(num[deep][r]-num[deep][l-1])

  如果x2$ge$k,我们去它的左子节点找[l,r]在左子节点中所在区间的第k大即可
  因为l之前有x1个数进入左子节点,[l,r]有x2个数进入左子节点,并且左子节点区间为[L,mid]
  所以[l,r]在左子节点中所在区间为[L+x1,L+x1+x2-1](x1+x2=num[deep][r])

  如果x2<k,我们去它的右子节点找[l,r]在右子节点中所在区间的第k-x2大即可
  因为l之前有l-L-x1个数进入右子节点,[l,r]有r-l+1-x2个数进入右子节点,并且右子节点的区间为[mid+1,R]
  所以[l,r]在右子节点中所在区间为[l-L-x1+mid+1,l-L-x1+mid+1+(r-l+1-x2)-1]=[l-L-x1+mid+1,r-L-x1+mid+1-x2](-x1-x2=-num[deep][r])

  如果是叶子节点直接返回即可

  int query(int deep,int L,int R,int l,int r,int k){//询问[l,r]中第k大的数,L,R为当前节点的区间范围 
      if(L==R)return partition_tree[deep][L];//叶子节点就直接返回 
      int mid=(L+R)>>1,x1=(L==l)?0:num[deep][l-1],x2=num[deep][r]-x1;//x1表示当前节点中在l之前有多少点进入了左子树,x2表示当前节点在[l,r]中有多少点进入左子树 
      if(x2>=k)return query(deep+1,L,mid,x1+L,L+num[deep][r]-1,k);//在左子树中
      else return query(deep+1,mid+1,R,l-L-x1+mid+1,mid+r-L-num[deep][r]+1,k-x2);//在右子树中 
  }

例题hdu2665 Kth number

#include<cstdio>
#include<algorithm>
using namespace std;
#define maxn 100005
int a[maxn],sorted[maxn],partition_tree[20][maxn],num[20][maxn],n,m;
void build(int deep,int l,int r){//构造第deep层,区间为[l,r]的子节点 
    if(l==r)return;
    int mid=(l+r)>>1,x=1;//x记录有多少和sorted[mid](当前节点元素的中位数)一样大的数进入左子节点 
    for(int i=mid-1;i>=l;i--,x++){
        if(sorted[i]<sorted[mid])break;//sorted是排好序的数组 
    }
    for(int i=l,j=l,k=mid+1;i<=r;i++){
        num[deep][i]=(i==l)?0:num[deep][i-1];
        if(partition_tree[deep][i]<sorted[mid]||(partition_tree[deep][i]==sorted[mid]&&(x--)>0)){//进入左子节点 
            partition_tree[deep+1][j++]=partition_tree[deep][i],num[deep][i]++;
        }
        else partition_tree[deep+1][k++]=partition_tree[deep][i];//进入右子节点 
    } 
    build(deep+1,l,mid);//构建子节点 
    build(deep+1,mid+1,r);
}
int query(int deep,int L,int R,int l,int r,int k){//询问[l,r]中第k大的数,L,R为当前节点的区间范围 
    if(L==R)return partition_tree[deep][L];//叶子节点就直接返回 
    int mid=(L+R)>>1,x1=(L==l)?0:num[deep][l-1],x2=num[deep][r]-x1;//x1表示当前节点中在l之前有多少点进入了左子树,x2表示当前节点在[l,r]中有多少点进入左子树 
    if(x2>=k)return query(deep+1,L,mid,x1+L,L+num[deep][r]-1,k);//在左子树中
    else return query(deep+1,mid+1,R,l-L-x1+mid+1,mid+r-L-num[deep][r]+1,k-x2);//在右子树中 
}
void work(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",a+i),partition_tree[0][i]=sorted[i]=a[i];
    sort(sorted+1,sorted+1+n);
    build(0,1,n);
    int l,r,k;
    for(int i=0;i<m;i++){
        scanf("%d%d%d",&l,&r,&k);
        printf("%d
",query(0,1,n,l,r,k));
    }
}
int main(){
//    freopen("input.txt","r",stdin);
    int t;scanf("%d",&t);
    while(t--)work();
    return 0;
}