seg_persistente.cpp

#include <bits/stdc++.h>

using namespace std;

struct node {
	node *l, *r;
	int v;
	node () {
		l = r = nullptr;
		v = 0;
	}
};

inline int val(node *t) {
	if (t != nullptr) return t->v;
	return 0;
}

int n;
void update(node *old, node *no, int p, int v, int ini=1, int fim=n) {
	// Sempre iremos garantir que o no existe antes de realizar o update.
	if (ini == fim) {
		no->v = v;
		return;
	}

	int meio = (ini + fim) >> 1;

	if (p <= meio) {
		if (old == nullptr || old->l == nullptr) no->l = new node;
		else no->l = new node(*old->l);

		if(old != nullptr && old->r != nullptr) no->r = old->r; // MANTEM O ANTIGO

		update(old&&old->l?old->l:nullptr, no->l, p, v, ini, meio);
	}else {
		if (old == nullptr || old->r == nullptr) no->r = new node;
		else no->r = new node(*old->r);

		if(old != nullptr && old->l != nullptr) no->l = old->l; // MANTEM O ANTIGO

		update(old&&old->r?old->r:nullptr, no->r, p, v, meio+1, fim);
	}

	no->v = val(no->l) + val(no->r);
}

int query(node *no, int l, int r, int ini=1, int fim=n) {
	if(no == nullptr || ini > r || fim < l) return 0;
	if(l <= ini && fim <= r) return no->v;

	int meio = (ini + fim) >> 1;

	int p1 = query(no->l, l, r, ini, meio);
	int p2 = query(no->r, l, r, meio+1, fim);
	return p1 + p2;
}
vector<node*> versions;

int main() {
	int x;
	cin >> n;

	versions.push_back(nullptr);
	while (cin >> x && x) {
		if(x == 1) { // Adicionaremos uma nova versão baseada na versão ver
			int ver, p, v;
			cin >> ver >> p >> v;
			node *t = new node;
			if (ver < 0 || ver >= versions.size()) ver = versions.size()-1;

			update(versions[ver], t, p, v);

			versions.push_back(t);
		}else { // Query na versão ver
			int ver, l, r;
			cin >> ver >> l >> r;
			if (ver < 0 || ver >= versions.size()) ver = versions.size()-1;

			cout << query(versions[ver], l, r) << "\n";
		}
	}
	return 0;
}