划分树 详解及模板

划分树的目的：求区间内第K大数。对于此类问题，暴力的话直接对区间进行sort，但是时间复杂度很高，如果q次查询的话嘛，时间复杂度O(q∗n∗log(n))$O(q\ast n\ast log(n))$
为了降低时间复杂度，我们采取将数组构造成树的形式，这样,时间复杂度能降到log(n)$log(n)$,但是空间复杂度为n∗log(n)$n\ast log(n)$.
建树规则为：小于等于中位数的放在左子树，大于中位数的放在右子树，以1−9$1-9$的随机数组为例，建树方式如下：

这样，我们查询的时候只需要对构造好的树像线段树一样，不断向下递归到指定区间即可
需要注意的是以下几点

• 划分树的构造需要平衡左右子树的元素个数，也就是说，如果是[1,1,1,1,1,1,1,1]$[1,1,1,1,1,1,1,1]$（8个1）$（8个1）$这样的数组，进入左右子树的元素都得是4个，这样才能避免极端数据卡时间的情况。
  为了处理这种特殊情况，我们在还没有进行划分之前，先假设中值左边的数据都小于中值。 即 设置一个flag标记，令flag=mid−l+1$flag=mid-l+1$,其中flag$flag$为区间内**元素个数**的一半，l$l$为区间左端点，mid−l+1$mid-l+1$即为区间内元素的一半（因为区间[l,r]$[l,r]$包含了l和r$l和r$两个端点）。

  如果当前的数小于中值,就使flag$flag$减一.

  如果结果如我们假设的那样，那么flag$flag$最后一定等于1，否则，就说明中值的数量不唯一。那么在下面进行的时候，如果还剩flag$flag$>1，就先把中值放在左子树，直到flag$flag$为0，如果仍还有中值，就把剩下的放进右子树。

• 建树是分层的，所以我们要用二维数组去存储，第一维只需要20就够了，因为100000的数据量的话，它的层数为log(n)$log(n)$。
• 划分的数永远存放在它的下一层,因为当前层的数据是由上一层划分来的（小于等于放入左子树，大于放入右子树）
• 为了查找，我们还需要设一个二维数组cnt$cnt$，其中，cnt[i][j]$cnt[i][j]$ 存的是 第 i 层，当前划分区间[l,r]$[l,r]$里进入左子树的个数.这样，当我们查询的时候，就能根据cnt$cnt$数组提供的信息判断当前查询的区间是在下一个左区间还是右区间。

附上建树+查询的代码

#define _mid(a,b) ((a+b)/2)

using namespace std;
typedef long long ll;
const int maxn =  1e5+10;
const int INF = 0x3f3f3f3f;
int sorted[maxn];
int cnt[20][maxn];
int tree[20][maxn];
void build(int l,int r,int k){
    if(r==l)          //如果区间内只有一个数，返回
        return;
    int mid = _mid(l,r),flag = mid-l+1;//求出flag
    for(int i=l;i<=r;i++)
        if(tree[k][i] < sorted[mid])  //sorted代表排序好了的数组
            flag -- ;
    int bufl = l,bufr = mid+1;
    for(int i=l;i<=r;i++){
        cnt[k][i] = (i==l)?0:cnt[k][i-1];   //初始化
        if(tree[k][i]<sorted[mid] || tree[k][i]==sorted[mid]&&flag>0){//如果有多个中值
            tree[k+1][bufl++] = tree[k][i];
            cnt[k][i]++;     //进入左子树
            if(tree[k][i] == sorted[mid])
                flag--;
        }
        else                                     //进入右子树
            tree[k+1][bufr++] = tree[k][i];
    }
    build(l,mid,k+1);
    build(mid+1,r,k+1);
}

int ask(int k,int sl,int sr,int l,int r,int x){
    if(sl==sr)
        return tree[k][sl];
    int cntl;
    cntl = (l==sl)?0:cnt[k][l-1];    //是否和查询区间重合
    int cntl2r = cnt[k][r]-cntl;     //计算l到r有cntl2r个数进入左子树
    if(cntl2r >= x)                  //如果大于当前查询的k则进入左子树（因为左子树中最大的数大于第k大的数）
        return ask(k+1,sl,_mid(sl,sr),sl+cntl,sl+cnt[k][r]-1,x);
    else{                            //否则进入右子树
        int lr = _mid(sl,sr) + 1 + (l-sl-cntl);
        return ask(k+1,_mid(sl,sr)+1,sr,lr,lr+r-l-cntl2r,x-cntl2r);
    }
}