[熟肉] 一棵主席树新增了一个数据，这是它的结构发生的变化

可持久化简介

可持久化数据结构，支持在保证操作不变的情况下、同时保存它的一个历史版本，以便后期的历史查询。一般的编辑器软件都会内置撤回/重做的功能，这时使用一个可持久化数据结构来存储用户的历史操作就显得非常便捷了；某些软件通过重演用户操作来实现撤回/重做功能：当用户操作较多时，会非常浪费系统资源、且效率极低，尤其是在进行连续撤回/重做时，体验感极差。

可持久化线段树/主席树 理论基础

对于一般的线段树，可以通过调用 modify 函数来进行单点插入，如果此时再加入一个要求——能够查询先前某一时刻的某一操作对应的区间最值，普通的线段树就无能为力了。比较直接的想法是：可以把每一次操作得到的线段树单独拎出来，然后对于每次询问，在对应的线段树里面跑即可。时间上过得了关，但显然这样太浪费空间——明明更改单点时只会影响到特定路径上的节点，为什么还要费劲把其他无关变量另外存下来呢？基于这个优化思路，可持久化线段树/主席树应运而生。

先来看看普通线段树的插入操作：

如果每次操作都要新建一整个线段树的话，那么插入五个元素的空间复杂度就有原先的五倍之多。注意到在插入操作进行时，只有红色标出的节点是受影响的，因此只需把红圈存下来而无需无效地复制那些黑色的节点。

按此理论，完成五次插入后的线段树应是下面这样（部分虚边为了美观未在图上连出）：

可以发现一个规律：副本树的连接关系与原树相同、且副本树中不连接副本节点方向上的的子树与原树对应节点的对应子树相同。但同时我们失去了一些东西——左右子树的下标再也不满足线段树中的二倍和二倍加一关系了。不过对历史记录的访问变得轻松——从右到左，分别是第一次到第五次的操作所复制出来的副本树，每个副本树都有一个根节点，代表当前的历史记录。对于询问，直接在对应根节点上查询即可。

可持久化线段树/主席树 建树部分

根据上述分析，在主席树中，把 l 和 r 变量变成节点左右子树的下标（或指针）。由于每次操作最坏会复制出一个节点数为 的副本， 次修改（插入节点）之后最多同时存在 个节点，习惯性把空间开到 倍，也就是左移 位。此外维护一个数组 root 用来存储每个历史记录对应的根节点：

1
2
3
4
5

struct HJTTree {
    int l, r;
    int dat; // 值
} tree[N << 5];
int idx = 0, root[N];

根据特定要求添加变量即可。在建树时，不断向深层递归，并动态创建新点。因为上面提到的主席树不再满足普通线段树的下标规律，我们给建树函数设置返回值，递归设置左右子树的值即可。大部分代码和原版线段树相差无几。

1
2
3
4
5
6
7
8
9
10
11

int build(int l, int r) {
    int p = ++idx; // 开点
    if (l == r) {
        tree[p].dat = a[l];
        return p;
    }
    int mid = (l + r) >> 1;
    tree[p].l = build(l, mid); // 创建左子树
    tree[p].r = build(mid + 1, r); // 创建右子树
    return p;
}

可持久化线段树/主席树 节点插入

插入新节点时，我们需要先把沿途的所有节点复制一遍。节点复制写在一个函数 clone(int u) 中，顾名思义，这个操作非常简单——单纯就是原先点的复制、同时返回新建的副本节点的下标。

1
2
3
4
5

int clone(int u) {
    int p = ++idx; // 开点
    tree[p] = tree[u]; // 复制
    return p;
}

接下来是节点插入的主体部分。把节点复制完毕得到一个新点后，就需要递归更新所有点的左右子树，最终在叶子节点的位置放置要插入的点。

1
2
3
4
5
6
7
8
9
10
11
12

int insert(int u, int dat, int pos, int l, int r) {
    int p = clone(u); // 先复制
    if (l == r) {
        tree[p].dat = dat; // 叶子节点的位置插入
        return p;
    }  
    // 找到插入位置，同时更新子树
    int mid = (l + r) >> 1;
    if (pos <= mid) tree[p].l = insert(tree[u].l, dat, pos, l, mid);
    else tree[p].r = insert(tree[u].r, dat, pos, mid + 1, r);
    return p;
}

节点和区间的查询和普通线段树是基本一样的。这里需要注意题目要求查询哪个历史操作的值，并从相应的根节点开始向下递归查找。

模板两题

洛谷 P3919 [模板] 可持久化线段树 1（可持久化数组）

题目地址：P3919

题目难度：提高+/省选-

如题，你需要维护这样的一个长度为 的数组，支持如下几种操作

1. 在某个历史版本上修改某一个位置上的值
2. 访问某个历史版本上的某一位置的值

此外，每进行一次操作（对于操作2，即为生成一个完全一样的版本，不作任何改动），就会生成一个新的版本。版本编号即为当前操作的编号（从1开始编号，版本0表示初始状态数组）

输入格式：

输入的第一行包含两个正整数 ， 分别表示数组的长度和操作的个数。

第二行包含个整数，依次为初始状态下数组各位的值（依次为 $ a_i 1 i N $）。

接下来$ M i $为基于的历史版本号）：

1. 对于操作1，格式为$ v_i  1  {loc}_i  {value}i v_i a