Query a Versioned Array

Versioned Array Design

Design a data structure VersionedArray that supports an array of a fixed length N (initialized to all zeros) and allows for versioning of its state. The structure must implement the following methods:

1. set(index, value, version): Sets the value at index for a specific version. Versions are non-decreasing integers.
2. get(index, version): Returns the value at index at the specified version. If no explicit set was performed for that index at or before the version, it should return the value from the most recent previous version.

Requirements

• Initialize the array with length N where all values are initially 0 at version 0.
• set(index, value, version): Update the array such that subsequent get calls for version and higher reflect this change until the next update for that index.
• get(index, version): Fetch the value at the given index as it existed at the provided version.

Example

v = VersionedArray(5)
v.set(1, 10, 1)
v.set(1, 20, 2)
print(v.get(1, 1)) # Output: 10
print(v.get(1, 2)) # Output: 20
print(v.get(1, 0)) # Output: 0

Constraints

• index is within [0, N-1].
• version is a non-negative integer.
• Aim for sub-linear time complexity for get operations relative to the total number of updates.

Edge Cases

• Accessing an index that was never set.
• Accessing a version lower than any update version.
• Performing multiple set operations for the same index at the same version (last update wins).