划分树小结

迈不过友情╰ 2022-08-01 14:56 135阅读 0赞

最近学习了一下划分树，下面总结一下。

我们在求区间最值的时候，一般可以用线段树解决，但是如果要求区间第k小或者第k大值的话线段树就有点力不从心了，这是我们可以用划分树来解决。划分树利用了快速排序的思想，首先是建树，我们设当前区间的中位数为mid，(为了能快速找到区间的中位数，我们一般先对原序列做一次排序)则我们将区间中比mid小的放入左子树，将区间中比mid大数的放入右子树中，和mid相等的要讨论一下，有些需要放到左子树中，其他的放到右子树中，注意我们将数字放入子树的时候其相对顺序是不变的。这样我们一层一层下去，每次区间都减半，则空间消耗为O（nlogn）。下面看一个例子。

假设序列长度为9，依次为 3 5 7 3 4 9 4 2 5，怎我们看看建树完成后是什么样子。

sort\[ \]\[2  3  3  4  4  5  5  7  9\]

tree\[0\]\[3  5  7  3  4  9  4  2  5\]

tree\[1\]\[3  3  4  4  2\]\[5  7  9  5\]

tree\[2\]\[3  3  2\]\[4  4\]\[5  5\]\[7   9\]

tree\[3\]\[3  2\]\[3\]\[4\]\[4\]\[5\]\[5\]\[7\]\[9\]

tree\[4\]\[2\]\[3\]\[3\]\[4\]\[4\]\[5\]\[5\]\[7\]\[9\]

好了，树建完了，接下来就是最关键的查询了，我们设函数query（p,l,r,s,t,k）表示在第p层子树区间范围在\[l,r\]的子树中查找区间\[s,t\]中的第k小值。我们在每一颗子树中设sum\[i\]表示区间\[l,i\]范围内有多少个数字被放到了左子树中，那么我们容易得到，sum\[t\]-sum\[s-1\]表示在区间\[s,t\]有多少个树被放入了左子树中，我们不妨设这个值为num，若k<=num，我们就可以知道我们要找的数一定在左子树中，否则一定在右子树中，我们接下来只要继续往下遍历，当l==r的时候我们就可以确定我们要找的数，容易知道这一步骤的复杂度为O(log n)，现在关键的一点就是如何再往下便利的时候确定ls,t的值。这个其实自己画画图就很容易推出来的，下面只写结论，这里先设区间\[l,s-1\]中被放入左子树的数有snum个,当前区间的中点为mid，

则若k<=num,我们返回query(p+1,l,mid,l+snum,l+sum\[t\]-1,k),(要找的数在左子树上)

否则，我们返回query(p+1,mid+1,r,mid+1\-l+s-snum,mid+1-l+t-sum\[t\],k-num);（要找的数在右子树上）

下面再举个例子，数和上面一样

我们现在要找到区间\[2,7\]中的第3小数。

sort\[ \]\[2  3  3  4  4  5  5  7  9\]

tree\[0\]\[3  5  7  3  4   9  4  2  5\]

tree\[1\]\[3  3  4  4  2\]\[5  7   9  5\]

tree\[2\]\[3  3  2\]\[4  4\]\[5  5\]\[7  9\]

tree\[3\]\[3  2\]\[3\]\[4\]\[4\]\[5\]\[5\]\[7\]\[9\]

tree\[4\]\[2\]\[3\]\[3\]\[4\]\[4\]\[5\]\[5\]\[7\]\[9\]

以上橙黄色背景的数字即为我们要求的范围。

我们首先在第一层树上寻找，即query(0,1,9,2,7,3),我们发现在\[2,7\]区间中有3个数被放入了左子树，满足k<=num，所以我们往左子树中找，调用query(1,1,5,2,4,3)。

在第二层树中我们发现区间\[2,4\]只有一个数被放入左子树，所以我们要找的数一定在右子树中，调用query(2,4,5,4,5,2)。

在第三层树中，我们发现区间\[4,5\]只有一个数被放入左子树，同理我们应该往右子树找，调用query(3,5,5,5,5,1)。现在可以发现l==r，则我们可以确定已经找到了要找的数，则返回4即可，我们可知在区间\[2,7\]上第3小的数为4。

基础的划分树就到这里，下面给出我的代码：

#include <iostream>
    #include <string.h>
    #include <stdio.h>
    #include <algorithm>
    #define maxn 100010
    #define mid ((l+r)>>1)
    using namespace std;
    int t[20][maxn],sum[20][maxn];
    int a[maxn],as[maxn];
    //以下为查找区间第k小划分树
    void build(int p,int l,int r)
    {
        int lm=0,i,ls=l,rs=mid+1;//lm表示应被放入左子树且与中位数相等的数有多少个，ls为左子树的起始位置，rs为右子树的起始位置
        for(i=mid;i>=l;i--) //求lm
        {
            if(as[i]==as[mid])
            lm++;
            else
            break;
        }
        for(i=l;i<=r;i++)
        {
            if(i==l)//这里要特殊讨论
            sum[p][i]=0;
            else
            sum[p][i]=sum[p][i-1];
            if(t[p][i]==as[mid])//若与中位数相等则判断是否应该被放入左子树
            {
                if(lm)
                {
                    lm--;
                    sum[p][i]++;
                    t[p+1][ls++]=t[p][i];
                }
                else
                t[p+1][rs++]=t[p][i];
            }
            else if(t[p][i]<as[mid])//查找区间第K大即为>
            {
                sum[p][i]++;
                t[p+1][ls++]=t[p][i];
            }
            else
            t[p+1][rs++]=t[p][i];
        }
        if(l==r)
        return;
        build(p+1,l,mid);
        build(p+1,mid+1,r);
    }
    int query(int p,int l,int r,int ql,int qr,int k)
    {
        int s,ss;//s表示l到ql-1的区间内放入左子树的个数，ss表示区间[ql,qr]被放入左子树的个数
        if(l==r)//找到所求的数
        return t[p][l];
        if(ql==l)
        s=0,ss=sum[p][qr];
        else
        s=sum[p][ql-1],ss=sum[p][qr]-s;
        if(k<=ss)//要找的数在左子树中
        return query(p+1,l,mid,l+s,l+sum[p][qr]-1,k);
        else//要找的数在右子树中
        return query(p+1,mid+1,r,mid+1-l+ql-s,mid+1-l+qr-sum[p][qr],k-ss);
    }