Problem

A fintech platform uses feature flags to safely roll out UI and risk-model changes to millions of daily active users. During an incident, engineers must answer questions like: “What was the flag state at the exact moment snapshot s was taken?”—even after many later updates.

Design a data structure SnapshotArray that behaves like an integer array, but supports immutable snapshots.

Requirements

Implement the following API:

1. SnapshotArray(length: int)
   • Initializes an array of size length with all values set to 0.
2. set(index: int, val: int) -> None
   • Sets the value at index to val in the current (not-yet-snapped) version.
3. snap() -> int
   • Takes a snapshot of the array and returns the snap_id (starting at 0, increasing by 1).
4. get(index: int, snap_id: int) -> int
   • Returns the value at index as it was when snapshot snap_id was taken.

Notes / Clarifications

• get must return 0 if an index had never been set at or before that snapshot.
• Multiple set calls to the same index before a snap() should be last-write-wins for that snapshot.
• Your solution must be memory-efficient: avoid copying the entire array on each snapshot.

Examples

Example 1

• Input: ops = [SnapshotArray(3), set(0,5), snap(), set(0,6), get(0,0)]
• Output: snap() -> 0, get(0,0) -> 5
• Explanation: Snapshot 0 captured index 0 as 5. The later set(0,6) does not affect reads from snapshot 0.

Example 2

• Input: ops = [SnapshotArray(2), snap(), get(1,0), set(1,7), snap(), get(1,1), get(1,0)]
• Output: snap() -> 0, get(1,0) -> 0, snap() -> 1, get(1,1) -> 7, get(1,0) -> 0
• Explanation: Index 1 is 0 in snapshot 0. After setting it to 7, it becomes visible starting snapshot 1.

Constraints

• 1 <= length <= 5 * 10^4
• 0 <= index < length
• 0 <= val <= 10^9
• 0 <= snap_id < number_of_snaps
• At most 2 * 10^5 total calls across set, snap, and get