[Java/Python 3] 3 codes w/ analysis, store difference by HashMap and TreeMap, respectively.
Method 1: HashMap\nStore to a HashMap the set() results since previous snapshot.\n\nAnalysis:\nTime: Each call of get() cost O(snap_id),  othersO(1);\nSpace: To
**Method 1: HashMap**\nStore to a HashMap the `set()` results since previous snapshot.\n\n**Analysis:**\nTime: Each call of `get()` cost `O(snap_id)`,  others` O(1)`;\nSpace: Total cost `O(n + length)`, where `n` is number of calls of `set()`.\n\n```    \n    private List<Map<Integer, Integer>> shot;\n    private Map<Integer, Integer> diff;\n    \n    public SnapshotArray(int length) {\n        shot  = new ArrayList<>(length);\n        diff  = new HashMap<>(length);\n    }\n    \n    public void set(int index, int val) {\n        diff.put(index, val);\n    }\n    \n    public int snap() {\n        shot.add(diff);\n        diff = new HashMap<>();\n        return shot.size() - 1;\n    }\n    \n    public int get(int index, int snap_id) {\n        for (int i = snap_id; i >= 0; --i)\n             if (shot.get(i).containsKey(index))   \n                 return shot.get(i).get(index); \n        return 0;\n    }\n```\n----\n**Method 2: TreeMap**\nStore the `set()` result together with current snapshot `count` to the TreeMap of the specified index.\n\n**Analysis:**\nTime: Instantiation cost `O(length)`, each call of `get()/set()` cost `O(log(count))`, `snap() O(1)`;\nSpace: Total cost `O(length + count)`.\n```\n    private int count;\n    private List<TreeMap<Integer, Integer>> shot = new ArrayList<>();\n    \n    public SnapshotArray(int length) {\n        IntStream.range(0, length).forEach(i -> { shot.add(new TreeMap<>()); });\n    }\n    \n    public void set(int index, int val) {\n        shot.get(index).put(count, val);\n    }\n    \n    public int snap() {\n        return count++;\n    }\n    \n    public int get(int index, int snap_id) {\n        Integer key = shot.get(index).floorKey(snap_id);\n        return key == null ? 0 : shot.get(index).get(key);\n    }\n```\n\n----\n\n**Method 3: Binary Search**\n\n```python\nclass SnapshotArray:\n\n    def __init__(self, length: int):\n        self.snap_id = 0\n        self.shot = [[[-1, 0]] for _ in range(length)]\n\n    def set(self, index: int, val: int) -> None:\n        a = self.shot[index]\n        if a[-1][0] == self.snap_id:\n            a[-1][1] = val\n        else:\n            a.append([self.snap_id, val])\n\n    def snap(self) -> int:\n        self.snap_id += 1\n        return self.snap_id - 1\n\n    def get(self, index: int, snap_id: int) -> int:\n        a = self.shot[index]\n        id = bisect.bisect(a, [snap_id + 1, ]) - 1\n        return a[id][1]\n```
['Java', 'Python3']