Fully Persistent Arrays

extended abstractA data structure is partially persistent if previous versions remain available for queries but not for updates. A data structure is fully persistent if past versions remain available both for queries and for updates in a "branching" model of time. The tree representing the branching temporal evolution of the data structure is called the version tree [4]. Each node in the version tree represents the result of one update operation on a version of the data structure. An array is a data structure A on which two operations are defined: Access(A, i), which returns the ith element of A, and Store(A, i, x), which replaces the ith element of A with x. 1 This paper outlines a technique for making arrays fully persistent in O(log log n) expected amortized time per operation and O(n) space.2 Since an array can model a RAM's memory, any data structure on a RAM in which each operation takes O(F(n)) time and performs O(U(n)) memory modifications can be made fully persistent using O(F(n) log log n) expected amortized time per operation and using O(nU(n)) space