1146. Snapshot Array

https://leetcode.com/problems/snapshot-array/

模拟对数组做snapshot/快照，要求能根据snap_id返回值，数组元素初始化为0。snapshot看上去是对整个数据做备份，但实际实现是只记录本次snapshot和上次的diff。类似的这里也只要针对每个元素记录每次snap后值的改变。snap_id为当前改变对应的snap，初始为0，对每个元素维护一个tree map并把默认的snap_id和值0输入进去，当snap()时代表当前snap结束，snap_id++。get(snap_id)时在tree map中找等于或最后一个小于snap_id的，用prev(upper_bound(snap_id))。

/*
 * @lc app=leetcode id=1146 lang=cpp
 *
 * [1146] Snapshot Array
 */

// @lc code=start
class SnapshotArray {
public:
    int snap_id = 0;
    vector<map<int, int>> snaps;
    SnapshotArray(int length) {
        snaps.resize(length);
        for (int i = 0; i < length; ++i) {
            snaps[i][0] = 0;
        }
    }
    
    void set(int index, int val) {
        snaps[index][snap_id] = val;
    }
    
    int snap() {
        return snap_id++;
    }
    
    int get(int index, int snap_id) {
        return prev(snaps[index].upper_bound(snap_id))->second;
    }
};

/**
 * Your SnapshotArray object will be instantiated and called as such:
 * SnapshotArray* obj = new SnapshotArray(length);
 * obj->set(index,val);
 * int param_2 = obj->snap();
 * int param_3 = obj->get(index,snap_id);
 */
// @lc code=end