AlgorithmsThread 5: Persistent Data Structures

It basically is a way to use segment trees when the coordinates/N is huge (10^9 or 10^18) and they work in O(log(MAX)). Also they can do everything that can be done with regular segment trees. The only caveat is that their constant is a bit larger than regular semgent trees so in practice they are ~1.2-1.5 slower which is still fine for most problems.

The main idea is that initially you only have the root node and you extend it to the left/right only when there is a query that affects those nodes. This way this problem can be solved in O(log 10^18) online without compression (and probably it will pass).

node* query(int ql, int qr, int l, int r, node *root) {
 if(ql <= l && r <= qr) {
  DO SOMETHING
  return root;
 }

 int mid = (l + r) >> 1;
 if(root->l == NULL) {
  root->l = new node();
 }

 if(root->r == NULL) {
  root->r = new node();
 }

 if(ql <= mid) {
  root->l = query(ql, qr, l, mid, root->l);
 }

 if(mid < qr) {
  root->r = query(ql, qr, mid + 1, r, root->r);
 }

 root->pull();
 return root;
}