A persistent array supports: - get(version, index): Get value at index in given version - set(version, index, value): Create new version with updated value Implementation using complete binary tree: Store array as leaves of a balanced binary tree.
Each update creates a new path from root to the modified leaf. Array [1, 2, 3, 4] as tree: root / \ * * / \ / \ 1 2 3 4 Update index 1 to value 5: copy root, left internal node, create new leaf 5.
Time: per operation. Space: per update.