persistent segtree.sublime-snippet

<snippet>
	<content><![CDATA[
struct Node {
    int val;
    Node* left, * right;

    Node(int v = 0, Node* l = nullptr, Node* r = nullptr) : val(v), left(l), right(r) {}
};

constexpr int MAX_SIZE = 10000000;
Node nodes[MAX_SIZE];
int nodeCounter = 0;

class PersistentSegmentTree {
public:
    vector<Node*> versions;
    vector<int> arr; // Store the array here
    Node* garbage = getNode(0);

    Node* getNode(int val, Node* l = nullptr, Node* r = nullptr) {
        if (nodeCounter < MAX_SIZE) {
            nodes[nodeCounter].val = val;
            nodes[nodeCounter].left = l;
            nodes[nodeCounter].right = r;
            return &nodes[nodeCounter++];
        }
        return nullptr;
    }

    Node* unite(Node* leftNode, Node* rightNode) {
        return getNode(leftNode->val + rightNode->val, leftNode, rightNode);
    }

    template<typename T>
    Node* initNode(T val) {
        return getNode(val);
    }

    template<typename T>
    Node* upd(Node* prev, int low, int high, int idx, T val) {
        if (low == high) {
            return initNode(val);
        }

        int mid = (low + high) / 2;
        if (idx <= mid) {
            return unite(upd(prev->left, low, mid, idx, val), prev->right);
        } else {
            return unite(prev->left, upd(prev->right, mid + 1, high, idx, val));
        }
    }

    Node* get(Node* node, int low, int high, int qlow, int qhigh) {
        // debug(low, high, qlow, qhigh);
        if (node == nullptr || qlow > high || qhigh < low) {
            return garbage;
        }

        if (qlow <= low && qhigh >= high) {
            return node;
        }

        int mid = (low + high) / 2;
        return unite(get(node->left, low, mid, qlow, qhigh), get(node->right, mid + 1, high, qlow, qhigh));
    }



    PersistentSegmentTree(vector<int>& input_arr) : arr(input_arr) {
        versions.push_back(build(0, arr.size() - 1, arr));
    }

    template<typename T>
    void upd(int version, int idx, T val) {
        versions.push_back(upd(versions[version], 0, (int)arr.size() - 1, idx, val));
    }

    template<typename T>
    void upd(int idx, T val) {
        upd(versions.size() - 1, idx, val);
    }

    Node* get(int version, int qlow, int qhigh) {
        return get(versions[version], 0, (int)arr.size() - 1, qlow, qhigh);
    }

    Node* get(int qlow, int qhigh) {
        return get(versions.back(), 0, (int)arr.size() - 1, qlow, qhigh);
    }

    Node* build(int low, int high, vector<int>& input_arr) {
        if (low == high) {
            return initNode(input_arr[low]);
        }

        int mid = (low + high) / 2;
        return unite(build(low, mid, input_arr), build(mid + 1, high, input_arr));
    }
};
]]></content>
	<!-- Optional: Set a tabTrigger to define how to trigger the snippet -->
	<tabTrigger>persistent segtree</tabTrigger>
	<!-- Optional: Set a scope to limit where the snippet will trigger -->
	<!-- <scope>source.python</scope> -->
</snippet>