Description
Implement a SnapshotArray that supports set(index, val), snap(), and get(index, snap_id). snap() takes a snapshot and returns the snap_id.
Examples
set(0, 5), snap(), set(0, 6), get(0, 0)5Snapshot 0 had value 5 at index 0.
set(1, 10), set(3, 20), snap(), set(1, 15), snap(), get(1, 0), get(3, 1), get(1, 1)10, 20, 15Initially set index 1 to 10 and index 3 to 20, then take snapshot 0. Change index 1 to 15 and take snapshot 1. Getting index 1 at snapshot 0 returns 10 (original value), index 3 at snapshot 1 returns 20 (unchanged since snapshot 0), and index 1 at snapshot 1 returns 15 (updated value).
snap(), get(2, 0), set(2, 100), get(2, 0), snap(), get(2, 1)0, 0, 100Take snapshot 0 immediately without setting any values. Getting index 2 at snapshot 0 returns 0 (default value). Set index 2 to 100, but getting index 2 at snapshot 0 still returns 0 since the change happened after the snapshot. Take snapshot 1, then getting index 2 at snapshot 1 returns 100 (the updated value).
Constraints
- •
1 ≤ length ≤ 5 × 10⁴ - •
0 ≤ index < length - •
0 ≤ val ≤ 10⁹