[Java/Python] Binary Search
Intuition\nInstead of copy the whole array,\nwe can only record the changes of set.\n\n\n## Explanation\nThe idea is, the whole array can be large,\nand we may 
## **Intuition**\nInstead of copy the whole array,\nwe can only record the changes of `set`.\n<br>\n\n## **Explanation**\nThe idea is, the whole array can be large,\nand we may take the `snap` tons of times.\n(Like you may always ctrl + S twice)\n\nInstead of record the history of the whole array,\nwe will record the history of each cell.\nAnd this is the minimum space that we need to record all information.\n\nFor each `A[i]`, we will record its history.\nWith a `snap_id` and a its value.\n\nWhen we want to `get` the value in history, just binary search the time point.\n<br>\n\n## **Complexity**\nTime `O(logS)`\nSpace `O(S)`\nwhere `S` is the number of `set` called.\n\n`SnapshotArray(int length)` is `O(N)` time\n`set(int index, int val)` is O(1) in Python and `O(logSnap)` in Java\n`snap()` is `O(1)`\n`get(int index, int snap_id)` is `O(logSnap)`\n<br>\n\n**Java**\n```java\nclass SnapshotArray {\n    TreeMap<Integer, Integer>[] A;\n    int snap_id = 0;\n    public SnapshotArray(int length) {\n        A = new TreeMap[length];\n        for (int i = 0; i < length; i++) {\n            A[i] = new TreeMap<Integer, Integer>();\n            A[i].put(0, 0);\n        }\n    }\n\n    public void set(int index, int val) {\n        A[index].put(snap_id, val);\n    }\n\n    public int snap() {\n        return snap_id++;\n    }\n\n    public int get(int index, int snap_id) {\n        return A[index].floorEntry(snap_id).getValue();\n    }\n}\n```\n**C++**\nfrom @vikas007\n```\nclass SnapshotArray {\nprivate:\n    map<int, map<int, int>> snaps;\n    int snapId = 0;\npublic:\n    SnapshotArray(int length) {\n        for (int i = 0; i < length; i++) {\n            map<int, int> mp; mp[0] = 0;\n            snaps[i] = mp;\n        }\n    }\n    \n    void set(int index, int val) {\n        snaps[index][snapId] = val;\n    }\n    \n    int snap() {\n        return snapId++;\n    }\n    \n    int get(int index, int snap_id) {\n        auto it = snaps[index].upper_bound(snap_id); it--;\n        return it->second;\n    }\n};\n```\n\n**Python:**\n```python\nclass SnapshotArray(object):\n\n    def __init__(self, n):\n        self.A = [[[-1, 0]] for _ in xrange(n)]\n        self.snap_id = 0\n\n    def set(self, index, val):\n        self.A[index].append([self.snap_id, val])\n\n    def snap(self):\n        self.snap_id += 1\n        return self.snap_id - 1\n\n    def get(self, index, snap_id):\n        i = bisect.bisect(self.A[index], [snap_id + 1]) - 1\n        return self.A[index][i][1]\n```\n
[]