题解：【模板】可持久化线段树 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. 不然就不是可持久化线段树的例题了。