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

b__b · 2025-06-13 22:19:13 · 题解

也许是我写过最长的题解。

在这里介绍两种做法：在线的 \mathcal{O}(n\log n) 做法（正解）与离线的 \mathcal{O}(n) 做法。

（感谢这篇题解为我提供的离线方案的思路。）

在线做法（可持久化线段树）

一种简单，容易想到的暴力做法就是每一次创建一个新版本就复制一个新数组，时间和空间复杂度都是 \mathcal{O}(mn)（m 次操作，每次创建一个大小为 n 的数组，从原数组复制要进行 n 次操作）。本题 n \leq 10^6，m \leq 10^6，这种做法显然不可接受。

我们观察需要创建新版本的场景，可以发现每次最多只会修改一个数，有时甚至不会修改，这些不修改的数字如果每一次都复制的话代价太高了。很容易想到每一次只记录修改的部分。

我们可以使用一种叫做可持久化线段树的数据结构。（没学过线段树的请右转学习线段树。）

我们现在先将版本 0 到版本 2 的线段树单独画出来：

我们发现版本 0 和版本 1 是重复的，我们可以直接将这些节点合并（将第二颗树的根节点的儿子设成第一颗树的根节点的儿子）：

对于版本 2，它只修改了一个数，我们可以想到只记录根节点到修改部分的一条“链”，其余的按照上面的方法操作：

总结：先将版本 0 的树完整的记录下来，接着之后的版本只记录修改的部分。

现在我们考虑复杂度：

空间复杂度：版本 0 要记录所有的数，会有 2n-1 个节点。总共有 m 个版本。假设每一个版本都有修改，那么每一次都要记录长为 \lceil \log_2 n \rceil+1 的“链”，空间复杂度约为 \mathcal{O}(n+m\log_2 n)。在此题中 n 和 m 最大为 10^6，内存限制为 1 GB，可以接受。

时间复杂度：建第一棵树复杂度为 \mathcal{O}(n)，后面每一次查找复杂度都是 \mathcal{O}(\log n) 的，合起来就是 \mathcal{O}(n+m \log n)。

现在我们开始编程。

我们不能像普通的线段树一样通过静态数组存储一个满二叉树，这样空间会直接炸掉。

我们可以写一个结构体，里面记录了这个节点的左儿子与右儿子以及它本身的值。

//由空间复杂度的分析可得数组大小
struct {int l, r, num;} tree[N << 5];

定义一个变量，表示当前分配的点的数量。

int rt;

每次新建节点时，只需要将 rt 加一。

我们定义一个数组，表示版本 i 的根节点位置以及现在有多少个版本：

int root[N], nowv;

我们先看怎么新建第一棵树（原理见注释）：

int build(int pl, int pr) { //返回值就是创建的这棵树的根节点的编号
    int cnt = ++rt, mid = (pl + pr) >> 1;
    if (pl == pr) { //区间只有一个数，直接输入
        scanf("%d", &tree[cnt].num);
        return cnt;
    }
    tree[cnt].l = build(pl, mid), tree[cnt].r = build(mid + 1, pr); //分开创建当前节点的左子树与右子树
    return cnt;
}

修改一个数：

//返回记录的修改“链”的根节点
int upd(int p, int c, int pl, int pr, int bef) { //bef指要修改的树
    int cnt = ++rt, mid = (pl + pr) >> 1;
    tree[cnt].l = tree[bef].l, tree[cnt].r = tree[bef].r; //将这个节点的左右子树都指向原来的树的左右子树
    if (pl == pr) { //区间内只有一个数，直接修改
        tree[cnt].num = c;
        return cnt;
    }
    if (p <= mid) tree[cnt].l = upd(p, c, pl, mid, tree[bef].l); //p在左子树
    else tree[cnt].r = upd(p, c, mid + 1, pr, tree[bef].r); //p在右子树
    return cnt;
}

查找：

//返回查找的数
int query(int p, int pl, int pr, int now) { //now就是现在正在查找的树
    if (pl == pr) return tree[now].num; //只有一个数，直接返回
    int mid = (pl + pr) >> 1;
    if (p <= mid) return query(p, pl, mid, tree[now].l); //p在左子树
    return query(p, mid + 1, pr, tree[now].r); //p在右子树
}

主函数部分：

int main() {
    int n, m;
    for (scanf("%d%d", &n, &m), root[nowv++] = build(1, n); m--;) {
        int v, op, p, c;
        scanf("%d%d%d", &v, &op, &p);
        if (op == 1) scanf("%d", &c), root[nowv++] = upd(p, c, 1, n, root[v]);
        else printf("%d\n", query(p, 1, n, root[nowv++] = root[v]));
    }
}

整理：

#include <cstdio>
const int N = 1e6 + 5;
int rt, root[N], nowv;
struct {int l, r, num;} tree[N << 5];
int build(int pl, int pr) {
    int cnt = ++rt, mid = (pl + pr) >> 1;
    if (pl == pr) {
        scanf("%d", &tree[cnt].num);
        return cnt;
    }
    tree[cnt].l = build(pl, mid), tree[cnt].r = build(mid + 1, pr);
    return cnt;
}
int upd(int p, int c, int pl, int pr, int bef) {
    int cnt = ++rt, mid = (pl + pr) >> 1;
    tree[cnt].l = tree[bef].l, tree[cnt].r = tree[bef].r;
    if (pl == pr) {
        tree[cnt].num = c;
        return cnt;
    }
    if (p <= mid) tree[cnt].l = upd(p, c, pl, mid, tree[bef].l);
    else tree[cnt].r = upd(p, c, mid + 1, pr, tree[bef].r);
    return cnt;
}
int query(int p, int pl, int pr, int now) {
    if (pl == pr) return tree[now].num;
    int mid = (pl + pr) >> 1;
    if (p <= mid) return query(p, pl, mid, tree[now].l);
    return query(p, mid + 1, pr, tree[now].r);
}
int main() {
    int n, m;
    for (scanf("%d%d", &n, &m), root[nowv++] = build(1, n); m--;) {
        int v, op, p, c;
        scanf("%d%d%d", &v, &op, &p);
        if (op == 1) scanf("%d", &c), root[nowv++] = upd(p, c, 1, n, root[v]);
        else printf("%d\n", query(p, 1, n, root[nowv++] = root[v]));
    }
}

于是这题在线正解完结。

离线（递归）

我们发现，每两个版本之间最多只会有一次修改，如果将版本画出来会形成一颗多叉树。以样例为例（边上只有一个数字代表查询，两个数字代表修改）：

我们可以想到通过递归的方法，每次经过一个边的时候就处理这个边所对应的操作。

写一个结构体用来存储操作：

struct op {int op, p, c, ind;}; //op是操作类型，p和c如题面所说，ind表示这个操作输出对应的序号（如果不是查询则为0）

每一条边上有且只会有一个操作，考虑邻接表。

std::vector<std::pair<int, op>> tree[N]; //每一个pair的第一个int表示指向的版本，第二个op表示这条边上的操作

定义一个存储查询的数组及表示有多少条查询的变量：

int result[N], resind;

定义 a 数组：

int a[N];

递归：

void dg(int p) { //遍历到第p个版本
    for (auto g : tree[p]) { //遍历自己的儿子
        const op &nop = g.second;
        if (nop.op == 1) { //修改操作
            int tmp = a[nop.p]; //存储原来的数
            a[nop.p] = nop.c, dg(g.first); //执行修改操作并处理儿子
            a[nop.p] = tmp; //还原原来的状态
        } else result[nop.ind] = a[nop.p], dg(g.first); //存储答案
    }
}

主函数：

int main() {
    int n, m, nowv = 0; //n与m如题意，nowv表示当前有多少个版本
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", a + i);
    for (int v, op, p, c; m--;) {
        scanf("%d%d%d", &v, &op, &p);
        if (op == 1) scanf("%d", &c);
        else c = 0, resind++; //增加一条查询
        tree[v].push_back({++nowv, {op, p, c, resind}});
    }
    dg(0);
    for (int i = 1; i <= resind; ++i) printf("%d\n", result[i]); //按照顺序输出查询
}

整理：

#include <cstdio>
#include <vector>
const int N = 1e6 + 5;
int a[N], result[N], resind;
struct op {int op, p, c, ind;};
std::vector<std::pair<int, op>> tree[N];
void dg(int p) {
    for (auto g : tree[p]) {
        const op &nop = g.second;
        if (nop.op == 1) {
            int tmp = a[nop.p];
            a[nop.p] = nop.c, dg(g.first);
            a[nop.p] = tmp;
        } else result[nop.ind] = a[nop.p], dg(g.first);
    }
}
int main() {
    int n, m, nowv = 0;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", a + i);
    for (int v, op, p, c; m--;) {
        scanf("%d%d%d", &v, &op, &p);
        if (op == 1) scanf("%d", &c);
        else c = 0, resind++;
        tree[v].push_back({++nowv, {op, p, c, resind}});
    }
    dg(0);
    for (int i = 1; i <= resind; ++i) printf("%d\n", result[i]);
}

又短又快又好理解，简直像是正解。

完结撒花~