In computer science, and more precisely regarding data structures, a persistent array is a persistent data structure with properties similar to a (non-persistent) array.
is a data structure, with a fixed number n of elements
It is expected that, given the array ar and an index
A fully persistent array may be updated an arbitrary number of times while a partially persistent array may be updated at most once.
Given that non-persistent arrays support both updates and lookups in constant time, it is natural to ask whether the same is possible with persistent arrays.
The following theorem shows that under mild assumptions about the space complexity of the array, lookups must take
, the lower bound on the lookup complexity in this partially persistent array is
The most straightforward implementation of a fully persistent array uses an arbitrary persistent map, whose keys are the numbers from 0 to n − 1.
A persistent map may be implemented using a persistent balanced tree, in which case both updates and lookups would take
This implementation is optimal for the pointer machine model.
[2] This implementation is used in the OCaml module parray.ml[3] by Jean-Christophe Filliâtre.
In order to define this implementation, a few other definitions must be given.
Finally, the tree of a family of arrays is the tree whose nodes are the arrays, and with an edge e from ar to each of its children ar.update(i,v).
This tree admits an arbitrary root - not necessarily the initial array.
The root may be moved to an arbitrary node of the tree.
Changing the root from root to an arbitrary node ar takes time proportional to the depth of ar.
Similarly, looking up a value takes time proportional to the distance between the array and the root of its family.
Thus, if the same array ar may be lookup multiple times, it is more efficient to move the root to ar before doing the lookup.
Finally updating an array only takes constant time.
Technically, given two adjacent arrays ar1 and ar2, with ar1 closer to the root than ar2, the edge from ar1 to ar2 is labelled by (i,ar2[i]), where i the only position whose value differ between ar1 and ar2.
Otherwise, let e the edge leaving ar toward the root.
The creation of ar.update(i,v) consists in adding a new node ar2 to the tree, and an edge e from ar to ar2 labelled by (i,v).
Finally, moving the root to a node ar is done as follows.
Otherwise, let e the edge leaving ar toward the current root, (i,v) its label and ar2 the other end of e. Moving the root to ar is done by first moving the root to ar2, changing the label of e to (i, ar2[i]), and changing array[i] to v. Updates take
time if the root is the array being looked up, but
In 1989, Dietz[4] gave an implementation of fully persistent arrays using
By the lower bound from the previous section, this time complexity for lookup is optimal when
This implementation is related to the order-maintenance problem and involves vEB trees, one for the entire array and one for each index.
Straka showed that the times for both operations can be (slightly) improved to
It remains open whether it is possible to achieve worst-case time