Editing Treap (section)

== Implicit treap ==
An implicit treap <ref name=":0">{{Cite web|title=Treap - Competitive Programming Algorithms|url=https://cp-algorithms.com/data_structures/treap.html#toc-tgt-1|access-date=2021-11-21|website=cp-algorithms.com}}</ref>{{unreliable source?|date=December 2021}} is a simple variation of an ordinary treap which can be viewed as a dynamic array that supports the following operations in <math>O(\log n)</math>:

* Inserting an element in any position
* Removing an element from any position
* Finding sum, minimum or maximum element in a given range.
* Addition, painting in a given range
* Reversing elements in a given range 

The idea behind an implicit treap is to use the array index as a key, but to not store it explicitly. Otherwise, an update (insertion/deletion) would result in changes of the keys in <math>O(n)</math> nodes of the tree. 

The key value ('''implicit key)''' of a node T is the number of nodes less than that node plus one. Note that such nodes can be present not only in its left subtree but also in left subtrees of its ancestors P,  if T is in the right subtree of P.

Therefore we can quickly calculate the implicit key of the current node as we perform an operation by accumulating the sum of all nodes as we descend the tree. Note that this sum does not change when we visit the left subtree but it will increase by <math>cnt (T\rightarrow L)+1</math> when we visit the right subtree.

The join algorithm for an implicit treap is as follows:<syntaxhighlight lang="c" line="1">
void join (pitem & t, pitem l, pitem r) {
    if (!l || !r)
        t = l ? l : r;
    else if (l->prior > r->prior)
        join (l->r, l->r, r),  t = l;
    else
        join (r->l, l, r->l),  t = r;
    upd_cnt (t);
}
</syntaxhighlight><ref name=":0" />

The split algorithm for an implicit treap is as follows:<syntaxhighlight lang="c" line="1">
void split (pitem t, pitem & l, pitem & r, int key, int add = 0) {
    if (!t)
        return void( l = r = 0 );
    int cur_key = add + cnt(t->l); //implicit key
    if (key <= cur_key)
        split (t->l, l, t->l, key, add),  r = t;
    else
        split (t->r, t->r, r, key, add + 1 + cnt(t->l)),  l = t;
    upd_cnt (t);
}
</syntaxhighlight><ref name=":0" />

=== Operations ===

==== Insert element ====
To insert an element at position ''pos'' we divide the array into two subsections ''[0...pos-1]'' and ''[pos..sz]'' by calling the '''''split''''' function and we get two trees <math>T1</math> and <math>T2
</math> . Then we merge <math>T1</math> with the new node by calling the '''''join''''' function. Finally we call the join function to merge <math>T1</math> and <math>T2
</math>.

==== Delete element ====
We find the element to be deleted and perform a join on its children L and R. We then replace the element to be deleted with the tree that resulted from the join operation. 

==== Find sum, minimum or maximum in a given range ====
To perform this calculation we will proceed as follows:

* First we will create an additional field F to store the value of the target function for the range represented by that node. we will create a function that calculates the value F based on the values of the L and R children of the node. We will call this target function at the end of all functions that modify the tree, ''i.e.'', split and join.  
* Second we need to process a query for a given range [A..B]: We will call the '''s''plit''''' function twice and split the treap into <math>T1</math> which contains <math>\{1..A-1\}
</math>, <math>T2
</math> which contains <math>\{A..B\}
</math>, and '''''<math>T3</math>''''' which contains <math>\{B+1..n\}
</math>. After the query is answered we will call the '''''join''''' function twice to restore the original treap.

==== Addition/painting in a given range ====
To perform this operation we will proceed as follows:

* We will create an extra field D which will contain the added value for the subtree. We will create a function '''''push''''' which will be used to propagate this change from a node to its children. We will call this function at the beginning of all functions which modify the tree, ''i.e.'', split and join so that after any changes made to the tree the information will not be lost.

==== Reverse in a given range ====
To show that the subtree of a given node needs to be reversed for each node we will create an extra boolean field R and set its value to true. To propagate this change we will swap the children of the node and set R to true for all of them.