This paper is obsoleted by my PhD thesis, which corrects some mistakes in this paper and fills additional details.
Abstract:
We describe an implementation of fully persistent arrays with worst-case
O(log log m) time complexity of update and lookup, and O(n+m) space
complexity, where n is the size of the array and m is the number of
modifications to the array.
This lookup complexity is shown to be asymptotically optimal even for partially
persistent arrays in the cell probe model using recent results of
Patrascu and Thorup. Hence there cannot exist any persistent array,
persistent hashtable nor any persistent graph with constant-time
operations.
We also improve the complexity of update and lookup to O(log log min(n, m))
and show how to augment the algorithm to cooperate with the garbage
collector to free unreachable data.