Persistent Segment Tree

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 10;
struct node{
    node *l, *r;
    int cnt;

    node () {}
};

node pool[(1 << 17) * 17];
int tcnt;

node* alloc(){
    memset(pool + tcnt, 0, sizeof(node));
    return pool + tcnt++;
}

node *tree_head[MAXN];

node * init(int l, int r){
    node *ret = alloc();
    if(l != r) {
        int mid = (l + r) / 2;
        ret->l = init(l, mid);
        ret->r = init(mid + 1, r);
    }
    return ret;
}

void update(node * here, node *par, int l, int r, int val){
    if(l == r) {
        here->cnt = par->cnt + 1;
        return;
    }

    int mid = (l + r) / 2;
    if(val <= mid){
        here->l = alloc();
        here->r = par->r;
        update(here->l, par->l, l, mid, val);
    }
    else {
        here->l = par->l;
        here->r = alloc();
        update(here->r, par->r, mid + 1, r, val);
    }
    here->cnt = here->l->cnt + here->r->cnt;
}

int query(node *node1, node *node2, int l, int r, int k){
    if(l == r) return l;
    int ccc = node1->l->cnt - node2->l->cnt;
    int mid = (l + r) / 2;
    if(k <= ccc) return query(node1->l, node2->l, l, mid, k);
    else return query(node1->r, node2->r, mid + 1, r, k - ccc);
}