主席树(区间第k大)

发布于 2017-12-27  27 次阅读


题目链接:poj-2104

主席树初步涉及,如有讲的不好的地方望海涵,或者留言留下你的问题,博主会在第一时间回复。

这里引用一点别人写的比较好的博客,

主席树又称函数式线段树,顾名思义,也就是通过函数来实现的线段树,至于为什么叫主席树,那是因为是fotile主席创建出来的这个数据结构(其实貌似是当初主席不会划分树而自己想出来的另一个处理方式。。。。是不是很吊呢? ORZ...)不扯了,切入正题。

主席树就是利用函数式编程的思想来使线段树支持询问历史版本、同时充分利用它们之间的共同数据来减少时间和空间消耗的增强版的线段树。

     很多问题如果用线段树处理的话需要采用离线思想,若用主席树则可直接在线处理。故很多时候离线线段树求解可以转化为在线主席树求解。注意,主席树本质就是线段树,变化就在其实现可持久化,后一刻可以参考前一刻的状态,二者共同部分很多。一颗线段树的节点维护的是当前节点对应区间的信息,倘若每次区间都不一样,就会给处理带来一些困难。有时可以直接细分区间然后合并,此种情况线段树可以直接搞定;但有时无法通过直接划分区间来求解,如频繁询问区间第k小元素,当然,此问题有比较特殊的数据结构-划分树。其实还有一个叫做归并树,是根据归并排序实现的,每个节点保存的是该区间归并排序后的序列,因此,时间、空间复杂度都及其高, 所以一般不推荐去用。当然,主席树也是可以解决的。

这里阐述一下主席树发明者原话:

“想法是对原序列的每一个前缀[1..i]建立出一颗线段树维护值域上每个数的出现次数,然后发现这样的树是可以减的,然后就没有然后了”

主席树的每个节点对应一颗线段树,此处有点抽象。在我们的印象中,每个线段树的节点维护的树左右子树下标以及当前节点对应区间的信息(信息视具体问题定)。对于一个待处理的序列a[1]、a[2]…a[n],有n个前缀。每个前缀可以看做一棵线段树,共有n棵线段树;若不采用可持久化结构,带来的严重后果就是会MLE,即对内存来说很难承受。根据可持久化数据结构的定义,由于相邻线段树即前缀的公共部分很多,可以充分利用,达到优化目的,同时每棵线段树还是保留所有的叶节点只是较之前共用了很多共用节点。主席树很重要的操作就是如何寻找公用的节点信息,这些可能可能出现在根节点也可能出现在叶节点。

下面是某大牛的理解:所谓主席树呢,就是对原来的数列[1..n]的每一个前缀[1..i](1≤i≤n)建立一棵线段树,线段树的每一个节点存某个前缀[1..i]中属于区间[L..R]的数一共有多少个(比如根节点是[1..n],一共i个数,sum[root] = i;根节点的左儿子是[1..(L+R)/2],若不大于(L+R)/2的数有x个,那么sum[root.left] = x)。若要查找[i..j]中第k大数时,设某结点x,那么x.sum[j] - x.sum[i - 1]就是[i..j]中在结点x内的数字总数。而对每一个前缀都建一棵树,会MLE,观察到每个[1..i]和[1..i-1]只有一条路是不一样的,那么其他的结点只要用回前一棵树的结点即可,时空复杂度为O(nlogn)。


我自己对主席树的理解,是一个线段树在修改一个值的时候,它只要修改logn个节点就可以了,那么我们只要每次增加logn个节点就可以记录它原来的状态了, 即你在更新一个值的时候仅仅只是更新了一条链,其他的节点都相同,即达到共用。由于主席树每棵节点保存的是一颗线段树,维护的区间相同,结构相同,保存的信息不同,因此具有了加减性。(这是主席树关键所在,当除笔者理解了很久很久,才相通的),所以在求区间的时候,若要处区间[l, r], 只需要处理rt[r] - rt[l-1]就可以了,(rt[l-1]处理的是[1,l-1]的数,rt[r]处理的是[1,r]的数,相减即为[l, r]这个区间里面的数。

比如说(以区间第k大为例hdu2665题目戳这里http://acm.hdu.edu.cn/showproblem.php?pid=2665):

设n = 4,q= 1;

4个数分别为4, 1, 3 ,2;

ql = 1, qr = 3, k = 2;

1.建树

首先需要建立一棵空的线段树,也是最原始的主席树,此时主席树只含一个空节点,此时设根节点为rt[0],表示刚开始的初值状态,然后依次对原序列按某种顺序更新,即将原序列加入到对应位置。此过程与线段树一样,时间复杂度为O(nlogn),空间复杂度O(nlog(n))(笔者目前没有完全搞清究竟是多少, 不过保守情况下,线段树不会超过4*n)

2.更新

 我们知道,更新一个叶节点只会影响根节点到该叶节点的一条路径,故只需修改该路径上的信息即可。每个主席树的节点即每棵线段树的结构完全相同,只是对应信息(可以理解为线段树的结构完全一样,只是对应叶子节点取值不同,从而有些节点的信息不同,本质是节点不同),此时可以利用历史状态,即利用相邻的上一棵线段树的信息。相邻两颗线段树只有当前待处理的元素不同,其余位置完全一样。因此,如果待处理的元素进入线段树的左子树的话,右子树是完全一样的,可以共用,即直接让当前线段树节点的右子树指向相邻的上一棵线段树的右子树;若进入右子树,情况可以类比。此过程容易推出时间复杂度为O(logn),空间复杂度为 O(logn)。如图:

 

3.查询

先附上处理好之后的主席树, 如图:

是不是看着很晕。。。。。。笔者其实也晕了,我们把共用的节点拆开来,看下图:

啊, 这下清爽多了,一眼看下去就知道每个节点维护的是哪棵线段树了,TAT,如果早就这样写估计很快就明白了,rt[i]表示处理完前i个数之后所形成的线段树,即具有了前缀和的性质,那么rt[r] - rt[l-1]即表示处理的[l, r]区间喽。当要查询区间[1,3]的时候,我们只要将rt[3] 和 rt[0]节点相减即可得到。如图:

<

p style="margin: 10px auto; line-height: 24px; font-family: 微软雅黑, 宋体, Arial; font-size: 13px; white-space: normal; background-color: rgb(255, 255, 255);">这样我们得到区间[l, r]的数要查询第k大便很容易了,设左节点中存的个数为cnt,当k<=cnt时,我们直接查询左儿子中第k小的数即可,如果k>cnt,我们只要去查右儿子中第k-cnt小的数即可,这边是一道很简单的线段树了。就如查找[1, 3]的第2小数(图上为了方便,重新给节点标号),从根节点1向下搜,发现左儿子2的个数为1,1<2,所有去右儿子3中搜第2-1级第1小的数,然后再往下搜,发现左儿子6便可以了,此时已经搜到底端,所以直接返回节点6维护的值3即可就可以了。

这里对原博主的一些地方进行说明,主席树其实就是a【1...9】序列的所有【1...i】子序列所对应的一个个线段树,只不过这些线段树和他们上一个线段树就只有一条路径上的结点不一样,所以用t[r]-t[l-1]得到的其实就是区间[l,r]的数出现的个数的情况的记录

具体实现见代码解析

代码:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <stack>
#include <vector>
#include <queue>
#define ri(n) scanf("%d",&n)
#define oi(n) printf("%d\n",n)
#define rl(n) scanf("%lld",&n)
#define ol(n) printf("%lld\n",n)
#define rep(i,l,r) for(i=l;i<=r;i++)
#define rep1(i,l,r) for(i=l;i<r;i++)
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int epg=10-8;
const int maxn=1e5+10;
struct node
{
    int l,r,sum;
}t[maxn*40];//t用来存所有主席树
vector<int>v;
int cnt,n,m,x,y,k,a[maxn],root[maxn*40];//root数组用来记录结点编号到哪里了
int getid(int x) {return lower_bound(v.begin(),v.end(),x)-v.begin()+1;}
//获取a数组在排序去重后的数组里的位置,也有离散化的作用
void updata(int l,int r,int &x,int y,int pos)
{
    t[++cnt]=t[y],t[cnt].sum++,x=cnt;
    //主席树t[++cnt]初始化为上个主席树,然后在递归更改需要更改的左儿子还是右儿子
    if(l==r) return;
    int mid=(l+r)>>1;
    if(pos<=mid) updata(l,mid,t[x].l,t[y].l,pos);
    //要插入的数在左儿子里面
    else updata(mid+1,r,t[x].r,t[y].r,pos);
    //要插入的数在右儿子里面
}
int query(int l,int r,int x,int y,int k)
{
    if(l==r)
        return l;
    int sum=t[t[y].l].sum-t[t[x].l].sum;
    //获取主席树x,y的左儿子存储的数的个数,差值就是区间里数的个数
    int mid=(l+r)>>1;
    if(k<=sum) return query(l,mid,t[x].l,t[y].l,k);
    //要查询的k在左儿子里面
    else return query(mid+1,r,t[x].r,t[y].r,k-sum);
    //要查询的数在右儿子里面
}
int main()
{
    scanf("%d%d",&n,&m);
    cnt=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        v.push_back(a[i]);
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    //unique是去重函数,
    for(int i=1;i<=n;i++) updata(1,n,root[i],root[i-1],getid(a[i]));
    //建立n个主席树,
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&k);
        printf("%d\n",v[query(1,n,root[x-1],root[y],k)-1]);
        //查询出来是第几个数,在v里面下标注意减一
    }
    return 0;
}

Comments


愿我如星君如月,夜夜流光相皎洁。