题解：P3919 【模板】可持久化线段树 1（可持久化数组）

· · 题解

我的博客

模板题：P3919 【模板】可持久化线段树 1（可持久化数组）

前置知识：线段树、动态开点。

简介

对于一个数据结构，例如普通线段树、树状数组等，我们通常维护的是经过若干次操作后该数据结构的最新状态。但对于模板题而言，如果要求我们查询该数据结构所有历史版本的信息时，就需要用到可持久化数据结构了。

何为可持久化？可以支持回退，访问所有历史版本的数据结构就被称为是可持久化的。

比方说对于模板题，不妨按照 naive 的思想看，我们可以在每次修改操作后 copy 一份线段树（预留编号），然后后续访问时再遍历其即可。但是这样做最多会建立 10^6 棵线段树，空间承受不住。不过这种 naive 想法给我们提供了一种实现可持久化的思路。

我们思考，为什么空间炸了呢？原因在于我们开的节点太多了。但是我们又知道，单次修改操作并不会将整棵线段树都发生改变，也就是说，上述 naive 思路记录了很多无用的、重复的信息，于是我们可以根据这一点，在每次修改操作时，只 copy 线段树的部分节点。基于这样的思路，我们来讲讲可持久化线段树。

可持久化线段树的原理

举个例子，现在我们有一棵线段树用于存放区间 [1,8] 的信息，如图所示：

现在我们通过一个操作修改了位置 6 的信息，按照普通线段树操作，相应关联的节点的信息也将被修改（图中红边节点）：

我们发现，除了红边节点外其余节点的信息并未发生改变，因此在 copy 时无需 copy 这些节点。

我们将 copy 的节点单独拿出来（如图，注意此时原线段树的节点信息并未改变，改变的信息储存在新的节点内）：

接下来就是作连边处理了。由于在修改后我们依然希望其能够按照正常线段树的功能去进行接下来的操作，所以我们按照线段树的方式给新的节点赋予左右儿子，即将新的节点插入原来的线段树，这个过程可以用左右儿子编号指针（用 ls 和 rs 表示）来实现。如图所示，新加边用红边表示：

我们可以发现，插入节点后，线段树实际上变成了一张有向图。

类似地，如果我们再次修改位置 8 的信息，我们依然可以类似进行操作（这步操作在图中体现为绿色节点及新加边）：

这个过程其实就是可持久化线段树的建立过程。

接下来要解决的问题是，如何通过这个有向图来访问所有历史版本的线段树呢？我们发现，每次修改时，我们新加入的节点中必然是有且仅有一个节点没有父节点，这个节点其实就是每次修改后信息必然改变的根节点；换句话说，这个节点其实是新的线段树的根节点，因此每个历史版本的线段树都唯一被一个根节点所确定。因此我们在每次访问某个历史版本的线段树时，就可以锚定一个根节点，从根节点往下遍历即可。

具体而言，我们可以用一个 root 数组来存放所有历史版本线段树的根节点，在每次访问时，只需给定其根节点的在 root 中的编号 k，即可找到其根节点指针 root_k，接着就可以在线段树上进行操作啦。

可以结合下面的图示再理解（前后三张图分别表示我们希望访问三次历史版本的线段树，虚线及浅色表示不访问的节点）：

第一个历史版本：

第二个历史版本：

第三个历史版本：

可持久化线段树的实现

由于可持久化线段树不再是一棵完全二叉树，我们在给节点编号时不再按层次序编号，而是记录当前节点的左右儿子编号。

    struct Tree
    {
        int l, r;
        int v;//值 
    }tr[N * 30];

需要注意的是，由于每次修改操作均会创建 \log n 个节点，因此我们最多额外添加 Q\log n 个节点（Q 为询问个数），所以可持久化线段树的空间要求较高。一般我们采用开 20 或 30 倍空间（或者采用 N<<5）来避免空间不足的问题。

此外，一般来说，可持久化线段树用动态开点实现，因此我们需要额外记录当前节点编号 id。为实现上文所述的实时访问历史版本的功能，我们还需记录根节点：

    int id;//编号 
    int root[N];//根节点

准备工作完毕，我们就可以实现可持久化线段树的各项操作啦。

首先来看创建新节点的操作（动态开点），没有什么好说的：

    int insert(int u)//动态开点 
    {
        id ++;
        tr[id] = tr[u];
        return id;
    }

然后就是建树。可持久化线段树的原始建树过程与线段树基本一样：

    int build(int u, int l, int r)
    {
        id ++, u = id;//赋予编号
        if(l == r)
        {
            tr[u].v = a[l];
            return id;//返还编号 
        }
        int mid = l + r >> 1;
        tr[u].l = build(tr[u].l, l, mid);
        tr[u].r = build(tr[u].r, mid + 1, r);
        return u;
    }

我们来看模板题需要我们实现什么具体操作：

这其实就是可持久化线段树的修改操作（modify）以及查询操作（query），由于每个历史版本的线段树我们都能够由不同的根节点独立访问，因此这两个操作与普通线段树也是一样的：

    int modify(int u, int l, int r, int p, int val)
    {
        u = insert(u);//该路径上的所有点均需重新开点
        if(l == r)
        {
            tr[u].v = val;
            return u;
        }
        int mid = l + r >> 1;
        if(p <= mid) tr[u].l = modify(tr[u].l, l, mid, p, val);
        else tr[u].r = modify(tr[u].r, mid + 1, r, p, val);
        return u;
    }
    int query(int u, int l, int r, int p)
    {
        if(l == r) return tr[u].v;
        int mid = l + r >> 1;
        if(p <= mid) return query(tr[u].l, l, mid, p);
        else return query(tr[u].r, mid + 1, r, p);
    }

这就是可持久化线段树的基本操作的实现了。总而言之，可持久化线段树的代码与线段树高度重合，原理基本一致，所以还是比较好写的。

而在主函数的调用中，我们仅需根据版本的索引获取当前版本的根节点即可：

    for(int i = 1; i <= Q; i ++)
    {
        scanf("%d%d", &ver, &op);//ver: 版本 
        if(op == 1)
        {
            scanf("%d%d", &p, &c);
            T.root[i] = T.modify(T.root[ver], 1, n, p, c);
        }
        else
        {
            scanf("%d", &p);
            printf("%d\n", T.query(T.root[ver], 1, n, p));
            T.root[i] = T.root[ver];//记录版本索引
        }
    }

到此为止，总算是把可持久化线段树好好讲了一遍，不妨再看看总代码再梳理一下：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, Q;
int ver, op, p, c;
int a[N];
struct PersistentSegmentTree
{
    struct Tree
    {
        int l, r;
        int v;//值 
    }tr[N * 30];
    int id;//编号 
    int root[N];//根节点 
    int insert(int u)//动态开点 
    {
        id ++;
        tr[id] = tr[u];
        return id;
    }
    int build(int u, int l, int r)
    {
        id ++, u = id;//赋予编号 
        if(l == r)
        {
            tr[u].v = a[l];
            return id;//返还编号 
        }
        int mid = l + r >> 1;
        tr[u].l = build(tr[u].l, l, mid);
        tr[u].r = build(tr[u].r, mid + 1, r);
        return u;
    }
    int modify(int u, int l, int r, int p, int val)
    {
        u = insert(u);//该路径上的所有点均需重新开点
        if(l == r)
        {
            tr[u].v = val;
            return u;
        }
        int mid = l + r >> 1;
        if(p <= mid) tr[u].l = modify(tr[u].l, l, mid, p, val);
        else tr[u].r = modify(tr[u].r, mid + 1, r, p, val);
        return u;
    }
    int query(int u, int l, int r, int p)
    {
        if(l == r) return tr[u].v;
        int mid = l + r >> 1;
        if(p <= mid) return query(tr[u].l, l, mid, p);
        else return query(tr[u].r, mid + 1, r, p);
    }
}T;
int main()
{
    cin >> n >> Q;
    for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
    T.root[0] = T.build(0, 1, n);//初始版本的根节点 
    for(int i = 1; i <= Q; i ++)
    {
        scanf("%d%d", &ver, &op);//ver: 版本 
        if(op == 1)
        {
            scanf("%d%d", &p, &c);
            T.root[i] = T.modify(T.root[ver], 1, n, p, c);
        }
        else
        {
            scanf("%d", &p);
            printf("%d\n", T.query(T.root[ver], 1, n, p));
            T.root[i] = T.root[ver];//记录版本索引
        }
    }
    return 0;
}