不知道哪里错了，一直过不去

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 9000010;
int n,q;

struct node
{
	long long sg,ls=0,rs=0;
};
node tr[N];long long a[N];
long long root[N],tot=1,cnt=0;
void build(int l,int r,int &u)
{
	u=++cnt;
	if(l==r)
	{
		tr[u].sg=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,tr[u].ls);
	build(mid+1,r,tr[u].rs);
	
	tr[u].sg=tr[tr[u].ls].sg+tr[tr[u].rs].sg; 
}
void update(int l, int r, int& u, int old, int pos, int val) {
	u = ++cnt;
	tr[u] = tr[old];
	if (l == r) 
	{
		tr[u].sg = val;
		return;
	}
	int mid = (l + r) >> 1;
	if (pos <= mid) 
	{
		update(l, mid, tr[u].ls, tr[old].ls, pos, val);
	}
	else 
	{
		update(mid + 1, r, tr[u].rs, tr[old].rs, pos, val);
	}
	tr[u].sg = tr[tr[u].ls].sg + tr[tr[u].rs].sg;
}
int query(int ll,int rr,int l,int r,int u)
{
	if(l>=ll && r<=rr) return tr[u].sg;
	int mid=(l+r)>>1;
	int k=0;
	if(mid>=ll) k+=query(ll,rr,l,mid,tr[u].ls);
	if(mid<rr) k+=query(ll,rr,mid+1,r,tr[u].rs);
	return k;
}
signed main()
{
	scanf("%lld%lld",&n,&q);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	build(1,n,root[1]);
	while(q--)
	{
		int op,k,x,y;
		scanf("%lld%lld",&op,&k);
		if(op==1)
		{
			scanf("%lld%lld",&x,&y);
			if(x>n) continue;
			int newroot=0;
			update(1,n,newroot,root[k],x,y);
			root[k]=newroot;
		}
		if(op==2)
		{
			scanf("%lld%lld",&x,&y);//cout<<"asdf"<<endl;
			cout<<query(x,y,1,n,root[k])<<endl;
		}
		else
		{
			tot++;
			root[tot]=root[k];
		}
	}
}