主席树模板 全输出0 求助！！！

#include<cstdio>
#include<algorithm>

#define N 1000005
#define M 1000005

using namespace std;

int read()
{
	int x=0,w=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*w;
}

int n,m;
int a[N];

struct Segment_Tree{
	int l,r;
	int val;
}tree[N];
int tree_cnt=0;
int root[M];
int clone(int node)
{
	tree[++tree_cnt]=tree[node];
	return tree_cnt;
}
void build(int &node,int left,int right)
{
	node=++tree_cnt;
	if(left==right)
	{
		tree[node].val=a[left];
		return;
	}
	int mid=(left+right)>>1;
	build(tree[node].l,left,mid);
	build(tree[node].r,mid+1,right);
	return;
}
void update(int &node,int left,int right,int x,int value)
{
	node=clone(node);
	if(left==right)
	{
		tree[node].val=value;
		return;
	}
	int mid=(left+right)>>1;
	if(x<=mid) update(tree[node].l,left,mid,x,value);
	else update(tree[node].r,mid+1,right,x,value);
	return;
}
int query(int node,int left,int right,int x)
{
	if(left==right) return tree[node].val;
	int mid=(left+right)>>1;
	if(x<=mid) return query(tree[node].l,left,mid,x);
	else return query(tree[node].r,mid+1,right,x);
}

int main()
{
	n=read(),m=read();
	for(int i=1;i<=n;i++)
		a[i]=read();
	build(root[0],1,n);
	for(int i=1;i<=m;i++)
	{
		int v,op;
		scanf("%d%d",&v,&op);
		if(op==1)
		{
			int loc,value;
			scanf("%d%d",&loc,&value);
			update(root[v],1,n,loc,value);
		}
		if(op==2)
		{
			int loc;
			scanf("%d",&loc);
			printf("%d\n",query(root[v],1,n,loc));
			root[i]=root[v];
		}
	}
	return 0;
}