可持久化数据结构

可持久化数据结构是指在每次修改后都保存了修改前版本的数据结构。在可持久化数据结构中，我们可以很方便的追溯到某次修改前的版本，以此来完成某些操作。简单来说，对于$n$次插入操作，我们就存储$n$个版本，第$i$个版本对应了前$i$次操作后的数据结构。当然，不可能真的存$n$个完全独立的版本，空间会直接爆炸(～￣▽￣)～。可以注意到，对于Trie和线段树等数据结构来说，每次插入只改变了一条链上的节点，因此对于每次插入操作，我们只需要新建这条链上的节点，而其他的节点可以直接白嫖上一个版本的。
常用的可持久化数据结构主要有可持久化的Trie和可持久化线段树。

可持久化Trie

首先，既然有$n$个版本，当然就对应了$n$个根节点，从不同的根节点开始遍历就可以得到不同版本的数据结构。下面简单演示一下可持久化Trie的插入过程。
最开始是一个空的Trie，插入一个字符串no（黑色节点表示根节点）

然后插入一个字符串game，由于这整个字符串都属于要改变的节点，所以都要新建，同时，为了从新建的根节点能够访问到以前插入的字符串，新的根节点也要有边连向n

继续再插入一个字符串no，但是no之前已经插入过了，如果是一般的Trie，那么插入之后不会有变化，但是对于可持久化Trie来说，不论之前有没有，新插入的字符串都需要再开新的节点存储

最后插入字符串life

从上面的演示可以看出，从对应版本的根节点开始遍历，就可以得到这个版本的对应的Trie，而不会遍历到在这之后插入的节点。
具体的代码如下：

// 实际占据空间为所有字符串长度和（每次插入都要创建新节点）加上字符串数量（每次都要创建一个根节点）
int tr[N + M + 10][26], tot;
// 每个版本的根节点
int rt[N + 1];
// p表示上一个版本的根节点，q为当前版本的根节点
void insert(std::string &s, int p, int q)
{
    for (auto ch : s) {
        int c = ch - 'a';
        // 从上一个版本继承节点
        for (int i = 0; i < 26; ++i)
            tr[q][i] = tr[p][i];
        // 为当前节点创建新节点
        tr[q][c] = ++tot;
        // 同时移动两个指针，因为需要将后续的节点也复制过来
        p = tr[p][c], q = tr[q][c];
    }
} 

for (int i = 1; i <= N; ++i) {
    rt[i] = ++tot; // 创建新的根节点
    insert(a[i], rt[i - 1], rt[i]);
}

接下来是一道例题：https://www.luogu.com.cn/problem/P4735
首先看到区间异或和，自然想到前缀和做法，而01Trie则可以找出最大的异或和，那么如何限制$l$与$r$呢？我们可以使用可持久化Trie，由于当从第$r$个根节点开始遍历时只会遍历到$1$至$r$的数字，这样就限制了$r$。接下来就是限制$l$，注意到对于每次插入可持久化Trie都会创建新的节点，所以对于每一个数字中的每一位，在01Trie中其实都有唯一一个节点与其对应，后面的节点都只是在引用这个节点，而一般的Trie由于公共前缀只存储一个，所以没有这样的一一对应关系。因此，我们可以在每个节点上再存储一个信息，即这个节点是作为第几个数字被插入的，这样在遍历寻找时，只需要判断一下是否大于等于$l$，就能保证遍历的范围限定在$l$之后。

#include <bits/stdc++.h>
using std::cin;
using ll = long long;
const int N = 6e5 + 10;
// lst即节点是作为第几个数字被插入的
int tr[N * 25][2], lst[N * 25];
int tot;
int main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    std::vector<int> a(n);
    for (auto &x : a)
        cin >> x;

    auto insert = [&](int idx, int x, int p, int q) -> void {
        for (int i = 25; i >= 0; --i) {
            int b = x >> i & 1;
            tr[q][!b] = tr[p][!b];
            tr[q][b] = ++tot;
            lst[tr[q][b]] = idx;
            p = tr[p][b], q = tr[q][b];
        }
    };

    std::vector<int> rt(n + m + 1);
    rt[0] = ++tot, lst[0] = -1;
    // 因为rt[0]是有意义的，但节点编号0表示没有，为了让l为0时不会出现误判，lst[0]要设置为-1
    insert(0, 0, 0, 1);
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        sum ^= a[i];
        rt[i + 1] = ++tot;
        insert(i + 1, sum, rt[i], rt[i + 1]);
    }

    auto query = [&](int l, int r, int x) -> int {
        int p = rt[r], res = 0;
        for (int i = 25; i >= 0; --i) {
            int b = x >> i & 1;
            // 这里不需要判空，因为没有子节点时lst[0]为-1一定小于l
            if (lst[tr[p][!b]] >= l)
                p = tr[p][!b], res |= 1 << i;
            else
                p = tr[p][b];
        }
        return res;
    };

    while (m--) {
        char op;
        cin >> op;
        if (op == 'A') {
            int x;
            cin >> x;
            rt[++n] = ++tot;
            sum ^= x;
            insert(n, sum, rt[n - 1], rt[n]);
        } else {
            int l, r, x;
            cin >> l >> r >> x;
            x ^= sum;
            std::cout << query(l - 1, r - 1, x) << '\n';
        }
    }
}

可持久化线段树

在单点修改的线段树中，每次修改都只改变了这一条路径上的$log(n)$个节点，所以线段树自然也有可持久化版本。其操作也与可持久化Trie类似，改变的节点创建新的节点，不改变的直接继承自上一个版本。下面用区间最值的线段树简单演示一下修改过程。
初始状态

将1修改为6，那么对于1到根节点上的所有节点，都需要新建一个节点

虽然有点扭曲，但还是可以看出来第二个线段树的样子的。由于过程基本和可持久化Trie一样主要是图变难画了，在此只演示一次修改。
可持久化线段树的插入操作代码如下，由于可持久化线段树内存占用较大，所以可以通过不存储$l$和$r$，而是直接将$l$和$r$作为递归参数传递，同时由于后面新建立的线段树不再是完全二叉树，不能直接线性存储，只能动态开点：

// lc：左儿子，rc：右儿子
int insert(int i, int x, int l, int r, int p) {
    // 创建新节点，复制上一个版本
    int q = ++tot;
    tr[q] = tr[p];
    if (l == r) {
        tr[q].max = x;
        return q;
    }
    int mid = l + r >> 1;
    if (i <= mid) tr[q].lc = insert(i, x, l, mid, tr[p].lc);
    else tr[q].rc = insert(i, x, mid + 1, r, tr[p].rc);
    tr[q].max = std::max(tr[tr[q].lc].max, tr[tr[q].rc].max);
    return q;
}

主席树

既然都提到了可持久化线段树，那就不得不提一下大名鼎鼎的主席树。
主席树的本质其实就是可持久化权值线段树，用来解决区间第$k$大之类的问题。首先什么是权值线段树？权值线段树其实就是一个维护数字出现次数的线段树，比如叶子节点的区间为$3$，值为$2$，就表示$3$出现了$2$次，当然实际使用时一般需要离散化，因为权值线段树不关心数字的具体大小。有了权值线段树，我们就可以找出整个数组的第$k$大，具体来说，每次递归时先判断左边区间里的数字数量是否大于$k$，是则说明第$k$大的数在右边，那么就往右儿子递归，同时$k$减去左边出现的数字数量，否则往左儿子递归。
这是全局的第$k$大，那么如何限制区间呢。可以使用可持久化线段树，这样从第$r$个根节点开始遍历就可以得到前$r$个数字的第$k$大，这样就限制了$r$，对于$l$，我们可以使用前缀和的思想来作差，从$l-1$个根节点开始遍历，两者相减就可以得到$l$至$r$这段区间中数字出现的次数。
具体可以看看模板题https://www.luogu.com.cn/problem/P3834

#include <bits/stdc++.h>
using std::cin;
using ll = long long;
const int N = 2e5 + 10;
struct Node {
    int lc, rc;
    int cnt;
};
Node tr[N * 25];
int tot;
int main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    std::vector<int> a(n);
    for (auto &x : a)
        cin >> x;

    auto t = a;
    std::sort(t.begin(), t.end());
    t.erase(std::unique(t.begin(), t.end()), t.end());

    std::vector<int> rt(n + 1);
    auto build = [&](auto &self, int l, int r) -> int {
        int p = ++tot;
        if (l == r)
            return p;
        int mid = l + r >> 1;
        tr[p].lc = self(self, l, mid);
        tr[p].rc = self(self, mid + 1, r);
        return p;
    };
    rt[0] = build(build, 0, n - 1);

    auto insert = [&](auto &self, int p, int l, int r, int x) -> int {
        int q = ++tot;
        tr[q] = tr[p];
        if (l == r) {
            tr[q].cnt++;
            return q;
        }
        int mid = l + r >> 1;
        if (x <= mid)
            tr[q].lc = self(self, tr[p].lc, l, mid, x);
        else
            tr[q].rc = self(self, tr[p].rc, mid + 1, r, x);
        tr[q].cnt = tr[tr[q].lc].cnt + tr[tr[q].rc].cnt;
        return q;
    };

    for (int i = 0; i < n; ++i) {
        int p = std::ranges::lower_bound(t, a[i]) - t.begin();
        rt[i + 1] = insert(insert, rt[i], 0, n - 1, p);
    }

    auto query = [&](auto &self, int p, int q, int l, int r, int k) -> int {
        if (l == r)
            return l;
        // 线段树作差
        int mid = l + r >> 1, t = tr[tr[q].lc].cnt - tr[tr[p].lc].cnt;
        if (t >= k)
            return self(self, tr[p].lc, tr[q].lc, l, mid, k);
        else
            return self(self, tr[p].rc, tr[q].rc, mid + 1, r, k - t);
    };

    while (m--) {
        int l, r, k;
        cin >> l >> r >> k;
        std::cout << t[query(query, rt[l - 1], rt[r], 0, n - 1, k)] << '\n';
    }
}

---

暑假集训开始了，愉快的假期生活结束了＞︿＜