题解：【模板】可持久化线段树 1 & 2

· · 题解

可持久化线段树 1

Problem

维护序列在某个历史版本上修改/查询某一个位置上的值。

算法介绍

什么是可持久化线段树呢？首先来考虑怎么暴力解决这个问题：

弱化版：n,m\le 10^3

对于每一次操作，我们每次复制一个版本即可。

这样子时空复杂度是 O(nm)（易得）。显然过不了。

标准版：n,m\le 10^5

首先我们将这个序列化成一个线段树。（至于为什么后面再讲）可是这样子复制的话还是 O(nm)。

我们来观察一次复制：

其实真正修改了的只有 树高 个节点（即 \log n 个节点），但是我们复制了 n 个节点。那这样就好办了，我们每次修改只修改一条链即可。

但是这样子就不能简单地使用基本的线段树了，于是就有了“可持久化线段树”。

可持久化线段树的原理就是如上讲的，每次修改只插入一条链。

代码实现

按照刚才的分析，最重要的问题就是无法建二叉树。

似乎在动态开点线段树中，我们也遇到了这个问题，当时我们使用了结构体，来存储左儿子右儿子编号。

struct tree{
    int l,r,val;
};

既然这样我们就需要开启新结点：

int add(int node)
{
  a[++top]=a[node];
  return top;
}

top 的意思是当前节点编号，node 的意思是原来的节点“本来修改的对象”，先复制一遍，再进行复制。

接着考虑建树，首先我们定义一个新数组 tr[i]，表示第 i 个版本所对应的树根。初始版本的根就叫做 tr[0]=1。为了知道节点的左右儿子，build 时返回当前节点编号即可。代码实现如下：

int build(int node,int l=1,int r=n)
{
  node=++top; // 其实也是 add(node),但是初始版本不用复制，直接这么写就可以了。
  if(l==r)
  {
    a[node].val=read(); // 本题可以直接输入
    return node;
  }
  int mid=(l+r)/2;
  a[node].l=build(a[node].l,l,mid);
  a[node].r=build(a[node].r,mid+1,r);
  return node;
}

update 和 build 差不多，但是 update 不能 node=++top，而需要 node=add(node)：

int update(int w,int val,int node,int l=1,int r=n)
{
  node=add(node);
  if(l==r) a[node].val=val;
  else
  {
    int mid=(l+r)/2;
    if(w<=mid) a[node].l=update(w,val,a[node].l,l,mid);
    else a[node].r=update(w,val,a[node].r,mid+1,r);
  }
  return node;
}

query 实现就非常简单了，和正常的没有区别：

int query(int w,int node,int l=1,int r=n)
{
  if(l==r) return a[node].val;
  else
  {
    int mid=(l+r)/2;
    if(w<=mid) return query(w,a[node].l,l,mid);
    else return query(w,a[node].r,mid+1,r);
  }
}

建树的话调用这个代码就可以了：

tr[0]=build(0); // 也可以写作 tr[0]=1;build(0);

修改和查询同理。

那么最后的代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int read() // 快读
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
struct ZX__tree{
    struct tree{
        int l,r,val;
    };
    tree a[32000006];
    int tr[32000006];
    int top;
    int build(int node,int l=1,int r=n)
    {
        node=++top;
        if(l==r)
        {
            a[node].val=read();
            return node;
        }
        int mid=(l+r)/2;
        a[node].l=build(a[node].l,l,mid);
        a[node].r=build(a[node].r,mid+1,r);
        return node;
    }
    int add(int &node)
    {
        top++;
        a[top]=a[node];
        return top;
    }
    int update(int w,int val,int node,int l=1,int r=n)
    {
        node=add(node);
        if(l==r) a[node].val=val;
        else
        {
            int mid=(l+r)/2;
            if(w<=mid) a[node].l=update(w,val,a[node].l,l,mid);
            else a[node].r=update(w,val,a[node].r,mid+1,r);
        }
        return node;
    }
    int query(int w,int node,int l=1,int r=n)
    {
        if(l==r) return a[node].val;
        else
        {
            int mid=(l+r)/2;
            if(w<=mid) return query(w,a[node].l,l,mid);
            else return query(w,a[node].r,mid+1,r);
        }
    }
}a;
signed main()
{
    int T;
    cin>>n>>T;
    a.tr[0]=a.build(0);
    for(int i=1;i<=T;i++)
    {
        int v=read(),op=read();
        if(op==1)
        {
            int w=read(),val=read();
            a.tr[i]=a.update(w,val,a.tr[v]);
        }
        else
        {
            int w=read();
            cout<<a.query(w,a.tr[v])<<endl;
            a.tr[i]=a.tr[v];
        }
    }
    return 0;
}

正确性证明

主要是对时空复杂度的证明。

对于时间复杂度：很显然的是 O(n+m\log n)。（不知道原因的自己回去学好线段树再来）

对于空间复杂度：因为每次只需要建一条链，空间复杂度也优化到了 O(n+m\log n)。

所以时空复杂度均为 O(n+m\log n)。

为什么要将序列变为线段树

  1. 本题虽然用不到节点合并，但并不排除别的题有（比如下一道就有）
  2. 虽然用不到节点合并，但是二叉树保证了每次我只需要修改左儿子或者右儿子，所以降低了时间复杂度。
  3. 不然就不是可持久化线段树的例题了。

    可持久化线段树 2

    Problem

    静态查询区间第 k 大。

    算法分析

    弱化版 1：查询的区间为 [1,n]

    考虑使用权值线段树。这个还是非常简单的，不知道自己去学。

伪代码如下：

int query(u,l,r,k):
  if l==r:
    return l;
  if 左孩子数的个数<=k:
    return query(lchild,l,r,k);
  else
    return query(rchild,l,r,k-左孩子数的个数);

弱化版 2：查询的区间为 [1,r]

通过我们对可持久化线段树的认识，我们发现其实可持久化线段树就是一个存储多棵线段树的数据结构且除了初始线段树其他线段树都可以通过另外一个线段树进行单点修改得到。

上面的意思是可持久化线段树：

这篇题解后面只要未说明，权值线段树简称为线段树。（包括可持久化线段树也被称作可持久化权值线段树）

那么我们可以利用可持久化线段树的这个性质，存储 n 棵线段树，第 i 棵线段树存的是前 i 个数。

那么查询 [1,r] 的第 k 大，相当于查询第 r 棵线段树的第 k 大。

变成了弱化版 1。

标准版：查询的区间为 [l,r]

继续沿用弱化版 2 的思路，我们仍然用可持久化权值线段树来解决这个问题。

以下记 mid=\frac{L+R}{2}，下取整。

在 [1,r] 中，假设我们枚举到了 [L,R] 这个区间里的数，要求第 k 大，就是先看 [L,mid] 中有没有 k 个数，如果有就往左边找，否则查右边的。

在 [l,r] 中，也是同理的，假设我们枚举到了 [L,R] 这个区间里的数，要求第 k 大，就是先看 [L,mid] 中有没有 k 个数。问题是怎么求 [L,mid] 里的数，我们可以用 r 这棵树里 [L,mid] 里的数的个数减去 (l-1) 这棵树里 [L,mid] 里的数的个数。

那么这道题不就做完了吗？

代码实现

update 从原来的单点赋值变为单点 +1。这里就不单独贴代码了。

query 和弱化版 1 差不多：

int query(int nl,int nr,int k,int L=1,int R=cnt)
{
  if(L==R) return L;
  int mid=(L+R)>>1,suml=a[a[nr].l].w-a[a[nl].l].w;
  if(suml>=k) return query(a[nl].l,a[nr].l,k,L,mid);
  else return query(a[nl].r,a[nr].r,k-suml,mid+1,R);
}

完整代码：

#include<bits/stdc++.h>
using namespace std;
int cnt;
struct ZX_tree{
    struct tree{
        int u,l,r,w; // w表示a[u]表示的区间内,数出现的个数 
    };
    tree a[6400005];
    int tr[6400005],tot;
    void add(int &node)
    {
        tot++;
        a[tot]=a[node];
        node=tot;
    }
    void pushup(int u){a[u].w=a[a[u].l].w+a[a[u].r].w;}
    int build(int node=0,int l=1,int r=cnt)
    {
        node=++tot;
        if(l==r) return node;
        int mid=(l+r)>>1;
        a[node].l=build(a[node].l,l,mid);
        a[node].r=build(a[node].r,mid+1,r);
        return node;
    }
    int update(int w,int p,int node,int l=1,int r=cnt)
    {
        add(node);
        if(l==r)
        {
            a[node].w+=p;
            return node;
        }
        int mid=(l+r)/2;
        if(w<=mid) a[node].l=update(w,p,a[node].l,l,mid);
        else a[node].r=update(w,p,a[node].r,mid+1,r);
        pushup(node);
        return node;
    }
    int query(int nl,int nr,int k,int L=1,int R=cnt)
    {
        if(L==R) return L;
        int mid=(L+R)>>1,suml=a[a[nr].l].w-a[a[nl].l].w;
        if(suml>=k) return query(a[nl].l,a[nr].l,k,L,mid);
        else return query(a[nl].r,a[nr].r,k-suml,mid+1,R);
    }
}seg;
int yl[200005],sor[200005];
unordered_map<int,int>mp,dy;
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>yl[i],sor[i]=yl[i];
    sort(sor+1,sor+1+n);
    cnt=unique(sor+1,sor+n+1)-sor-1;
    for(int i=1;i<=cnt;i++) mp[sor[i]]=i,dy[i]=sor[i];
    seg.tr[0]=seg.build();
    for(int i=1;i<=n;i++)
        seg.tr[i]=seg.update(mp[yl[i]],1,seg.tr[i-1]);
    while(m--)
    {
        int l,r,k;
        cin>>l>>r>>k;
        cout<<dy[seg.query(seg.tr[l-1],seg.tr[r],k)]<<'\n';
    }
    return 0;
}

正确性证明

和模板 1 一样的分析，时空复杂度均为 O(n+m\log n)。

《其他做法》

话说你都动态开点了，干嘛离散化啊...

#include<bits/stdc++.h>
using namespace std;
int len=1000000000,a[6400005];
struct ZX_tree{
    struct tree{
        int u,l,r,val;
    };
    tree a[64200005];
    int tr[26400005],tot;
    int add(int node)
    {
        a[++tot]=a[node];
        return tot;
    }
    int build(int node,int l=0,int r=len)
    {
        node=++tot;
        if(l==r) return node;
        int mid=(l+r)>>1;
        a[node].l=build(node,l,mid);
        a[node].r=build(node,mid+1,r);
        return node;
    }
    void pushup(int u){a[u].val=a[a[u].l].val+a[a[u].r].val;}
    int update(int w,int node,int l=0,int r=len)
    {
        node=add(node);
        if(l==r)
        {
            a[node].val++;
            return tot;
        }
        int mid=(l+r)>>1;
        if(w<=mid)a[node].l=update(w,a[node].l,l,mid);
        else a[node].r=update(w,a[node].r,mid+1,r);
        pushup(node);
        return node;
    }
    int query(int nl,int nr,int k,int l=0,int r=len)
    {
        if(l==r) return l;
        int mid=(l+r)>>1,sm=a[a[nr].l].val-a[a[nl].l].val;
        if(sm>=k) return query(a[nl].l,a[nr].l,k,l,mid);
        else return query(a[nl].r,a[nr].r,k-sm,mid+1,r);
    }
}seg;
unordered_map<int,int>mp,dy;
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) seg.tr[i]=seg.update(a[i],seg.tr[i-1]);
    while(m--)
    {
        int l,r,k;
        cin>>l>>r>>k;
        cout<<seg.query(seg.tr[l-1],seg.tr[r],k)<<'\n';
    }
    return 0;
}