可持久化线段树学习笔记

可持久化线段树就是可以询问历史版本状态的线段树。

我们考虑暴力怎样实现询问线段树的历史状态，我们每次在对线段树进行操作的时候，每次都把位修改前的版本存一下，然后要找历史版本的时候直接找，这样时间复杂度和空间复杂都会爆炸。

我们可以发现，每次对线段树进行操作最多才会修改 \(\log_2(size)\) 个节点，其中 \(size\) 为线段树的大小，所以我们每次把线段树全部复制一遍是不必要的，我们只需要把修改时经过的节点新建出来，然后将其他的节点连接了原来的线段树上就可以了。

\(like\ this\)

严格的来说这个东西不是一棵树，但是他如果从父亲节点往儿子节点走就是一棵树，所以对于任意一颗这样的树它还满足线段树的性质，所以我们不用纠结这个是不是一棵树。

然后每次修改都进行一下这样的操作，要查询历史版本的时候只需要找到历史版本的根节点，然后直接当成线段树来用就可以了。

inline void insert(int &rt,int l,int r,int x)
{
    t[++cnt]=t[rt];
    rt=cnt;
    if (l==r)
    {
        t[rt].sum++;
        return ;
    }
    int mid=(l+r)>>1;
    if (x<=mid) insert(t[rt].ls,l,mid,x);
    else insert(t[rt].rs,mid+1,r,x);
    push_up(rt);
    return ;
}

与普通线段树不同的地方就是对 \(rt\) 加了取地址，表示对传入的值的原值进行操作，还有下面的这两句

    t[++cnt]=t[rt]; //将原节点的信息复制给新建的节点的信息，不要丢失另一个不修改儿子的信息
    rt=cnt;         //把树根转化为新建节点，再加上取地址，这样对于父亲节点来说，它的修改的儿子就是新建的节点

P3834 可持久化线段树 1（主席树）

这道题目咋一看和可持久化线段树没有任何关系，但是这确实是可持久化线段树的日常操作。

我们考虑假设给你 \(l-1\) 和 \(r\) 这个状态下的权值线段树，这题肯定就很好做了，只需要两颗线段树减一下就可以了，然后我们发现这就是维护一颗可持久化线段树，然后在查询历史信息。

#include<bits/stdc++.h>
const int N=2e5+100;
using std::sort;
int n,m,bsize;
int a[N],b[N],rt[N];
struct tree{
    int cnt;
    struct Tree{
        int sum,ls,rs;
    }t[N*20];
    inline void clear() {cnt=0;return ;}
    inline void push_up(int rt)
    {
        t[rt].sum=t[t[rt].ls].sum+t[t[rt].rs].sum;
        return ;
    }
    inline void insert(int &rt,int l,int r,int x)
    {
        t[++cnt]=t[rt];
        rt=cnt;
        if (l==r)
        {
            t[rt].sum++;
            return ;
        }
        int mid=(l+r)>>1;
        if (x<=mid) insert(t[rt].ls,l,mid,x);
        else insert(t[rt].rs,mid+1,r,x);
        push_up(rt);
        return ;
    }
    inline int query(int rt1,int rt2,int l,int r,int k)
    {
        if (l==r) return l;
        int sz=t[t[rt2].ls].sum-t[t[rt1].ls].sum,mid=(l+r)>>1;
        if (k<=sz) return query(t[rt1].ls,t[rt2].ls,l,mid,k);
        else return query(t[rt1].rs,t[rt2].rs,mid+1,r,k-sz);
    }
}t;
inline int midfind(int x)
{
//  printf("%d\n",x);
    int l=1,r=bsize;
    while (l<=r)
    {
        int mid=(l+r)>>1;
        if (b[mid]==x) return mid;
        if (b[mid]<x) l=mid+1;
        else r=mid-1;
    }
    return 0;
}
inline int read()
{
    int ans=0,p=1;
    char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') p=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') {ans=ans*10-'0'+ch;ch=getchar();}
    return ans*p;
}
inline void Pre()
{
    sort(b+1,b+n+1);
    for (int i=1;i<=n;i++)
    {
        int k=i;
        b[++bsize]=b[i];
        while (b[k]==b[k+1]) k++;
        i=k;
    }
    return ;
}
int main()
{
    n=read();m=read();
    for (int i=1;i<=n;i++)
    a[i]=b[i]=read();
    Pre();
    t.clear();
    for (int i=1;i<=n;i++)
    {
        int now=midfind(a[i]);
        rt[i]=rt[i-1];
        t.insert(rt[i],1,bsize,now);
    }
    while (m--)
    {
        int l,r,k;
        l=read();r=read();k=read();
        printf("%d\n",b[t.query(rt[l-1],rt[r],1,bsize,k)]);
    }
    return 0;
}

可持久化线段树学习笔记

原文：https://www.cnblogs.com/last-diary/p/11632086.html