Fully Persistent Arrays allow access and modification of all historical versions of an array, not just the latest. The naive copy-on-write approach wastes memory proportional to the number of versions. A more efficient implementation uses Backer's Trick: a single in-memory cache array combined with an n-ary tree of modifications where each node stores the changed index, value, and a pointer to its parent version. This makes `create` O(n), `update` O(1), and `get` O(n) in the worst case. To optimize read-heavy workloads, a rerooting technique can be applied — rotating the modification tree so any version becomes the root, reducing successive reads on the same version to O(1).
Table of contents
Fully Persistent ArraysImplementing Fully Persistent ArrayFully Persistent Arrays using Backer’s TrickOptimizing successive reads on the same versionReferences15 Impressions