#include <iostream>
using namespace std;
struct tree
{
	int num, l, r;
	tree *lef, *rig;
}*root[1000010];
int n, m, a[1000010], v, op, loc, val;
void build(tree *r)
{
	if (r->l == r->r)
	{
		r->num = a[r->l];
		return;
	}
	int mid = (r->l + r->r) >> 1;
	tree *ll, *rr;
	ll = new tree;
	rr = new tree;
	ll->l = r->l;
	rr->r = r->r;
	ll->r = mid;
	rr->l = mid + 1;
	build(ll);
	build(rr);
	r->lef = ll;
	r->rig = rr;
	r->num = ll->num + rr->num;
	return;
}
int query(tree *r, int x)
{
	if (r->l == r->r)
		return r->num;
	int mid = (r->l + r->r) >> 1;
	if (x > mid)
		return query(r->rig, x);
	return query(r->lef, x);
}
tree* update(tree *r, int x, int val)
{
	if (r->l == r->r)
	{
		tree *u = new tree;
		u->l = r->l;
		u->r = r->r;
		u->num = val;
		return u;
	}
	int mid = (r->l + r->r) >> 1;
	if (x > mid)
	{
		tree *u = new tree, *ll = update(r->rig, x, val);
		u->l = r->l;
		u->r = r->r;
		u->num = ll->num + r->lef->num;
		u->lef = r->lef;
		u->rig = ll;
		return u;
	}
	else
	{
		tree *u = new tree, *ll = update(r->lef, x, val);
		u->l = r->l;
		u->r = r->r;
		u->num = ll->num + r->rig->num;
		u->rig = r->rig;
		u->lef = ll;
		return u;
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	root[0] = new tree;
	root[0]->l = 1;
	root[0]->r = n;
	build(root[0]);
	for (int i = 1; i <= m; i++)
	{
		cin >> v >> op >> loc;
		if (op == 1)
		{
			cin >> val;
			root[i] = update(root[v], loc, val);
		}
		else
		{
			root[i] = root[v];
			cout << query(root[i], loc) << "\n";
		}
	}
}

评测记录