Implement a SnapshotArray that supports the following interface:


	SnapshotArray(int length) initializes an array-like data structure with the given length. Initially, each element equals 0.
	void set(index, val) sets the element at the given index to be equal to val.
	int snap() takes a snapshot of the array and returns the snap_id: the total number of times we called snap() minus 1.
	int get(index, snap_id) returns the value at the given index, at the time we took the snapshot with the given snap_id


&nbsp;
Example 1:

Input: ["SnapshotArray","set","snap","set","get"]
[[3],[0,5],[],[0,6],[0,0]]
Output: [null,null,0,null,5]
Explanation: 
SnapshotArray snapshotArr = new SnapshotArray(3); // set the length to be 3
snapshotArr.set(0,5);  // Set array[0] = 5
snapshotArr.snap();  // Take a snapshot, return snap_id = 0
snapshotArr.set(0,6);
snapshotArr.get(0,0);  // Get the value of array[0] with snap_id = 0, return 5

&nbsp;
Constraints:


	1 &lt;= length &lt;= 5 * 104
	0 &lt;= index &lt; length
	0 &lt;= val &lt;= 109
	0 &lt;= snap_id &lt; (the total number of times we call snap())
	At most 5 * 104 calls will be made to set, snap, and get.


class SnapshotArray:

    def __init__(self, length: int):
        self.snap_id = 0
        self.history = defaultdict(dict)

    def set(self, index: int, val: int) -> None:
        self.history[self.snap_id][index] = val

    def snap(self) -> int:
        self.snap_id += 1
        return self.snap_id-1

    def get(self, index: int, snap_id: int) -> int:
        for i in range(snap_id,-1,-1):
            if index in self.history[i]:
                return self.history[i][index]
        return 0 # default value in case it wasn't set earlier
class SnapshotArray {

    TreeMap<Integer,Integer>[] snapshotArray;
    int currSnapId;

    public SnapshotArray(int length) {
        snapshotArray = new TreeMap[length];
        for(int i=0;i<length;i++)
        {
            snapshotArray[i] = new TreeMap();
        }
        currSnapId =0;
    }

    public void set(int index, int val) {
        snapshotArray[index].put(currSnapId,val);
    }

    public int snap() {
        return currSnapId++;
    }

    public int get(int index, int snap_id) {
        Integer lowerKey = snapshotArray[index].floorKey(snap_id);

        if(lowerKey !=null)
        {
            return snapshotArray[index].get(lowerKey);
        }
        return 0;
    }
}

/**
 * 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);
 */
class SnapshotArray {
    int timestamp;
    unordered_map<int, vector<int>> toSnaps, toValues;
public:
    SnapshotArray(int length) {
        timestamp = 0;
    }

    void set(int index, int val) {
        if (toSnaps.count(index) == 0) {
            // After lower_bound, prevent returning negative lo
            toSnaps[index].push_back(-1);
            // 0 means not found
            toValues[index].push_back(0);
        }
        // same timestamp -> just update value
        if (toSnaps[index].back() == timestamp) {
            toValues[index].back() = val;
        }
        // not -> add timestamp and value
        else {
            toSnaps[index].push_back(timestamp);
            toValues[index].push_back(val);
        }
    }

    int snap() {
        return timestamp++;
    }

    int get(int index, int snap_id) {
        // check whether index exists or not
        if (toSnaps.count(index) == 0) return 0;
        auto& snaps = toSnaps[index];
        int lo = 0, hi = snaps.size()-1;
        while (lo < hi) {
            int m = lo + (hi - lo)/2;
            if (snaps[m] >= snap_id) hi = m;
            else lo = m + 1;
        }
        // lower bound can be larger than target
        if (snaps[lo] > snap_id) lo--;
        // if lo is negative, then ther is no value of index at lo time
        //if (lo < 0) return 0;
        return toValues[index][lo];
    }
};

/**
 * 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);
 */
var SnapshotArray = function(length) {
    this.snaps = []
    this.currentIndex = 0
    this.currentSnaps = []
}

SnapshotArray.prototype.set = function(index, val) {
    this.currentSnaps[index] = val
}

SnapshotArray.prototype.snap = function() {
    this.snaps[this.currentIndex] = [...this.currentSnaps]
    
    return this.currentIndex++
}

SnapshotArray.prototype.get = function(index, snap_id) {
    const res = this.snaps[snap_id]
    
    if (res[index] === undefined) return 0
    
    return res[index]
}
Snapshot Array