Java Binary Search Solution without TreeMap
Java Binary Search Solution without TreeMap\n\nTime Complexity: \n  SnapshotArray(int length): O(n)\n  set(int index, int val): O(1)\n  snap(): O(1)\n  get(int 
Java Binary Search Solution without TreeMap\n\nTime Complexity: \n*  SnapshotArray(int length): O(n)\n*  set(int index, int val): O(1)\n*  snap(): O(1)\n*  get(int index, int snap_id): O(log(Set))\n```\nclass SnapshotArray {\n    List<int[]>[] record;\n    int sid;\n\n    public SnapshotArray(int length) {\n        record = new List[length];\n        sid = 0;\n        for (int i = 0; i < length; i++) {\n            record[i] = new ArrayList<>();\n            record[i].add(new int[]{0, 0});\n        }\n    }\n    \n    public void set(int index, int val) {\n        if (record[index].get(record[index].size() - 1)[0] == sid) {\n            record[index].get(record[index].size() - 1)[1] = val;\n        } else \n            record[index].add(new int[]{sid, val});\n    }\n    \n    public int snap() {\n        return sid++;\n    }\n    \n    public int get(int index, int snap_id) {\n        int idx = Collections.binarySearch(record[index], new int[]{snap_id, 0}, \n                                           (a, b) -> Integer.compare(a[0], b[0]));\n        if (idx < 0) idx = - idx - 2;\n        return record[index].get(idx)[1];\n    }\n}\n```
['Binary Tree', 'Java']