For each index i, histories[i] is a sorted list of (snap_id, value) pairs. To answer get(i, snap_id), we need the value written most recently at or before that snap_id. In other words, we need the rightmost pair whose snapshot id is <= snap_id.

This becomes a standard binary search boundary problem: if histories[i][mid][0] <= snap_id, then mid is a valid candidate, but there may be a later valid entry, so move right. Otherwise, move left. The final candidate index pos is the answer.

We initialize each history with (-1, 0), so pos is always valid and get correctly returns 0 when no set happened before that snapshot.

Implementation

class SnapshotArray(object):

def __init__(self, n):
    # set up histories so that each index has its own history
    self.histories = [[[-1, 0]] for _ in range(n)]
    self.snap_id = 0

def set(self, index, val):
    self.histories[index].append([self.snap_id, val])

def snap(self):
    self.snap_id += 1
    return self.snap_id - 1

def get(self, index, snap_id):
    left, right, pos = 0, len(self.histories[index])-1, -1
    while left <= right:
        mid = (left+right) // 2
        if self.histories[index][mid][0] <= snap_id:
            left = mid + 1
            pos = mid
        else:
            right = mid - 1
    return self.histories[index][pos][1]

Instead of copying the entire array each time we take a snapshot, we wish to only store the changes to each index. we keep track of an array histories of size n where histories[i] is an array that stores the history of the changes of array[i]'s values. We use the pair (snap_id, value) to indicate that we have updated array[i]=value at the time we took the snapshot with the given snap_id.

So when implementing get(snap_id) for index i, we will do binary search on histories[i] to find the index pos in histories[i] that contains the most recent value up to the time we took the snapshot with the given snap_id.