可持久化线段树

原理

见《进阶指南》第255页。

模板题

洛谷-P3919-【模板】可持久化线段树 1（可持久化数组）

#include <iostream>
using namespace std;

const int N = 1000010;
int n, a[N], m;
struct node {
    int ls, rs;
    int data;
    #define ls(x) t[x].ls
    #define rs(x) t[x].rs
    #define data(x) t[x].data
};
int tot, root[N];
node t[N * 20];

int build (int l, int r) {
    int cur = ++ tot;
    if (l == r) {
        data(cur) = a[l];
        return cur;
    }
    int mid = l + r >> 1;
    ls(cur) = build(l, mid);
    rs(cur) = build(mid + 1, r);
    return cur;
}
int modify (int prev, int l, int r, int idx, int val) {
    int cur = ++ tot;
    ls(cur) = ls(prev), rs(cur) = rs(prev);
    data(cur) = data(prev);
    if (l == r) {
        data(cur) = val;
        return cur;
    }
    int mid = l + r >> 1;
    if (idx <= mid)
        ls(cur) = modify(ls(prev), l, mid, idx, val);
    else
        rs(cur) = modify(rs(prev), mid + 1, r, idx, val);
    return cur;
}
int query (int cur, int l, int r, int idx) {
    if (l == r) return data(cur);
    int mid = l + r >> 1;
    if (idx <= mid)
        return query(ls(cur), l, mid, idx);
    else
        return query(rs(cur), mid + 1, r, idx);
}

int main () {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++ i) scanf("%d", &a[i]);

    root[0] = build(1, n);
    for (int i = 1, v, opt; i <= m; ++ i) {
        scanf("%d%d", &v, &opt);
        if (opt == 1) {
            int idx, val;
            scanf("%d%d", &idx, &val);
            root[i] = modify(root[v], 1, n, idx, val);
        } else {
            int idx;
            scanf("%d", &idx);
            printf("%d\n", query(root[v], 1, n, idx));
            root[i] = root[v];
        }
    }
    return 0;
}