Snapshottable array

Design SnapshotArray(length), an array initialized to zeros that supports:

• set(index, val), write val at index in the current (uncommitted) version.
• snap(), take a snapshot; return its id (0, then 1, ...) and advance the counter.
• get(index, snap_id), return the value at index at the time snapshot snap_id was taken.

arr = SnapshotArray(3)
arr.set(0, 5)
arr.snap()        # -> 0
arr.set(0, 6)
arr.get(0, 0)     # -> 5   (value when snapshot 0 was taken)

Make get run in $O(\log m)$ where m is the number of writes to that index.