Range queries and copies

#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<int> v;
vector<int> seg, e, d;

int create()
{
    seg.push_back(0);
    e.push_back(0);
    d.push_back(0);
    return seg.size()-1;
}

void copy(int pos, int novo)
{
    seg[novo] = seg[pos];
    e[novo] = e[pos];
    d[novo] = d[pos];
}

int update(int pos, int ini, int fim, int id, int val)
{
    if (id < ini || id > fim) return pos;
    int novo = create();
    copy(pos, novo);
    if (ini == fim)
    {
        seg[novo] = val;
        return novo;
    }
    int m = (ini + fim) >> 1;
    if (id <= m)
    {
        e[novo] = update(e[novo], ini, m, id, val);
    }
    else
    {
        d[novo] = update(d[novo], m+1, fim, id, val);
    }
    seg[novo] = seg[e[novo]] + seg[d[novo]];
    return novo;
}

int query(int pos, int ini, int fim, int p, int q)
{
    if (q < ini || p > fim) return 0;
    if (pos == 0) return 0;
    if (p <= ini && fim <= q) return seg[pos];
    int m = (ini + fim) >> 1;
    return (query(e[pos], ini, m, p, q) + query(d[pos], m+1, fim, p, q));
}

void build(int pos, int ini, int fim)
{
    if (ini == fim)
    {
        seg[pos] = v[ini];
        return;
    }
    int m = (ini + fim) >> 1;
    e[pos] = create();
    d[pos] = create();
    build(e[pos], ini,  m );
    build(d[pos], m+1, fim);
    seg[pos] = seg[e[pos]] + seg[d[pos]];
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N, Q;
    cin >> N >> Q;
    v.resize(N+1);
    for (int i = 1; i <= N; i++) cin >> v[i];
    vector<int> raiz(2);
    create(); create();
    raiz[1] = 1;
    build(1, 1, N);
    while (Q--)
    {
        int type;
        cin >> type;
        if (type == 1)
        {
            int K, id, val;
            cin >> K >> id >> val;
            raiz[K] = update(raiz[K], 1, N, id, val);
        }
        else if (type == 2)
        {
            int K, p, q;
            cin >> K >> p >> q;
            cout << query(raiz[K], 1, N, p, q) << '\n';
        }
        else
        {
            int K;
            cin >> K;
            raiz.push_back(create());
            copy(raiz[K], raiz.back());
        }
    }
}