Untitled

#include <iostream>
#include <algorithm>
#include <string>
#include <bitset> 
#include <vector>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <set>
#ifndef LOCAL
	#include <bits/stdc++.h>
	#define cerr if(false)cerr
#endif
 
using namespace std;
using ll = long long;
 
const int N = 1e6 + 66;
 
struct node {
	ll sum;
	node *l, *r;
	node(ll val = 0ll) : sum(val), l(nullptr), r(nullptr) {}
};
 
int n;
 
ll sum(node *a){ 
	return a ? a->sum : 0ll;
}
 
void upd_sum(node *a) {
	a->sum = sum(a->l) + sum(a->r);
}
 
node* upd(int pos, int val, node *t, int l = 0, int r = n) {
	if (r - l == 1) {
		return new node(val);
	}
	int m = (l + r) >> 1;
	node *ret = new node(0);
	if (pos < m) {
		ret->l = upd(pos, val, t ? t->l : nullptr, l, m);
		if (t)
			ret->r = t->r;
		upd_sum(ret);
		return ret;
	} else {
		ret->r = upd(pos, val, t ? t->r : nullptr, m, r);
		if (t)
			ret->l = t->l;
		upd_sum(ret);
		return ret;
	}
}
 
ll sum(int L, int R, node *t, int l = 0, int r = n) {
	if (!t) return 0ll;
	if (L <= l && r <= R) return t->sum;
	if (L >= r || l >= R) return 0ll;
	int m = (l + r) >> 1;
	return sum(L, R, t->l, l, m) + sum(L, R, t->r, m, r);
}
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int m;
	cin >> n >> m;
	vector<node*>t;
	t.emplace_back(new node());
	for (int i = 0 ; i < n ; ++ i) {
		int x;
		cin >> x;
		t[0] = upd(i, x, t[0]);
	}
	while (m--) {
		int type;
		cin >> type;
		if (type == 1) {
			int k, pos, x;
			cin >> k >> pos >> x;
			--k, --pos;
			t[k] = upd(pos, x, t[k]);
		} else if (type == 2) {
			int k, l, r;
			cin >> k >> l >> r;
			--k, --l;
			cout << sum(l, r, t[k]) << "\n";
		} else {
			int k;
			cin >> k;
			--k;
			t.emplace_back(t[k]);
		}
	}
}