Easy C++ explanation || Binary Search || Using Vector
Intuition\nWe don\'t need to save the whole array at the time of snapshot. It would be sufficient to store the changed value at a given snap time, and if we wan
# Intuition\nWe don\'t need to save the whole array at the time of snapshot. It would be sufficient to store the changed value at a given snap time, and if we want to reduce time complecity then we need to have a tradeoff between the given 3 queries and store the values in such a mannner that our queries can be handled in the desired time constraint.\n\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nCreating a vector<vector<pair<int,int> > > which will store the initial values and then at the time of set, we push an element to this vector containg the snap time and the changed value. \n\nWe will use a **binary search** on the set query to find the most recent snap with respect to given time/snapId.\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(nlogn)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n+m) where m is number of times set() is called\nwhich is at most 5*10^4 calls.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass SnapshotArray {\npublic:\n    vector< vector<pair<int,int> > >v;\n    int id;\n    SnapshotArray(int length) {\n        v.resize(length);\n        id=-1;\n        for(int i=0;i<length;i++)\n        {\n            v[i].push_back({id,0});\n        }\n    }\n    \n    void set(int index, int val) {\n        v[index].push_back({id,val});\n    }\n    \n    int snap() {\n        id++;\n        return id;\n    }\n    \n    int get(int index, int snap_id) {\n        int l=0,r=v[index].size()-1;\n        int ans=0;\n        while(l<=r)\n        {\n            int mid=(r-l)/2+l;\n            if(v[index][mid].first<snap_id)\n            {\n                ans=mid;\n                l=mid+1;\n            }\n            else\n            r=mid-1;\n        }\n        return v[index][ans].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 Search', 'C++']