# 1146. Snapshot Array
###### tags: `Leetcode` `Google` `Medium` `Binary Search`
Link: https://leetcode.com/problems/snapshot-array/
## 思路
$SnapshotArray:O(N)$ $set:O(1)$ $snap:O(1)$ $get:O(logM)$
$N=length$ $M$是这个index被更改的次数

Instead of record the history of the whole array,
we will record the history of each cell.
And this is the minimum space that we need to record all information.

For each ```A[i]```, we will record its history.
With a snap_id and a its value.

When we want to get the value in history, just binary search the time point.
## Code

class SnapshotArray {
    TreeMap<Integer, Integer>[] map;
    int id = 0;

    public SnapshotArray(int length) {
        map = new TreeMap[length];
        for(int i=0; i<length; i++){
            map[i] = new TreeMap<>();
            map[i].put(0,0);
        }
    }
    
    public void set(int index, int val) {
        map[index].put(id, val);
    }
    
    public int snap() {
        return id++;
    }
    
    public int get(int index, int snap_id) {
        return map[index].floorEntry(snap_id).getValue();
    }
}