Cartesian tree: Part 3. Cartesian tree by implicit key

Table of Contents (for now)

Part 1. Description, operation, application.
Part 2. Valuable information in the tree and multiple operations with it.
Part 3. The Cartesian tree by implicit key.
To be continued ...

Very strong witchcraft

After all the heaps of opportunities that the Cartesian tree gave us in the previous two parts, today I will do something strange and blasphemous with it. Nevertheless, this action will allow to consider a tree in a completely new incarnation - as a kind of improved and powerful array with additional features. I will show you how to work with it, I will show that all operations with the data from the second part are also saved for the modified tree, and then I will cite several new and useful ones.

Recall the structure of the deramids. It contains the key x , for which the deramid is a search tree, the random key y , for which the deramid is a heap, and also, perhaps, some user information c (cost). Let's do the impossible and consider the deramid ... without the x keys. That is, we will have a tree in which the x key is not present at all, and the y keys are random. Accordingly, why it is needed is generally incomprehensible :)
')
In fact, this structure is regarded as a Cartesian tree, in which the keys x are still somewhere, but we are not informed. However, they swear that the condition of a binary search tree is fulfilled for them. Then you can imagine that these unknown X's are numbers from 0 to N-1 and implicitly arrange them according to the tree structure:

It turns out that in the tree it is as if the keys at the vertices are not marked, but the vertices themselves are numbered. Moreover, they are numbered in the in-order bypass order already familiar with the previous part. A tree with clearly numbered vertices can be viewed as an array, in which the index is the same implicit key, and the content is user information c . The games are needed only for balancing, these are internal details of the data structure that are not needed by the user. X really is not, in principle, they do not need to be stored.

Unlike the last part, this array does not automatically acquire any properties, like sorting. After all, we have no structural restrictions on information, and it can be stored in the peaks at any time.

Main applications

Now we should talk about why such an interpretation is generally needed.
For example, have you ever wanted to merge two arrays? That is, simply assign one of them to the end of the other, while not copying all the elements of the second in O (N) in the loop. With the Cartesian tree using an implicit key, you have such an opportunity: after all, nobody took away the Merge operation from us.

Stop-stop-stop, but Merge was written for an explicit Cartesian tree. So its algorithm will have to be reworked here? Not really. Look again at its code.

 public static Treap Merge(Treap L, Treap R) { if (L == null) return R; if (R == null) return L; if (Ly > Ry) { var newR = Merge(L.Right, R); return new Treap(Lx, Ly, L.Left, newR); } else { var newL = Merge(L, R.Left); return new Treap(Rx, Ry, newL, R.Right); } } 

The Merge operation, as you remember, relies on the fact that all the keys of the left input tree L do not exceed the keys of the right input tree R. Assuming that this condition is met, it produces a merge, disregarding the keys in principle: during the execution of the algorithm, only priorities are compared.

It turns out that the Merge operation we cheat here in the most arrogant way: she expects that she will be given trees with ordered keys, and we slip trees without keys at all :) However, the assumption that there are clear keys in the trees, and they are ordered, will force her to merge trees so that the L keys will turn out to be in a tree structure in some sense earlier than the R keys - because the condition of the search tree must be satisfied. That is: if in the tree L there were N elements, and in the tree R, respectively, M elements, then after merging the elements of the tree R will automatically acquire implicit numbers from N to N + M-1 . According to the tree structure, the Merge operation will automatically distribute them appropriately, and the priorities that it takes into account will perform “quasi-balancing”. Thus, we kind of attributed the “array” R to the “array” L.

As for the sources, we only need to create a new data type ImplicitTreap without the x key, and for it the corresponding private constructor. All Merge code will remain the same. Of course, this is taking into account that here is the version without calculating multiple queries - the functions of “restoring justice” and “pushing promises”, implemented in the second part, will also remain in the Merge in their old places.

For complete clarity, I will take two random implicit Cartesian trees and give them in the figure along with the result of the merge. Priorities are chosen randomly, so the actual structure of both trees and the result can be very different. But it does not matter - the structure of the array, i.e. the order of the elements c is always preserved.
The orange arrow is the path to the recursion in Merge.


Now it's time to Split. It’s not so easy to fool it anymore: the Split operation, on the contrary, is not interested in priorities, it only compares the keys. We'll have to think about how she will compare vertices in an implicit tree. Although in fact the problem lies higher: what does the Split operation do in general in the new data structure? Previously, she cut the tree by key, but here we don’t have the keys, which need to be cut.

There are no keys, however there is their implicit representation - array indices. Thus, the essence of cutting has changed somewhat: we want to split a tree into two so that exactly x ₀ elements are in the left, and all the others are in the right. In the “massive” interpretation, this means the separation of x0 elements from the array from the beginning into a new array.

How to perform a new Split operation? It considers, as before, two cases: the root T appears in the left result L or in the right R. In the left one it will be if its index in the array is less than x ₀ , otherwise in the right one. And what is the index of the top of the tree in the array? We already know how to work with it from the second part: it is enough to store the sizes of subtrees in the tree tops. Then the selection process is easily restored.

Let S _L be the size of the left subtree ( T.Left.Size ).
If S _L +1 ≤ x ₀ , then the root will be in the left result. So you need to recursively cut the right subtree. But cut by another key, by x ₀ -S _L -1 , because S _L +1 element has already fallen into the desired left result.
If S _L +1> x ₀ , then the root will be in the right result. Now you need to recursively cut the left subtree. This case is not quite symmetric, as before: we cut the subtree with the same key x ₀ , because at this recursion step we split the elements into the right result, not the left result.

In the figure, a Cartesian tree with subtree dimensions is taken and split by x ₀ = 6 .

The source code of the new Split, along with the new class procurement - without a key and with another private designer.
Split I give again so far without multiple operations - the reader can restore these lines on their own, they have not gone from their old places. But we must not forget about the recalculation of the sizes of subtrees.

 private int y; public double Cost; public ImplicitTreap Left; public ImplicitTreap Right; public int Size = 1; private ImplicitTreap(int y, double cost, ImplicitTreap left = null, ImplicitTreap right = null) { this.y = y; this.Cost = cost; this.Left = left; this.Right = right; } public static int SizeOf(ImplicitTreap treap) { return treap == null ? 0 : treap.Size; } public void Recalc() { Size = SizeOf(Left) + SizeOf(Right) + 1; } //    -  Split public void Split(int x, out ImplicitTreap L, out ImplicitTreap R) { ImplicitTreap newTree = null; int curIndex = SizeOf(Left) + 1; if (curIndex <= x) { if (Right == null) R = null; else Right.Split(x - curIndex, out newTree, out R); L = new ImplicitTreap(y, Cost, Left, newTree); L.Recalc(); } else { if (Left == null) L = null; else Left.Split(x, out L, out newTree); R = new ImplicitTreap(y, Cost, newTree, Right); R.Recalc(); } } 

Now, after we wrote for the array Split and Merge, working in logarithmic time, it is time to apply them somewhere. Let's play around with the array.

Array games

Insert

Focus №1 - we insert the element inside the array to the required position Pos for O (log ₂ N), and not for O (N), as usual.

In principle, we are already able to do this with ordinary Cartesian trees, only now the index has become in place of the key. And the rest of the procedure has not changed.

• Cut the array T [0; N) at index Pos on arrays L [0; Pos) and R [Pos; N) .
• Make an array-tree of the inserted element from one vertex.
• We assign the created array to the right to the left result L, and to both of them the right result R.
• Received array T '[0; N + 1) , in which the required element stands in the Pos position, and the remaining right side is shifted.

The source code for the insert has not changed at all.

 public ImplicitTreap Add(int pos, double elemCost) { ImplicitTreap l, r; Split(pos, out l, out r); ImplicitTreap m = new ImplicitTreap(rand.Next(), elemCost); return Merge(Merge(l, m), r); } 

Deletion

Focus №2 - we will cut out from the array the element standing at this position Pos .

Again, the procedure is the same as with ordinary Cartesian trees.

• Cut the array T [0; N) at index Pos on arrays L [0; Pos) and R [Pos; N) .
• The right-hand result R is cut by index 1 (one!). Get the array M [Pos; Pos + 1) from one element (previously standing at Pos position), and the array R '[Pos + 1; N) .
• Merge arrays L and R '.

Source code removal:

 public ImplicitTreap Remove(int pos) { ImplicitTreap l, m, r; Split(pos, out l, out r); r.Split(1, out m, out r); return Merge(l, r); } 

Multiple segment queries

Focus number 3: for O (log ₂ N), you can also perform all the same multiple queries on sublotting an array (sum / maximum / minimum / presence or number of labels, etc.).

The structure of the tree does not change from the last part: at the top we store the parameter corresponding to the desired value calculated for the whole subsegment. At the end of the Merge and Split, the same Recalc() call is Recalc() , recalculating the value of the value at the vertex based on the calculated parameters in its descendants.

Request for segment [A; B) uses the standard method: cut the required segment from the array (not forgetting that after the first cut, the desired index in the right result decreased!) And return the value of the parameter stored in its root.
Source code - as an example, for the maximum.

 public double MaxTreeCost; public static double CostOf(ImplicitTreap treap) { return treap == null ? double.NegativeInfinity : treap.MaxTreeCost; } public void Recalc() { Size = SizeOf(Left) + SizeOf(Right) + 1; MaxTreeCost = Math.Max(Cost, Math.Max(CostOf(Left), CostOf(Right))); } public double MaxCostOn(int A, int B) { ImplicitTreap l, m, r; this.Split(A, out l, out r); r.Split(B - A, out m, out r); return CostOf(m); } 

Multiple operations on the segment

Focus №4: now, in O (log ₂ N), we will perform the operations from the second part on array plots, adding a constant, painting, setting to a single value, etc.

Having workers Merge and Split, implementation of the postponed calculations in the Cartesian tree does not change at all. The basic principle of operation is the same: before performing any “push promise” operation to descendants. If you additionally need to support multiple requests from the previous section, after the operation is completed, it is necessary to “restore justice”.

To perform an operation on a segment, you first need to cut this segment from the tree with two calls of Split, and then insert it again with two calls of Merge.
For the lazy, I cite the full source code for the addition, along with the new Merge / Split implementations (they differ by as many as 1-2 lines), and also with the push function Push :

 public double Add; public static void Push(ImplicitTreap treap) { if (treap == null) return; treap.Cost += treap.Add; if (treap.Left != null) treap.Left.Add += treap.Add; if (treap.Right != null) treap.Right.Add += treap.Add; treap.Add = 0; } public void Recalc() { Size = SizeOf(Left) + SizeOf(Right) + 1; } public static ImplicitTreap Merge(ImplicitTreap L, ImplicitTreap R) { // ! Push( L ); Push( R ); if (L == null) return R; if (R == null) return L; ImplicitTreap answer; if (Ly > Ry) { var newR = Merge(L.Right, R); answer = new ImplicitTreap(Ly, L.Cost, L.Left, newR); } else { var newL = Merge(L, R.Left); answer = new ImplicitTreap(Ry, R.Cost, newL, R.Right); } answer.Recalc(); return answer; } public void Split(int x, out ImplicitTreap L, out ImplicitTreap R) { Push(this); // ! ImplicitTreap newTree = null; int curIndex = SizeOf(Left) + 1; if (curIndex <= x) { if (Right == null) R = null; else Right.Split(x - curIndex, out newTree, out R); L = new ImplicitTreap(y, Cost, Left, newTree); L.Recalc(); } else { if (Left == null) L = null; else Left.Split(x, out L, out newTree); R = new ImplicitTreap(y, Cost, newTree, Right); R.Recalc(); } } public ImplicitTreap IncCostOn(int A, int B, double Delta) { ImplicitTreap l, m, r; this.Split(A, out l, out r); r.Split(B - A, out m, out r); m.Add += Delta; return Merge(Merge(l, m), r); } 

A small digression about allowed operations:

In fact, the recursive tree structure and deferred calculations allow to implement any operation of a monoid. A monoid is a set with a binary operation ◦ defined on it, which has the following properties:
• Associativity - for any elements a, b, c we have (a ◦ b) ◦ c = a (b c) .
• The existence of a neutral element - in the set there is an element e such that for any element a there is a a e = e ◦ a = a .
Then for such an operation it is possible to realize a segment tree , and for similar reasons - a Cartesian tree.

Array flip

The focus number 5 is a subsection reversal, that is, rearrangement of its elements in the reverse order.

And on this place I will stop a little more in detail. The array reversal is not a monoidal operation — frankly speaking, it is not a binary operation on any set at all — but nonetheless. The uniqueness of this task is that you can think of a push function for it. And since there is an opportunity to push through the operation, it means that you can implement it as deferred.

So, we will store in each vertex a boolean value - an inverted bit. This will be a deferred promise that "this segment of the array needs to be expanded in the future." Then, assuming that we are able to push this bit to the descendants with a peculiar version of the Push function, the tree always remains in its current form - before any access to the array elements (search), as well as at the beginning of the Merge and Split, the pushing is performed. It remains to figure out how to make this "fulfillment of the promise."

Suppose that at some vertex T there is a promise to turn the subsegment around. To begin to actually perform it, it is enough to do the following:
• Remove the promise at the current top:

  T.Reversed = false; 

• Swap his left and right sons.

  temp = T.Left;
   T.Left = T.Right;
   T.Right = temp; 

• Change promise among descendants. Please note: do not set to true (we do not know whether this bit was still in the descendants!), But to change. To do this, use the operation ^.

  T.Left.Reversed ^ = true;
   T.Right.Reversed ^ = true; 

Indeed, what is “actually flip the array”? Take two pieces of this array (subtrees), swap them in reality, and promise to turn these two subarrays in the future. It is easy to see that when all promises are fulfilled to a single, the elements of the original array will turn upside down.

Notice - such a machination cannot be done with ordinary Cartesian trees, since we violate the property of the search tree - the keys in the right subtree turn out to be less than the keys in the left one. But since there are no keys in the implicit Cartesian tree at all, and for indices the property is always observed, nothing breaks in the tree.

The user function of turning the segment works on the same principle as any other operation: cut the required segment, set the promise in its root, and paste the segment back. Here is the source code for the push and turn functions:

 public bool Reversed; public static void Push(ImplicitTreap treap) { if (treap == null) return; //    -   if (!treap.Reversed) return; var temp = treap.Left; treap.Left = treap.Right; treap.Right = temp; treap.Reversed = false; if (treap.Left != null) treap.Left.Reversed ^= true; if (treap.Right != null) treap.Right.Reversed ^= true; } public ImplicitTreap Reverse(int A, int B) { ImplicitTreap l, m, r; this.Split(A, out l, out r); r.Split(B - A, out m, out r); m.Reversed ^= true; return Merge(Merge(l, m), r); } 

Now you can solve the classic assignment at interviews in a fundamentally new way :)

Cyclic Array Shift

Focus №6: cyclic shift. The essence of this operation, for those who do not know, is easier to explain in the figure.

Of course, a cyclic shift can always be performed in O (N), but by implementing an array as an implicit Cartesian tree, you can shift it in O (log ₂ N). The shift procedure to the left by K is trivial: we cut the tree by the index K, and glue it in the reverse order. The shift to the right is symmetrical, only you need to cut by the index NK .

 public ImplicitTreap ShiftLeft(int K) { ImplicitTreap l, r; this.Split(K, out l, out r); return Merge(r, l); } 

Again: the operation is unique to Cartesian trees by an implicit key, since it is unacceptable to glue the two results of Split, whether they are ordinary Cartesian trees: after all, Merge expects ordered trees from us, and we feed him the arguments in the wrong order.

Summary

The Cartesian tree with an implicit key is a simple representation of an array in the form of a tree, which allows a lot of operations to be performed with it and with its subarrays in logarithmic time. In this case, the memory is still spent O (N). Of course, using the O-notation, I’ve a bit of a crush here, because in real life, the actual memory occupied by the tree is important, and the Cartesian tree is famous for its overhead. Judge for yourself: N for information, N for priorities, 2N for references to descendants, N for subtree sizes is the cost of living, and if you add multiple queries, you will get N for each operation. You can improve your life a little by creating priorities from information , but this is, firstly, a drop in the ocean (only minus N), and secondly, it is fraught with consequences from a security point of view: if someone finds out the function that you use priorities, he will be potentially able to give you new entries to create in a malicious order, to greatly unbalance the Cartesian tree. In the end, it is possible that all your data will slow down noticeably - although such cases, of course, are few and require remarkable work. You can get rid of the danger by using different primes P for different vertices of the tree ... but this is a topic for separate scientific research. For me personally, the possibility of a Cartesian tree and the simplicity of its code are advantages that exceed the problem of high memory consumption. Although, of course, the program is different.

Of interesting facts: in Western literature, articles and the Internet, I did not manage to find a single mention of the Cartesian tree using an implicit key. Of course, no one knows how it should be called in English terminology - however, questions on the forums and StackOverflow also led to nothing. In the Russian practice of sports programming ACM ICPC, this structure was used for the first time in 2000, invented by Kitten Computing team member Nikolay Durov - a numerous winner of international competitions (however, Runet knows his brother Pavel more , as well as their joint creation ).

I finish this compulsory Cartesian program. Most likely, there will be at least one or two parts later - about alternative implementations of tree operations, and about its functional implementation - however, the three already written in principle make up enough ammunition for the full use of deramids in life. Thanks to all who honestly wade through the lines of this tutorial with me :) I hope you were interested.