Cartesian trees by implicit key + space compression

Before reading this article, you need to understand what a Cartesian tree is by an implicit key (this is not the topic of one article, so it’s better to read about it here ). Space compression is a method used to compress on a piece of data. For example, instead of storing the set {1, 1, 1, 2, 2, 2, 3, 1, 1} we will store {1 x 3, 2 x 3, 3 x 1, 1 x 2}.

Now we will try to compress space using this method and be able to perform online operations with any segment.



Immediately give my implementation of such trees

struct treap_node { int x, y; treap_node *l, *r, *p; int width; int val; //    void push() { //       } //  ,     void update() { x = width; if (l) x += l -> x; if (r) x += r -> x; if (l) l -> p = this; if (r) r -> p = this; //   ,    ,      } treap_node(int _width, int _val) { //   // val -  , width -    y = (rand() << 16) + rand(); l = r = p = NULL; width = _width; val = _val; update(); } }; //  2  treap_node* merge(treap_node *l, treap_node *r) { if (l == NULL) return r; if (r == NULL) return l; if (l -> y >= r -> y) { l -> push(); l -> r = merge(l -> r, r); l -> update(); return l; } else { r -> push(); r -> l = merge(l, r -> l); r -> update(); return r; } } //  1   2 void split(treap_node *t, int x, treap_node *&l, treap_node *&r) { if (t == NULL) { l = r = NULL; return; } t -> push(); if ((t -> l == NULL ? 0 : t -> l -> x) >= x) { split(t -> l, x, l, t -> l); if (l != NULL) l -> p = NULL; t -> update(); r = t; return; } else if ((t -> l == NULL ? 0 : t -> l -> x) + t -> width <= x) { split(t -> r, x - (t -> l == NULL ? 0 : t -> l -> x) - t -> width, t -> r, r); if (r != NULL) r -> p = NULL; t -> update(); l = t; return; } else { //   .       ,      treap_node *t1 = new treap_node(x - (t -> l == NULL ? 0 : t -> l -> x), t -> val); treap_node *t2 = new treap_node(t -> width - t1 -> width, t -> val); l = merge(t -> l, t1); r = merge(t2, t -> r); l -> p = NULL; r -> p = NULL; delete(t); } } 

Note that, compared with ordinary Cartesian trees, we have the width property in the structure — the width of the segment stored at our current vertex. And val is the value itself.

Another major change is the split function.

 else { //   .       ,      treap_node *t1 = new treap_node(x - (t -> l == NULL ? 0 : t -> l -> x), t -> val); treap_node *t2 = new treap_node(t -> width - t1 -> width, t -> val); l = merge(t -> l, t1); r = merge(t2, t -> r); l -> p = NULL; r -> p = NULL; delete(t); } 

Here another part appeared if. Which refers to the division of the segment into 2 subsegments. And then gluing in the left and right side.



We will not change the merge function, since in the task for which I use it, this does not affect the asymptotics. By this, I solve the problem of space compression, and I can respond to inquiries online. In principle, if anyone needs it, you can rewrite the function mergege to merge two segments. Instead of reading all possible data, setting fixed segments, and then searching for the necessary segment numbers with a binpoisk, and making the necessary changes in the segment tree, I’m doing a little if for tighter asymptotics. Truth has to use Cartesian trees. For me, writing is much more convenient and faster. Maybe it will be useful to somebody.