专栏文章

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

bb__b
P3919题解参与者 5已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@mip3he7d
此快照首次捕获于
2025/12/03 05:33
3 个月前
此快照最后确认于
2025/12/03 05:33
3 个月前
查看原文
也许是我写过最长的题解。
在这里介绍两种做法：在线的 O(nlog⁡n)\mathcal{O}(n\log n) 做法（正解）与离线的 O(n)\mathcal{O}(n) 做法。
（感谢这篇题解为我提供的离线方案的思路。）

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

一种简单，容易想到的暴力做法就是每一次创建一个新版本就复制一个新数组，时间和空间复杂度都是 O(mn)\mathcal{O}(mn)（mm 次操作，每次创建一个大小为 nn 的数组，从原数组复制要进行 nn 次操作）。本题 n≤106n \leq 10^6，m≤106m \leq 10^6，这种做法显然不可接受。
我们观察需要创建新版本的场景，可以发现每次最多只会修改一个数，有时甚至不会修改，这些不修改的数字如果每一次都复制的话代价太高了。很容易想到每一次只记录修改的部分。
我们可以使用一种叫做可持久化线段树的数据结构。（没学过线段树的请右转学习线段树。）
我们现在先将版本 00 到版本 22 的线段树单独画出来：
我们发现版本 00 和版本 11 是重复的，我们可以直接将这些节点合并（将第二颗树的根节点的儿子设成第一颗树的根节点的儿子）：
对于版本 22，它只修改了一个数，我们可以想到只记录根节点到修改部分的一条“链”，其余的按照上面的方法操作：
总结：先将版本 00 的树完整的记录下来，接着之后的版本只记录修改的部分。
现在我们考虑复杂度：
空间复杂度：版本 00 要记录所有的数，会有 2n−12n-1 个节点。总共有 mm 个版本。假设每一个版本都有修改，那么每一次都要记录长为 ⌈log⁡2n⌉+1\lceil \log_2 n \rceil+1 的“链”，空间复杂度约为 O(n+mlog⁡2n)\mathcal{O}(n+m\log_2 n)。在此题中 nn 和 mm 最大为 10610^6，内存限制为 11 GB，可以接受。
时间复杂度：建第一棵树复杂度为 O(n)\mathcal{O}(n)，后面每一次查找复杂度都是 O(log⁡n)\mathcal{O}(\log n) 的，合起来就是 O(n+mlog⁡n)\mathcal{O}(n+m \log n)。
现在我们开始编程。
我们不能像普通的线段树一样通过静态数组存储一个满二叉树，这样空间会直接炸掉。
我们可以写一个结构体，里面记录了这个节点的左儿子与右儿子以及它本身的值。
CPP
//由空间复杂度的分析可得数组大小
struct {int l, r, num;} tree[N << 5];
定义一个变量，表示当前分配的点的数量。
CPP
int rt;
每次新建节点时，只需要将 rt 加一。
我们定义一个数组，表示版本 ii 的根节点位置以及现在有多少个版本：
CPP
int root[N], nowv;
我们先看怎么新建第一棵树（原理见注释）：
CPP
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;
}
修改一个数：
CPP
//返回记录的修改“链”的根节点
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;
}
查找：
CPP
//返回查找的数
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在右子树
}
主函数部分：
CPP
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]));
    }
}
整理：
CPP
#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]));
    }
}
于是这题在线正解完结。

离线（递归）

我们发现，每两个版本之间最多只会有一次修改，如果将版本画出来会形成一颗多叉树。以样例为例（边上只有一个数字代表查询，两个数字代表修改）：
我们可以想到通过递归的方法，每次经过一个边的时候就处理这个边所对应的操作。
写一个结构体用来存储操作：
CPP
struct op {int op, p, c, ind;}; //op是操作类型，p和c如题面所说，ind表示这个操作输出对应的序号（如果不是查询则为0）
每一条边上有且只会有一个操作，考虑邻接表。
CPP
std::vector<std::pair<int, op>> tree[N]; //每一个pair的第一个int表示指向的版本，第二个op表示这条边上的操作
定义一个存储查询的数组及表示有多少条查询的变量：
CPP
int result[N], resind;
定义 aa 数组：
CPP
int a[N];
递归：
CPP
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); //存储答案
    }
}
主函数：
CPP
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]); //按照顺序输出查询
}
整理：
CPP
#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]);
}
又短又快又好理解，简直像是正解。
完结撒花~

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...