记录一下对归并树和划分树的理解

注意：这是一篇从旧博客恢复的文章。

原地址：http://freemeepo.com/acm/1410.html

归并树：在$$n\log n$$的时间内离线处理一个序列，在$$\log^3 n$$的时间查询[l, r]区间内的第K大数。

其原理就是利用归并排序+线段树。

记录下归并排序的过程，可以得到$$\log n$$个长度为$$n$$的序列，把这$$\log n$$个序列纵向展开，按照线段树的形式分解区间，每个序列是一棵线段树，但是第i个序列只保留其展开成线段树的第i层，这样我们就得到了$$\log n$$个线段树的$$\log n$$层，即一个新线段树。（第一个序列是排完序的序列，第$$\log n$$个序列是未排序的序列。）

或者说是用归并排序分割出来的区间可以正好建成一棵线段树，如下：

[1, 2, 3, 4, 5, 6, 7, 8]
[1, 3, 5, 7][2, 4, 6, 8]
[3, 5][1, 7][2, 4][6, 8]
[5][3][1][7][4][2][8][6]

3个 $$\log n$$是这么来的：

在线段树的一个节点里，找到数x是第几大数可以二分。
在线段树中找[l, r]区间需要找$$\log n$$个线段树区间，这些区间的信息合起来就可以知道某个数在[l, r]里是第几大数。
现在我们已经可以在$$\log^2 n$$内找到某个数在[l, r]区间里是第几大数，接着我们1,n二分下标，用排好序的数组的下标为mid的元素，进行上面两个操作即可。

归并树是在归并排序的过程中建好树的，而划分树正相反。

划分树：在$$n\log n$$的时间内离线处理一个序列，在$$\log n$$的时间查询[l, r]区间内的第K大数。划分树的建树依赖一个排好序的数组来辅助建树。

设初始数组为a，先对数组排好序，设排好序的数组为b，这样我们就可以知道任何一个区间[l, r]的中间值。于是我们现在对初始序列a进行建树，很显然初始序列的a[1, n]区间的中间值必然是排好序的数组的b[1, n]区间的b[n/2]的值，我们用这个值，把初始序列a分成两部分，左边都是小于等于这个值的，右边是大于这个值的。接着再对这两个区间重复上面的操作，即可得到一棵线段树。很显然，线段树的最下面一层是个有序序列，如下：

[5, 3, 1, 7, 4, 2, 8, 6]
[3, 1, 4, 2][5, 7, 8, 6]
[1, 2][3, 4][5, 6][7, 8]
[1][2][3][4][5][6][7][8]

同时，我们在处理每个区间的时候，用一个sum数组记录i左边有多少个元素进入了左区间。例如线段树第一层sum[4]记录的是第四个数左边有多少个数进入了左区间，有3、1两个数所以是2。

所以我们在查询某个区间[L, R]的时候，只需要查询sum[R]-sum[L-1]就可以知道这整个区间有多少个数进入了左边，如果数量大于等于要查询的K（要查的是第K大数的值），说明必定要去左区间继续找K，否则去右区间找K-(sum[R]-sum[L-1])。需要注意的是，查询的区间[L, R]也要相应修改。例如：设线段树区间是l和r。如果此时将要继续查询的是左区间，那么查询的区间[L, R]要修改成[l+sum[rt][L-1], l+sum[rt][R]-1]，因为有sum[rt][L-1]个数跑到了左区间的最左边，而这sum[rt][L-1]个数并不在我们要查询的[L, R]区间内。右区间同理要改成[mid+1+L-l-sum[rt][L-1], mid+1+R-l-sum[rt][R]]。而且这样的写法能够保证查询的[L, R]一定在线段树的区间[l, r]之内。

值得注意的是，在建树时要对有重复元素的情况处理一下，因为如果值为b[n/2]的元素有多个的话，必然要出现其中一部分在左区间，另一部分在右区间的情况，必须处理好这种情况而不能直接按“小于等于b[n/2]的放左边其他在右边”来处理。解决方法是先找一下有多少个元素是小于b[n/2]的，于是就可以知道剩下多少个位置是留给恰好等于b[n/2]的元素的了。

于是，我们可以在$$\log n$$的时间内完成查询操作。

模板在此：（POJ2761 POJ2104）

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cassert>
#include<climits>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<deque>
#include<list>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<numeric>
#include<iomanip>
#include<bitset>
#include<sstream>
#include<fstream>
#define debug puts("-----")
#define pi (acos(-1.0))
#define eps (1e-8)
#define inf (1<<30)
#define INF (1ll<<62)
using namespace std;
const int NV=100005;
int a[NV],sum[20][NV],s[20][NV];
void build(int l,int r,int rt=0)
{
    int mid=l+r>>1;
    int ln=l,rn=mid+1;
    int x=a[mid];
    sum[rt][l]=0;
    int cnt=mid-l+1;
    for (int i=l;i<=r;i++)
        if (s[rt][i]<x) cnt--;
    for (int i=l; i<=r; i++)
    {
        if (i>l) sum[rt][i]=sum[rt][i-1];
        if (ln<=mid&&(s[rt][i]<x||s[rt][i]==x&&cnt-->0))
            s[rt+1][ln++]=s[rt][i],sum[rt][i]++;
        else s[rt+1][rn++]=s[rt][i];
    }
    if (l<mid) build(l,mid,rt+1);
    if (mid+1<r) build(mid+1,r,rt+1);
}
int query(int k,int L,int R,int l,int r,int rt=0)
{
    if (l==r) return s[rt][l];
    int mid=l+r>>1;
    int lsum=0;
    if (L>l) lsum=sum[rt][L-1];
    int t=sum[rt][R]-lsum;
    if (t>=k) return query(k,l+lsum,l+sum[rt][R]-1,l,mid,rt+1);
    else return query(k-t,mid+1+L-l-lsum,mid+1+R-l-sum[rt][R],mid+1,r,rt+1);
}
void init(int n)
{
    for (int i=0; i<20; i++) sum[i][0]=0;
    for (int i=1; i<=n; i++) s[0][i]=a[i];
    sort(a+1,a+n+1);
    build(1,n);
}
int main()
{
    int n,m;
    cin>>n>>m;
    for (int i=1; i<=n; i++)
        scanf("%d",&a[i]);
    init(n);
    while(m--)
    {
        int l,r,k;
        scanf("%d%d%d",&l,&r,&k);
        printf("%d\n",query(k,l,r,1,n));
    }
    return 0;
}

FanZheng's Debug Blog

记录一下对归并树和划分树的理解

Comments