Persistent segment tree

PersistentSegmentTree.cpp

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

class Node {
   public:
    ll value;
    int l, r;
    shared_ptr<Node> left;
    shared_ptr<Node> right;

    Node(ll val = 0, int l = 0, int r = 0) : value(val), l(l), r(r), left(nullptr), right(nullptr) {}

    bool isOutOfRange(int queryL, int queryR) const {
        return queryR < queryL || r < l || queryR < l || r < queryL;
    }

    bool isFullyCovered(int queryL, int queryR) const {
        return queryL <= l && r <= queryR;
    }
};

class PersistentSegmentTree {
   private:
    vector<shared_ptr<Node>> roots;
    int size;

    shared_ptr<Node> build(const vector<ll>& arr, int l, int r) {
        auto node = make_shared<Node>(0, l, r);

        if (l == r) {
            node->value = arr[l];
            return node;
        }

        int mid = (l + r) / 2;

        node->left = build(arr, l, mid);
        node->right = build(arr, mid + 1, r);
        node->value = node->left->value + node->right->value;

        return node;
    }

    ll query(shared_ptr<Node> node, int l, int r) {
        if (!node || node->isOutOfRange(l, r)) {
            return 0;
        }

        if (node->isFullyCovered(l, r)) {
            return node->value;
        }

        return query(node->left, l, r) + query(node->right, l, r);
    }

    shared_ptr<Node> update(shared_ptr<Node> oldNode, int index, ll value) {
        auto node = make_shared<Node>(0, oldNode->l, oldNode->r);

        if (node->l == node->r) {
            node->value = value;
            return node;
        }

        int mid = (node->l + node->r) / 2;

        if (index <= mid) {
            node->left = update(oldNode->left, index, value);
            node->right = oldNode->right;
        } else {
            node->left = oldNode->left;
            node->right = update(oldNode->right, index, value);
        }

        node->value = node->left->value + node->right->value;
        return node;
    }

   public:
    PersistentSegmentTree(const vector<ll>& arr, int n) : size(n) {
        auto root = build(arr, 0, n - 1);
        roots.push_back(root);
    }

    ll query(int ver, int left, int right) {
        if (ver < 0 || ver >= roots.size()) {
            return 0;
        }

        return query(roots[ver], left, right);
    }

    void update(int ver, int index, ll value) {
        if (ver < 0 || ver >= roots.size()) {
            return;
        }
        
        roots[ver] = update(roots[ver], index, value);
    }

    void copy(int ver) {
        if (ver >= 0 && ver < roots.size()) {
            roots.push_back(roots[ver]);
        }
    }
};

int main() {
    ios::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);
    int n, q;
    cin >> n >> q;

    vector<ll> arr(n);

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    PersistentSegmentTree tree(arr, n);

    while (q--) {
        int type, k;
        cin >> type >> k;
        k--;

        if (type == 1) {
            int a;
            ll b;
            cin >> a >> b;
            tree.update(k, a - 1, b);
        } else if (type == 2) {
            int a, b;
            cin >> a >> b;
            cout << tree.query(k, a - 1, b - 1) << '\n';
        } else {
            tree.copy(k);
        }
    }
}