[Python] Maintaining history, Binary search, O(log(n)) get, O(1) snap, O(1) set
Idea\nMaintain the history of every index.\n# Brute force solution\nCopy the entire array for every snapshot. This has O(1) get and set, but O(n) for every snap
# Idea\nMaintain the history of every index.\n# Brute force solution\nCopy the entire array for every snapshot. This has O(1) get and set, but O(n) for every snapshot.\n# Faster snapshot solution (this solution)\nMaintain the _history_ for every index, by storing for every set the current snapshot id, and appending it to the history. To take a snapshot, just update the snapshot id, and to find the value of an index element for a certain snapshot id, perform a binary search, since the history is sorted by snapshot id. This gives O(1) set and snap, and O(log(n)) get.\n\n# Code\n```\nclass SnapshotArray:\n    def __init__(self, length: int):\n        self.snap_id = -1\n        self.history = [[(self.snap_id, 0)] for _ in range(length)] # list of histories (snap_id, value)\n        self.snap_id = 0\n       \n\n    def set(self, index: int, val: int) -> None:\n        self.history[index].append((self.snap_id, val))\n        \n\n    def snap(self) -> int:\n        self.snap_id += 1\n        return self.snap_id - 1\n\n   \n    def get(self, index: int, snap_id: int) -> int:\n        history = self.history[index]\n        lower, upper = 0, len(history) - 1\n        while lower != upper:\n            mid = (upper + lower) // 2 + 1\n            if history[mid][0] <= snap_id:\n                lower = mid\n            else: # history[mid][0] > snap_id implying history[mid-1][0] is >= snap_id - 1\n                upper = mid - 1\n            \n        return history[lower][1]\n```
['Binary Tree', 'Python']