Most Optimal Solution using Binary search
\nclass SnapshotArray {\n    vector<vector<pair<int, int>>> nums;\n    int snapId = 0;\npublic:\n    SnapshotArray(int length) {\n        nums = vector<vector<p
```\nclass SnapshotArray {\n    vector<vector<pair<int, int>>> nums;\n    int snapId = 0;\npublic:\n    SnapshotArray(int length) {\n        nums = vector<vector<pair<int, int>>>(length); //snapId, val\n        for(int i=0; i<length; i++){\n            nums[i].push_back({0, 0});\n        }\n    }\n    \n    void set(int index, int val) {\n        auto itr = nums[index].back();\n        if(itr.first == snapId){\n            nums[index].back().second = val;\n        }else{\n            nums[index].push_back({snapId, val});\n        }\n    }\n    \n    int snap() {\n        snapId++;\n        return (snapId - 1);\n    }\n    \n    int get(int index, int snap_id) {\n        auto itr = lower_bound(nums[index].begin(), nums[index].end(), make_pair(snap_id, INT_MIN));\n        if(itr == nums[index].end() || itr->first > snap_id){\n            itr--;\n        }\n        return itr->second;\n    }\n};\n\n/**\n * Your SnapshotArray object will be instantiated and called as such:\n * SnapshotArray* obj = new SnapshotArray(length);\n * obj->set(index,val);\n * int param_2 = obj->snap();\n * int param_3 = obj->get(index,snap_id);\n */\n```
['Binary Tree', 'C++']