Persistent Structures, Part 1: Persistent Stack
I noticed that there were a lot of posts on Habré about such classic data structures as stack, queue, hip; a segment tree and many different search trees were also considered, but very little attention was paid to persistent data structures. In this series of articles, I would like to talk about them. It so happened that I have been engaged in Olympiad programming for a long time, so I will consider them from the point of view of my experience with the use of persistent structures in this area.
By persistent data structures, we will call such structures that, with any change, there remains access to all previous versions of this structure. Obviously, one of the options (not the best, of course) can be considered a complete copy of the entire structure with each change. This is extremely inefficient both in memory and in operation time, but this method can be applied for example at the testing stage of a more complex organization of structure. Nevertheless, there is little sense from such an implementation, so further we, among other things, will search for more optimal implementations for various structures.
Today we look at the implementation and use of the persistent stack. In subsequent articles, I will talk about the persistent queue, the Cartesian tree and the segment tree, and we will also examine a couple of problems that we will solve using these persistent structures.
Formulation of the problem. Initially, there is one empty stack with the number 0, n (the number of stacks) initially equal to one. You are required to implement the following operations:
Simply put, after each operation, you need to create a "new" stack without spoiling the old one.
')
Decision. The simplest and most obvious solution to this problem is the simulation of the described process, i.e. honest stack copying at every operation. Obviously, this is not the most effective solution. The complexity of one operation is O (n) and the amount of required memory is O (n * n).
In order to get closer to the idea of an optimal solution, you can try to present the stack as a graph, where the vertex is its element, then from each vertex (except for the tail) let us insert an edge into the previous stack element. An example for a stack in which '1', '2', '3', '4', '5' are added sequentially:
It is clear that in order to restore the entire stack it is enough for us to know the “head” of the stack. Let's try instead of n copies of the stack to store the n first elements. Then the push and pop operations will have the following form:
Consider for clarity, the algorithm for example. Suppose we initially have one empty stack. For convenience, we will store it as a “head” with an empty stack:
Next, execute push (1, 5). A new vertex is created with a value of 5, referring to the 1st:
Similarly, we execute push (2, 10) and push (1, 6):
Obviously, all 4 stacks are now correctly built and easily restored. Let's now try to perform successively pop (2) and pop (3) operations:
pop (2) returns 5 and copies the 1st vertex. The resulting fifth stack is empty.
pop (3) returns 10 and copies the 2nd vertex: we get the sixth stack.
Obviously, one request works for O (1) and O (n) memory is required in total, which is good news.
Application. As far as I remember, I encountered several tasks that can be solved using a persistent stack. It is clear that, due to some primitiveness, these structures cannot be too complicated, but they exist nonetheless. For example:
N children take turns making snowmen. The first child blinded a snowman from one ball with radius R1. Each next child blinded the same snowman as the previous one, but after thinking a little bit he either added a ball with a radius Ri or destroyed the top, already existing ball. It is guaranteed that all snowmen have a strictly positive number of balls. Input data - N, information about each of the children about whether he destroyed the last ball, or added his own (then his radius is also given). Next, a set of K numbers ranging from 1 to N is given, for each of them you need to output a sequence of balls in a snowman with that number. Limit on N and K - million.
After reading the section with the implementation of the persistent stack, the solution to this problem becomes obvious.
Conclusion Today we looked at a data structure such as a persistent stack and its effective implementation. This was useful from the point of view of further understanding of other persistent structures and the principles of their implementation. As already noted, in the next articles I plan to consider more complex structures, such as a persistent queue, a Cartesian tree, and a segment tree. Structures are more complex - more complicated and more interesting are their implementation and solving problems with the help of them. Thanks for attention.
By persistent data structures, we will call such structures that, with any change, there remains access to all previous versions of this structure. Obviously, one of the options (not the best, of course) can be considered a complete copy of the entire structure with each change. This is extremely inefficient both in memory and in operation time, but this method can be applied for example at the testing stage of a more complex organization of structure. Nevertheless, there is little sense from such an implementation, so further we, among other things, will search for more optimal implementations for various structures.
Today we look at the implementation and use of the persistent stack. In subsequent articles, I will talk about the persistent queue, the Cartesian tree and the segment tree, and we will also examine a couple of problems that we will solve using these persistent structures.
Persistent stack
Formulation of the problem. Initially, there is one empty stack with the number 0, n (the number of stacks) initially equal to one. You are required to implement the following operations:
- push (i, x) - Add item x to stack i. The resulting stack will be n + 1.
- pop (i) - Return the last element of the stack number i and "throw it out of the stack." The resulting stack will be n + 1.
Simply put, after each operation, you need to create a "new" stack without spoiling the old one.
')
Decision. The simplest and most obvious solution to this problem is the simulation of the described process, i.e. honest stack copying at every operation. Obviously, this is not the most effective solution. The complexity of one operation is O (n) and the amount of required memory is O (n * n).
In order to get closer to the idea of an optimal solution, you can try to present the stack as a graph, where the vertex is its element, then from each vertex (except for the tail) let us insert an edge into the previous stack element. An example for a stack in which '1', '2', '3', '4', '5' are added sequentially:
It is clear that in order to restore the entire stack it is enough for us to know the “head” of the stack. Let's try instead of n copies of the stack to store the n first elements. Then the push and pop operations will have the following form:
- push (x, i) - creates a new element with the value x, which refers to the element with the number i as the previous element in the stack.
- pop (i) - returns the value stored in the element with the number i and copies the element previous to it.
Consider for clarity, the algorithm for example. Suppose we initially have one empty stack. For convenience, we will store it as a “head” with an empty stack:
Next, execute push (1, 5). A new vertex is created with a value of 5, referring to the 1st:
Similarly, we execute push (2, 10) and push (1, 6):
Obviously, all 4 stacks are now correctly built and easily restored. Let's now try to perform successively pop (2) and pop (3) operations:
pop (2) returns 5 and copies the 1st vertex. The resulting fifth stack is empty.
pop (3) returns 10 and copies the 2nd vertex: we get the sixth stack.
Obviously, one request works for O (1) and O (n) memory is required in total, which is good news.
Application. As far as I remember, I encountered several tasks that can be solved using a persistent stack. It is clear that, due to some primitiveness, these structures cannot be too complicated, but they exist nonetheless. For example:
N children take turns making snowmen. The first child blinded a snowman from one ball with radius R1. Each next child blinded the same snowman as the previous one, but after thinking a little bit he either added a ball with a radius Ri or destroyed the top, already existing ball. It is guaranteed that all snowmen have a strictly positive number of balls. Input data - N, information about each of the children about whether he destroyed the last ball, or added his own (then his radius is also given). Next, a set of K numbers ranging from 1 to N is given, for each of them you need to output a sequence of balls in a snowman with that number. Limit on N and K - million.
After reading the section with the implementation of the persistent stack, the solution to this problem becomes obvious.
Conclusion Today we looked at a data structure such as a persistent stack and its effective implementation. This was useful from the point of view of further understanding of other persistent structures and the principles of their implementation. As already noted, in the next articles I plan to consider more complex structures, such as a persistent queue, a Cartesian tree, and a segment tree. Structures are more complex - more complicated and more interesting are their implementation and solving problems with the help of them. Thanks for attention.
Source: https://habr.com/ru/post/113585/
All Articles