可持久化线段树

emm，也算是一个动态的数据结构。

可持久化就是指，我可以访问以前的状态，也可以修改之前的内容。

struct tree

线段树，这里用结构体存是因为在可持久化的线段树里面，左右儿子并不满足 x<<1的关系

struct {

  int l,r,val;

}tree[N];

Clone(int node)

复制节点。

原因： 因为在更新节点的时候，我们需要保留之前版本，所以我们只能新开一个版本来存放当前版本的值。

作用： 尽可能减少新点，优化内存的使用

int clone(int node)

{

  top++;

  tree[top]=tree[node];

  return top;

}

int build(int node,int be,int en)

建树,与普通线段树建树不同的是，这里建树的时候会返回当前建树的编号.

返回建树节点的作用 : 更新父/根节点的信息.

int build( int node,int be,int en )

{

  node=++top;

  if( be==en )

  {

    tree[node].val=a[be];

    return top;

  }

  int mid=(be+en)>>1;

  tree[node].l=build( tree[node].l,be,mid );

  tree[node].r=build( tree[node].r,mid+1,en );

  return node;

}

int update(int node,int be,int en,int x,int v)

更新区间,因为需要保存各个版本的内容,所以更新的时候需要首先复制更新前的内容,然后再更新子区间,然后递归更新子区间.并返回该次更新后的新编号.

int update(int node,int be,int en,int x,int v)

{

  node=clone(node);

  if( be==en )

  {

    tree[node].val=v;

    return node;

  }

  int mid=be+en>>1;

  if( x<=mid ) tree[node].l=update( tree[node].l,be,mid,x,v );

  else tree[node].r=update( tree[node].r,mid+1,en,x,v );

  return node;

}

query(int node,int be,int en,int x)

去普通的没有区别,be和en就是这个node所在区间的左右范围,x是单点查询位置

int query(int node,int be,int en,int x)

{

  if(be==en) return tree[node].val;

  int mid=be+en>>1;

  if( x<=mid )

      return query( tree[node].l,be,mid,x );

  return query( tree[node].r,mid+1,en,x );

}

Code

#include<bits/stdc++.h>

using namespace std;

const int N=4e7+12;

int top,x,y,mode,rt,a[N],n,m,root[N];

struct {

  int l,r,val;

}tree[N];

int clone(int node)

{

  top++;

  tree[top]=tree[node];

  return top;

}

int build( int node,int be,int en )

{

  node=++top;

  if( be==en )

  {

    tree[node].val=a[be];

    return top;

  }

  int mid=(be+en)>>1;

  tree[node].l=build( tree[node].l,be,mid );

  tree[node].r=build( tree[node].r,mid+1,en );

  return node;

}

int update(int node,int be,int en,int x,int v)

{

  node=clone(node);

  if( be==en )

  {

    tree[node].val=v;

    return node;

  }

  int mid=be+en>>1;

  if( x<=mid ) tree[node].l=update( tree[node].l,be,mid,x,v );

  else tree[node].r=update( tree[node].r,mid+1,en,x,v );

  return node;

}

int query(int node,int be,int en,int x)

{

  if(be==en) return tree[node].val;

  int mid=be+en>>1;

  if( x<=mid )

      return query( tree[node].l,be,mid,x );

  return query( tree[node].r,mid+1,en,x );

}

int main(){

  cin>>n>>m;

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

  root[0]=build(0,1,n);

  for(int i=1;i<=m;i++)

  {

    scanf("%d %d %d",&rt,&mode,&x);

    if( mode==1 )

    {

      scanf("%d",&y);

      root[i]=update(root[rt],1,n,x,y);

    }

    else{

      printf("%d\\n",query(root[rt],1,n,x));

      root[i]=root[rt];

    }



  }



}