What is a persistent data structure?
Suppose there is a problem where a queue is used. The program is requesting the standard queue operations such as enqueue and pop/deque. Let’s say that there is a new version every time a new item is added. When the problem asks to pop something, it also specifies which version it wants to pop off of. What is the optimal way to complete this?
Persistent data structures are the key. PDS uses a technique that allows them to save a lot of memory. It avoids having to completely duplicate the data structure every time a new version is made.
What is the technique?
The idea of a persistent data structure rides off of the fact that there is some data that doesn’t change. A persistent segment tree is a great way to visualize this.
The Persistent Segment Tree
When doing a simple point operation on a segment tree it affects a total of log(n) nodes. Every time an operation is used to change the create a new tree will all of the affected nodes (call this tree 2). Go through each node in the tree 2 and make sure to add a point to the original tree. Image is a good reference for how this works.