persistent segment tree implementation in c++

persistent_seg.cpp

#include <bits/stdc++.h>

using namespace std;

int func(int a, int b) {
    // binary function
    // ex) return gcd(a, b);
    // ex) return a * b;
    // ex) return a ^ b;
    // BUT! associated law has to be held
    return a + b;
}

int inv_func(int a, int b) {
    // inverse function of binary function
    // func(a, b) == c then inv_func(c, b) == a
    // ex) return a / b;
    // ex) return a ^ b;
    return a - b;
}

vector<int> seg, root{0}, left, right;

int new_node(int v = 0, int l = 0, int r = 0) {
    seg.emplace_back(v);
    ::left.emplace_back(l);
    ::right.emplace_back(r);
    return seg.size() - 1;
}

int make_tree(int node, int l, int r, int index, int diff) {
    if(index < l || r < index) return node;
    if(l == r) return new_node(seg[node] + diff);
    int left = make_tree(::left[node], l, (l + r) >> 1, index, diff);
    int right = make_tree(::right[node], ((l + r) >> 1) + 1, r, index, diff);
    return new_node(func(seg[left], seg[right]), left, right);
}

int query(int node1, int node2, int l, int r, int start, int end) {
    if(start <= l && r <= end) return inv_func(seg[node2], seg[node1]);
    int mid = (l + r) >> 1;
    if(mid < start) return query(::right[node1], ::right[node2], mid + 1, r, start, end);
    if(mid + 1 > end) return query(::left[node1], ::left[node2], l, mid, start, end);
    return func(query(::left[node1], ::left[node2], l, mid, start, end),
                query(::right[node1], ::right[node2], mid + 1, r, start, end));
}

int main() {
    new_node();
    vector<int> v{1, 2, 3, 4};
    for(int i: v) {
        root.emplace_back(make_tree(root.back(), 0, INT_MAX, i, 1));
    }
    cout << query(root[0], root[3], 0, INT_MAX, 2, 3);
}