划分树：_牛客博客

话说这个东西大概要退出历史的舞台了吧。。。
专用功能，静态查询区间第k大，主席树完全可以搞定啊，还能搞点别的。
不过思想还是要学一下的。
以下转自：https://blog.csdn.net/Akatsuki__Itachi/article/details/80030929
有这样一类题目，求的是区间内的第k大数。

划分树的定义就是对整体的区间进行划分，把相对于原来序列中较小的值放在左子树，较大的放在右子树，最后按照它的性质进行查询以此找到要查询的区间里的第k大数。
logn 查询。

例图（图是偷的~~~）

1.建树
建树是一个不停递归的过程

第一步： 首先我们要根据排序后的数组找到当前层数的中值（中值即中位数。注意，是中位数，不是中间的数），将没有排序的序列（即输入的原序列）里面的数这样安排：小于中位数的放进左子树，大于等于中位数的放进右子树。当然了，这是针对中值只有唯一一个时候的做法，一会再说多个中值应该怎么处理。

第二步： 对于每一个子区间，我们都采用第一步的方法去划分，直到左右区间相等的时候，即为终止递归的条件。

第三步： 在我们向左子树里放数的时候，我们还要统计出区间 [left,right ] 里有多少个数进入了左子树（这个主要用于查询操作）。

在划分树的时候，有几点需要注意：
1.建树是分层的，所以我们要用二维数组去存储，第一维只需要20就够了，因为100000的数据量的话，它的层数为logN。
2.划分的标准是中值，在第一步里已经特别强调过。
3.划分的数永远存放在它的下一层，为什么呢？下面举个例子模拟一下过程就知道了。

那么下面先列出我们要用到的数组：

const int MAXL(1e5);
int tree[20][MAXL+50];//第一维代表当前的树的层数，
                      //第二维代表这一层经过划分后的序列值
int toLeft[20][MAXL+50];//第一维代表当前的树的层数，
                      //第二维代表当前层区间[left,right]进入左子树的数目
int sorted[MAXL+50];//将初始序列排序后的数组

按照图中给出的原始序列为
4 2 5 7 1 8 3 6

排序后的序列为
1 2 3 4 5 6 7 8
那么我们tree [ 0 ]保存的应该是原始序列
并且得到toLeft [ 0 ] 的序列

tree[0] = 4 2 5 7 1 8 3 6
toLeft[0]= 1 2 2 2 3 3 4 4

再次强调一遍
toLeft [ i ] [ j ] 存的是第 i 层，当前划分区间【 left , right 】里进入左子树的个数
（什么叫当前划分区间呢？举个例子：一开始数组长度为8，建树时第一层区间肯定是【1，8】，那么接下来我们要递归建树，【1，8】分成两部分分别为【1，4】，【5，8】，那么要对新区间【1，4】操作时，我们就称这时候的【1，4】为当前的划分区间）
至于为什么要这么存，一会说查询的时候就知道了。

模拟一下划分过程
首先是第一层，找到中值4 （ sorted[ ( left + mid) / 2 ] ）
那么tree [ 1 ] 和toLeft [ 1 ] 应该是

tree[1]= 4 2 1 3 5 7 8 6
toLeft[1]= 0 1 2 2 1 1 1 2

可能这里有人注意到问题了，为什么把4划分到了左区间？上面不是说大于等于中值的划分到右区间吗？别急-

第二层，分别对左子树和右子树按照上述的方法划分

tree[2]= 2 1 4 3 5 6 7 8
toLeft[2]= 0 1 0 1 1 1 1 1

在这里再啰嗦地解释一下这一组的toLeft数组
很明显这一组的 2 1 ， 4 3 ， 5 6 ， 7 8
分别在左右左右子树
那么对于左子树里的 2 1这个小区间，进入下一层左子树的数分别为 0 1
对于右子树 4 3 这个小区间，进入下一层左子树的数分别为 0 1
…
…
第三层

tree[3]= 1 2 3 4 5 6 7 8
toLeft[3]= 0 0 0 0 0 0 0 0

下面开始说另外一个要注意的问题：有多个中值怎么办？

因为我们要使得左右区间的数量尽可能的均等
所以在这里，我们用一种特殊的处理方法。

在还没有进行划分之前，我们先假设中值左边的数据都小于中值。
即设置一个suppose = mid - left + 1。
如果当前的数小于中值,就使suppose减一，即

if(tree[level][i]<sorted[mid]
suppose–;

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

再举个例子增深理解：
3 3 4 4 4 5 7
中值为4，左子树要放4个（(1+7)/2），右子树放3个
处理后的suppose为2
那么遇到第一个4，放进左子树，suppose=1;
遇到第二个4，放进左子树，suppose=0；
遇到第三个4,这时suppose已经等于0，所以放进右子树。

在建好树之后，接下来就是查询的问题。
假设初始大区间为【left , right】，要查询的区间为【qLeft , qRight】
现在要查询区间【qLeft , qRight】的第k大数

我们的想法是，先判断【qLeft , qRight】在【left , right】的哪个子树中，然后找出对应的小区间和k，然后递归查找，直到小区间qLeft==qRight时为止。

那如何解决这个问题呢？这时候前面记录的进入左子树的元素个数就派上用场了。通过之前的记录可以知道，在区间【left , qLeft】中有toLeft [ level ] [ qLeft - 1 ] 个元素进入了左子树，记它为lef，同理，在区间【left , qRight】中有toLeft [ level ] [ qRight ] 个元素进入了左子树，记它为rig ，所以在区间【qLeft , qRight】之间就有 rig - lef 个元素进入了左子树，记为 toLef。如果 toLef>= k ，说明第k大元素肯定进入了左子树，那么就进入左子树查找，否则进入右子树查找。

那么接下来要解决确定小区间的问题：

如果进入的是左子树，那么小区间就应该是
【 left +( [ left,qLeft-1] )进入左子树的数目，left +（ [ left,qRight ] ）进入左子树的数目-1】
即：【 left + lef , left + lef + tolef-1 】,并且，这时候k的值不用变化。

如果进入的是右子树，那么小区间就应该是
【 mid +( [ left,qLeft-1] )进入右子树的数目+1，mid +（ [ left,qRight ] ）进入右子树的数目】
即：【 mid + qLeft - left -lef + 1 , mid + qRight - left - toLef - lef + 1 】
同时，这里的k要发生变化，变为k-（【qLeft , qRight】进入左子树的元素个数）
即 k-toLef

其中mid = ( left + right ) / 2

这里的区间式子很长，需要仔细思考。

以下例题，totleft数组表示某层 1–i 分入左区间数的个数，建树，查询稍有不同，总体思想一致。
例题：K-th Number POJ - 2104

You are working for Macrohard company in data structures department. After failing your previous task about key insertion you were asked to write a new data structure that would be able to return quickly k-th order statistics in the array segment.
That is, given an array a[1…n] of different integer numbers, your program must answer a series of questions Q(i, j, k) in the form: “What would be the k-th number in a[i…j] segment, if this segment was sorted?”
For example, consider the array a = (1, 5, 2, 6, 3, 7, 4). Let the question be Q(2, 5, 3). The segment a[2…5] is (5, 2, 6, 3). If we sort this segment, we get (2, 3, 5, 6), the third number is 5, and therefore the answer to the question is 5.
Input
The first line of the input file contains n — the size of the array, and m — the number of questions to answer (1 <= n <= 100 000, 1 <= m <= 5 000).
The second line contains n different integer numbers not exceeding 10 9 by their absolute values — the array for which the answers should be given.
The following m lines contain question descriptions, each description consists of three numbers: i, j, and k (1 <= i <= j <= n, 1 <= k <= j - i + 1) and represents the question Q(i, j, k).
Output
For each question output the answer to it — the k-th number in sorted a[i…j] segment.
Sample Input
7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3
Sample Output
5
6
3
Hint
This problem has huge input,so please use c-style input(scanf,printf),or you may got time limit exceed.

静态查询某个区间从小往大数第K个。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<queue>
#define ll long long
#define llu unsigned ll
using namespace std;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const int maxn=100100;
int tree[20][maxn];//表示每层每个位置的值
int sorted[maxn];//已经排好序的数
int totleft[20][maxn];//totleft[p][i] 表示第p层，
                      //1--i 分入左区间的数的个数
void build(int l,int r,int deep)
{
    if(l==r) return ;
    int mid=(l+r)>>1;
    int same=mid-l+1;//表示等于中间值而且被分入左边的个数
    for(int i=l;i<=r;i++)
        if(tree[deep][i]<sorted[mid]) same--;

    int lpos=l;
    int rpos=mid+1;
    for(int i=l;i<=r;i++)
    {
        if(tree[deep][i]<sorted[mid])
            tree[deep+1][lpos++]=tree[deep][i];
        else if(tree[deep][i]==sorted[mid]&&same>0)
            tree[deep+1][lpos++]=tree[deep][i],same--;
        else
            tree[deep+1][rpos++]=tree[deep][i];

        totleft[deep][i]=totleft[deep][l-1]+lpos-l;
    }
    build(l,mid,deep+1);
    build(mid+1,r,deep+1);
}

//查询区间第K大，L,R是大区间，l，r是要查询的小区间。
int ask(int L,int R,int l,int r,int deep,int k)
{

    if(l==r) return tree[deep][l];

    int mid=(L+R)>>1;

    int cnt=totleft[deep][r]-totleft[deep][l-1];

    if(cnt>=k)
    {
        int nowl=L+totleft[deep][l-1]-totleft[deep][L-1];
        int nowr=nowl+cnt-1;
        return ask(L,mid,nowl,nowr,deep+1,k);
    }
    else
    {
        int nowr=r+totleft[deep][R]-totleft[deep][r];
        int nowl=nowr-(r-l-cnt);
        return ask(mid+1,R,nowl,nowr,deep+1,k-cnt);
    }
}

int main(void)
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&tree[0][i]);
            sorted[i]=tree[0][i];
        }
        sort(sorted+1,sorted+n+1);
        build(1,n,0);

        int l,r,k;
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&l,&r,&k);
            printf("%d\n",ask(1,n,l,r,0,k));
        }
    }
    return 0;
}