题目描述

实现支持下列接口的「快照数组」- SnapshotArray：

• SnapshotArray(int length) 初始化一个与指定长度相等的类似于数组的数据结构。初始时，每个元素都等于 0。
• void set(index, val) 会将指定索引 index 处的元素设置为 val。
• int snap() 获取该数组的快照，并返回快照的编号 snap_id（快照号是调用 snap() 的总次数减去 1）。
• int get(index, snap_id) 根据指定的 snap_id 选择快照，并返回该快照指定索引 index 的值。

样例

输入：["SnapshotArray","set","snap","set","get"]
     [[3],[0,5],[],[0,6],[0,0]]
输出：[null,null,0,null,5]
解释：
SnapshotArray snapshotArr = new SnapshotArray(3); // 初始化一个长度为 3 的快照数组。
snapshotArr.set(0,5);  // 令 array[0] = 5。
snapshotArr.snap();  // 获取快照，返回 snap_id = 0。
snapshotArr.set(0,6);
snapshotArr.get(0,0);  // 获取 snap_id = 0 的快照中 array[0] 的值，返回 5。

限制

• 1 <= length <= 50000
• 题目最多进行 50000 次 set，snap，和 get 的调用。
• 0 <= index < length
• 0 <= snap_id < （我们调用 snap() 的总次数）
• 0 <= val <= 10^9

算法

(数据结构，二分)

1. 我们在普通数组的基础上进行改造，每个位置都存储一个新动态数组，存储每个版本（如果有）下的更改。
2. 初始时，我们建立长度为 length 的数组，每个位置是一个长度为 1 的数组，仅保存版本号 0 和 元素 0 的一个数对。
3. 修改时，我们去 index 位置的数组中的最后一个位置，如果那个位置的版本号等于当前计数器的版本号，则直接修改元素值；否则新插入一个数对，记录当前版本号和元素值。
4. 快照时，直接更新计数器。
5. 查询时，我们得到那个位置的数组，然后开始二分，找到小于等于待查询版本的最大版本的那个数对，返回数对的元素值即可。

时间复杂度

• 初始化时间复杂度为 $O(length)$。
• 修改元素的时间复杂度为 $O(1)$。
• 快照的时间复杂度为 $O(1)$。
• 查询的时间复杂度最坏为 $O(\log S)$，其中 $S$ 为快照的次数。

空间复杂度

• 最坏需要 $O(length + Q)$ 的空间，其中 $Q$ 为操作的总次数。

C++ 代码

class SnapshotArray {
public:
    vector<vector<pair<int, int>>> arr;
    int counter;

    SnapshotArray(int length) {
        arr.resize(length);
        for (int i = 0; i < length; i++)
            arr[i].emplace_back(0, 0);

        counter = 0;
    }

    void set(int index, int val) {
        auto &x = arr[index].back();
        if (x.first == counter) x.second = val;
        else arr[index].emplace_back(counter, val);
    }

    int snap() {
        return counter++;
    }

    int get(int index, int snap_id) {
        auto &v = arr[index];
        int l = 0, r = v.size() - 1;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (snap_id >= v[mid + 1].first)
                l = mid + 1;
            else
                r = mid;
        }

        return v[l].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);
 */