Python Solution Binary Search
Time complexity\n set: O(1)\n snap: O(1)\n* get: O(#set operations on the given index)\n\nSpace complexity O(#set operations)\n\nimport bisect\nimport collectio
Time complexity\n* set: O(1)\n* snap: O(1)\n* get: O(#set operations on the given index)\n\nSpace complexity O(#set operations)\n```\nimport bisect\nimport collections\n\n\nclass SnapshotArray:\n\n    def __init__(self, length: int):\n        self.map = collections.defaultdict(list)\n        self.cur_snap = 0\n\n    def set(self, index: int, val: int) -> None:\n        self.map[index].append(((self.cur_snap, val)))\n\n    def snap(self) -> int:\n        self.cur_snap += 1\n        return self.cur_snap - 1\n        \n    def get(self, index: int, snap_id: int) -> int:\n        snap_list = self.map.get(index, None)\n        if snap_list is None:\n            return 0\n        index = bisect.bisect_right(snap_list, (snap_id, float(\'inf\'))) - 1\n        return snap_list[index][1] if index >= 0 else 0\n```
['Binary Tree', 'Python', 'Python3']