Snapshot Array

Design a data structure that supports taking snapshots of an array and querying past values.

Implement a function that processes an array of operations and an array of arguments:

• "SnapshotArray" — Initializes the array of the given length. All elements start at 0.
• "set" — Sets arr[index] = val.
• "snap" — Takes a snapshot of the array and returns the snap_id (starts at 0, increments with each call).
• "get" — Returns the value at arr[index] as of the snapshot with snap_id.

Examples

Example 1:

Input: operations = ["SnapshotArray","set","snap","set","get"], args = [[3],[0,5],[],[0,6],[0,0]]

Output: [null,null,0,null,5]

Explanation: Initialize array of length 3. Set index 0 to 5. Take snapshot (returns 0). Set index 0 to 6. Get index 0 at snap_id 0 returns 5 (the value before the update).

Example 2:

Input: operations = ["SnapshotArray","snap","snap","set","snap","get","get"], args = [[2],[],[],[1,7],[],[1,0],[1,2]]

Output: [null,0,1,null,2,0,7]

Explanation: Snap twice (ids 0 and 1). Set index 1 to 7. Snap (id 2). get(1, snap_id=0)=0 (initial). get(1, snap_id=2)=7.

Constraints

• 1 <= length <= 5 * 10^4
• 0 <= index < length
• 0 <= val <= 10^9
• 0 <= snap_id < (number of times snap() was called)
• At most 5 * 10^4 calls to set, snap, and get