Editing Persistent data structure (section)

== Partially persistent data structure ==
A type of data structure where user may query any version of the structure but may only update the latest version.

An ephemeral data structure can be converted to partially persistent data structure using a few techniques.

One of the technique is by using randomized version of Van Emde Boas Tree which is created using dynamic perfect hashing. This data structure is created as follows:

* A stratified tree with m elements is implemented using dynamic perfect hashing.
* The tree is pruned by dividing the m elements into buckets of size log(log n) such that the elements of bucket 1 is smaller than the elements of bucket 2 and so on.
* The maximal element in each bucket is stored in the stratified tree and each bucket is stored in the structure as an unordered linked list.

The size of this data structure is bounded by the number of elements stored in the structure that is O(m). The insertion of a new maximal element is done in constant O(1) expected and amortized time. Finally query to find an element can be done in this structure in O(log(log n)) worst-case time.<ref>{{Cite journal |last=Lenhof |first=Hans-Peter |last2=Smid |first2=Michiel |date=1994 |title=Using persistent data structures for adding range restrictions to searching problems |url=http://dx.doi.org/10.1051/ita/1994280100251 |journal=RAIRO - Theoretical Informatics and Applications |volume=28 |issue=1 |pages=25–49 |doi=10.1051/ita/1994280100251 |issn=0988-3754|hdl=11858/00-001M-0000-0014-AD4F-B |hdl-access=free }}</ref>