P3834 主席树模板解题报告

wjyyy · 2018-04-15 17:55:53 · 题解

主席树，就是通过查询线段树的历史版本返回信息的可持久化线段树。可以利用之前已经有的数据来减少时空开销。

我是用指针写的，这样省去了数组下标存储的空间（但是64位）和下标调用访问时浪费的一点点时间。

本题有n个数，m个询问，相当于n次插入新结点,有n+1个历史版本（因为还有初始版本的空树）。

因此这个题目可以转化为第l-1个版本与第r个版本之间的线段树“差”上求第k值的问题，下面会解释。

而主席树因为每次改变时只会改变一条链，那么每个结点的另一条链就是上一个版本的同一条链，这样可以大大减少建树的时间上的开销以及一大堆指针的空间上的开销。从第0颗树，也就是空树开始，每个版本不用多开结点，直接将指针指向上一个版本就可以了。如果线段树掌握的不错的话，那么主席树的建立也就不在话下了。

上面提到的线段树之差，其实是像前缀和一样，用r版本的线段树，将前面l-1版本的树上的数据减去，而且只减去有影响的，即更新过的，因此在查询时判断并更新就可以了。还要注意的是，并不是两个完整的树相减，因为两个树相减结果一定是r-l+1，要让它们的左孩子相减，如果左孩子之差\geq k,说明l到r之间第k小值在根结点的左孩子里，否则在右孩子里。

另外还有一点，这个题目的a_i范围是[-10^9,10^9]，而数据总共只有200,000个，所以我们要根据大小离散化数据。不需要hash，只需要将其按大小顺序赋予一个映射函数就可以了。\qquad有两种实现方法，一是代码中的结构体gg,需要用到两次排序，可能慢一点；二是输入时使用两个相同的数组，只排一个序，像这样

    for(int i=1;i<=n;i++)
    {
        scanf("%d\n",a[i].v);
       a[i].t=i;//输入时间
    }
    std::sort(a+1,a+1+n);
    for(int i=1;i<=n;i++)
        b[a[i].t]=i;//将具体数值按输入时间的导入新编排的位置

Code：

#include<cstdio>
#include<cstring>
#include<algorithm>
#define mid ((l+r)>>1)
const int N=2e5+5;//200000个点
struct node
{
    int v,l,r;//v存的是当前状态下[l,r]范围内有多少个点
    node *ls,*rs;
    node()
    {
        v=0;
        ls=NULL;//因为这里置为NULL，所以调用时要为其申请空间或赋值
        rs=NULL;
    }
}*root[N];//有n个树根，申请n个根结点
struct gg
{//题解正文提到的gg结构体
    int num,o,v;//num存本来的数，order(o)存输入顺序，v存离散化的顺序
}d[N];
bool cmp1(gg a,gg b)//给各个点赋予它的离散化顺序
{
    return a.num<b.num;
}
bool cmp2(gg a,gg b)//将各个点恢复成输入顺序
{
    return a.o<b.o;
}
int n,m;
int q[N];//q[i]存的是离散点i的原本值（相当于gg的反函数）
void Build(node *root,int l,int r)//建立空树时没有前车之鉴，所以特殊建树，无论能不能满，把这棵树的叶子节点覆盖到位
{
    root->l=l;
    root->r=r;
    if(l==r)
        return;//叶子节点
    root->ls=new node();//给NULL申请新的空间
    root->rs=new node();
    Build(root->ls,l,mid);//递归建树
    Build(root->rs,mid+1,r);
}
void build(node *prer,node *root,int l,int r,int x)//preroot带的是前一棵树，因此可以依附它，并将它的左右孩子一同带入各个函数，root是要建的树，x是要添加的值
{
    root->l=l;
    root->r=r;
    if(l==r)
    {
        root->v++;//找到了要添加的值，可以返回
        return;
    }
    if(x>mid)//其他情况一直寻找知道找到要添加的值
    {
        root->rs=new node();
        root->ls=prer->ls;
        build(prer->rs,root->rs,mid+1,r,x);
        root->v=root->ls->v+root->rs->v;//从两个孩子结点回溯上来，不一定是只增加了1，因为还会从其他孩子结点更新
        return;
    }
    else
    {
        root->ls=new node();
        root->rs=prer->rs;
        build(prer->ls,root->ls,l,mid,x);
        root->v=root->ls->v+root->rs->v;
        return;
    }
}
int ask(node *prer,node *root,int k)//找第k小值并返回q中下标
{
    if(root->l==root->r)
        return root->l;
    int del=root->ls->v-prer->ls->v;//这里是重点，删树的过程，这里记录的是左孩子之间相差多少，记差值为delta
    if(del<k)//如果相差小于k，那么第k小值就在右孩子处，并且要在右孩子处找到第（k-del）小值
        return ask(prer->rs,root->rs,k-del);
    return ask(prer->ls,root->ls,k);//在左边还是找第k小值
}
int main()
{
    scanf("%d%d",&n,&m);
    int u;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&u);
        d[i].o=i;//记录输入顺序
        d[i].num=u;//原本数据
        root[i]=new node();
    }
    root[0]=new node();
    std::sort(d+1,d+n+1,cmp1);
    for(int i=1;i<=n;i++)
    {
        d[i].v=i;//记录排序后的顺序
        q[i]=d[i].num;//记录顺序对应的原数据
    }
    std::sort(d+1,d+n+1,cmp2);//没有去重，可以去重优化少量时间复杂度
    Build(root[0],1,n);//建空树
    for(int i=1;i<=n;i++)
        build(root[i-1],root[i],1,n,d[i].v);//每一个都要建树，并且传入d[i].v作为新添加的叶子节点
    int l,r,k;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&l,&r,&k);
        printf("%d\n",q[ask(root[l-1],root[r],k)]);//查询并输出
    }
    return 0;
}

P3834 主席树 模板 解题报告

Code：

P3834 主席树模板解题报告