可持久化数组

可持久化数组相比与一般的数组来说多了一个限制条件:可持久化。
原题中的数组则可以用线段树来优化。
而可持久化的暴力解法就是对于每个操作都开一个线段树，可是这样的耗费空间都太多了，因此我们选择动态开点。

动态开点：

定义结构体的时候就不能像普通线段树一样来定义了，应该定义为

struct data {
    int l, r, dat;//l,r分别代表左右端点，dat代表该节点的权值
}tree[N];

我们可以在原有节点基础上来增加新节点，而直接用

inline int newroot(int root)
{
    tree[++cnt] = tree[root];//使新节点的l,r,dat都与原节点相同。
    return cnt; 
}

线段树的操作：

有了动态开点，那线段树的操作就很好写了，代码也类似于普通线段树，有几个点需要注意，主要在代码中。

建树(建树其实就是动态开点)

int build(int left, int right, int root)
{
    root = ++cnt;
    if (left == right)
    {
        tree[root].dat = a[left];
        return cnt;
    }
    int mid = (left + right) >> 1;
    tree[root].l = build(ls);//ls -> left, mid, tree[root].l
    tree[root].r = build(rs);
    return root;
}

修改

int update(int left, int right, int root, int pos, int add)
{
    root = newroot(root);
    if (left == right)
    {
        tree[root].dat = add;
        return root;
    }
    //注意root << 1并不是root该节点的左儿子，因为之间有新节点，所以要用tree[root].l和tree[root].r来代替。 
    int mid = (left + right) >> 1;
    if (pos <= mid) tree[root].l = update(ls, pos, add);//访问左子树 
    else tree[root].r = update(rs, pos, add);//访问右子树
    return root;
}

查询

int query(int left, int right, int root, int pos)
{
    root = newroot(root);
    int mid = (left + right) >> 1;
    if (left == right) return tree[root].dat;
    if (pos <= mid) return query(ls, pos);
    else return query(rs, pos);
}

总代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring> 
#define N 60000010
#define ls left, mid, tree[root].l
#define rs mid + 1, right, tree[root].r 
using namespace std;
int n, m, cnt, a[N], r[N];
struct data {
    int l, r, dat;
}tree[N];
inline int newroot(int root)
{
    tree[++cnt] = tree[root];
    return cnt; 
}
int update(int left, int right, int root, int pos, int add)
{
    root = newroot(root);
    if (left == right)
    {
        tree[root].dat = add;
        return root;
    }
    //注意root << 1并不是root该节点的左儿子，因为之间有新节点，所以要用tree[root].l和tree[root].r来代替。 
    int mid = (left + right) >> 1;
    if (pos <= mid) tree[root].l = update(ls, pos, add);//访问左子树 
    else tree[root].r = update(rs, pos, add);//访问右子树
    return root;
}
int query(int left, int right, int root, int pos)
{
    root = newroot(root);
    int mid = (left + right) >> 1;
    if (left == right) return tree[root].dat;
    if (pos <= mid) return query(ls, pos);
    else return query(rs, pos);
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    r[0] = build(1, n, 0);//build(1, n, 0); //r[x]是第x版本上的根节点，而线段树中的几个基本操作返回的也就是根节点。
    for (int i = 1; i <= m; i++)
    {
        int a, b, c, d;
        scanf("%d%d%d", &a, &b, &c);
        if (b == 1)
        {
            scanf("%d", &d);
            r[i] = update(1, n, r[a], c, d);
        }       
        else
        {   
            printf("%d\n", query(1, n, r[a], c));
            r[i] = r[a];
        }
    }
    return 0;
}