[Python] Easy solution - Store only the updates for each index + binary search O(logK)
The idea is to store only the updates for each index, and when a get action is performanced, binary search on the index changes list.\n\nTime:\nConstruct: O(n)\
The idea is to store only the updates for each index, and when a `get` action is performanced, binary search on the index changes list.\n\nTime:\nConstruct: O(n)\nSet, Snap: O(1)\nGet: O(logk) where k is number of updates for the index\nSpace: O(n) + O(#of Set by snapshot)\n\n```\nclass SnapshotArray:\n\n    def __init__(self, length: int):\n        self.array = [[(0,0)] for _ in range(length)]\n        self.curSnapshot = 0\n\n    def set(self, index: int, val: int) -> None:\n        snapId, _ = self.array[index][-1]\n\t\t# Overwrite the number if within same snapshot, else add new value with latest Id\n        if self.curSnapshot == snapId:\n            self.array[index][-1] = (snapId, val)\n        else:\n            self.array[index].append((self.curSnapshot, val))\n\n    def snap(self) -> int:\n\t\t# Increment the lastest snapshot Id\n        self.curSnapshot += 1\n        return self.curSnapshot - 1\n\n    def get(self, index: int, snap_id: int) -> int:\n\t\t# Only need to search on the index updates\n        ss = self.array[index]\n\t\t# Binary search for the latest change by snapshot id\n        i = bisect_left(ss, snap_id, key = lambda x: x[0])\n\t\t# If the asked snapshot happened after latest snapshot of this index, take latest change\n        if i == len(ss):\n            return ss[-1][1]\n\t\t# If the found index is that snapshot, return the value, or return last value\n        return ss[i][1] if ss[i][0] == snap_id else ss[i-1][1]\n\n```
['Binary Tree', 'Python']