P3919 【模板】可持久化数组（可持久化线段树/平衡树）（题解）

· · 题解

P3919 【模板】可持久化数组（可持久化线段树/平衡树）（题解）

题目传送门：

点我

解题思路：

用一棵可持久化线段树来记录数组中的树。
（蒟蒻我不想写可持久化平衡树）

题目注意点：

  1. 查询时应生成的树是查询到的那棵树
  2. 注意数组范围 错误QWQ
  3. 这道题毒瘤地让习惯开long long的人MLE了

补充：

可持久化线段树

  1. 可持久化定义（自行上网问度娘）
  2. 如何实现可持久化： 在每次修改结束后，建一棵新树。
  3. 空间太费： 最大限度地利用原节点。

eg:

像左下方这棵树，是由中间的表格生成的。

把第三个点改动，就生成了右边这棵树。

画红色圈的就是要改动的节点。

上方这个表格，第一行是数值，第二行是左孩子，第三行是右孩子。

带绿色框的是原始节点，红色的是新增节点，读者可自行理解。

最后再用一个数组root记录每次修改后的根节点。便可实现

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=30000005,maxm=1000005;
struct data     //可持久化线段树的节点
{
    int number,lson,rson;
    data() {number=0;lson=0;rson=0;}
    data(int n,int l,int r):number(n),lson(l),rson(r) {}
};
struct zhu_tree     //可持久化线段树
{
    data tree[maxn];
    int root[maxm],tsize;
    zhu_tree()      //初值
    {
        tsize=0;
        root[0]=1;      //不要忘了！！！
    }
    inline int add_node(int x)      //把x位的节点拷贝
    {
        tsize++;
        tree[tsize]=tree[x];
        return tsize;
    }
    void build(int &now,int l,int r,int da[])       //造一棵新树
    {
        tsize++;
        now=tsize;
        if(l==r)
        {
            tree[now].number=da[l];
            tree[now].lson=0;
            tree[now].rson=0;
            return;
        }
        int mid=(l+r)>>1;
        build(tree[now].lson,l,mid,da);
        build(tree[now].rson,mid+1,r,da);
    }
    int search(int now,int l,int r,int dw)      //查找节点
    {
        if(l==r) return tree[now].number;
        int mid=(l+r)>>1;
        if(dw<=mid) return search(tree[now].lson,l,mid,dw);
        return search(tree[now].rson,mid+1,r,dw);
    }
    void insert(int old,int &now,int l,int r,int dw,int dd)     //修改节点（名字不大好，莫怪）
    {
        now=add_node(old);
        if(l==r)
        {
            tree[now].number=dd;
            return;
        }
        int mid=(l+r)>>1;
        if(dw<=mid) insert(tree[old].lson,tree[now].lson,l,mid,dw,dd);
        else insert(tree[old].rson,tree[now].rson,mid+1,r,dw,dd);
    }
}tree;
int main()
{
    int n,m,a[maxm];
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    tree.build(tree.root[0],1,n,a);
    for(int i=1;i<=m;i++)
    {
        int v,f,l,val;
        scanf("%d%d%d",&v,&f,&l);
        if(f==1)
        {
            scanf("%d",&val);
            tree.insert(tree.root[v],tree.root[i],1,n,l,val);
        }
        if(f==2)
        {
            tree.root[i]=tree.root[v];
            printf("%d\n",tree.search(tree.root[i],1,n,l));
        }
    }
    return 0;
}