segment tree implicita

#include "bits/stdc++.h"
#define MAX 100007

using namespace std;

struct node {
    int val;
    node* l, *r;
    node() {}
    node(node* _l, node* _r, int v) {
        l = _l;
        r = _r;
        val = v;
    }
};

int arr[MAX];
node* version[MAX];

node* update(node* no, int l, int r, int idx, int value) {
    if (l == r) return new node(NULL, NULL, value);

    int mid = (l+r) / 2;
    node* ret = new node(no->l, no->r, 0);
    if (idx <= mid) ret->l = update(no->l, l, mid, idx, value);
    else ret->r = update(no->r, mid+1, r, idx, value);

    ret->val = ret->l->val + ret->r->val;
    return ret;
}

int query(node* no, int l, int r, int x, int y) {
    if (x > r || y < l || l > r) return 0;
    if (x <= l && r <= y) return no->val;

    int mid = (l+r) / 2;
    return query(no->l,l, mid,l,r) +
           query(no->r,mid+1,r,l,r);
}

int main() {
    node *root = new node(NULL, NULL, 0);
    version[0] = root;
    int n; cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> arr[i];
        version[i] = update(version[i-1], 0, n-1, i, arr[i]);
    }

    return 0;
}