Persistent Array

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. ```text Array [1, 2, 3, 4] as tree: root /
* * / \ /
1 2 3 4

Time: $O(\log n)$ per operation. Space: $O(\log n)$ per update.