1
class SnapshotArray {
2

3
  TreeMap<Integer, Integer>[] snapshotArray;
4
  int currSnapId;
5

6
  public SnapshotArray(int length) {
7
    snapshotArray = new TreeMap[length];
8
    for (int i = 0; i < length; i++) {
9
      snapshotArray[i] = new TreeMap();
10
    }
11
    currSnapId = 0;
12
  }
13

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

18
  public int snap() {
19
    return currSnapId++;
20
  }
21

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

25
    if (lowerKey != null) {
26
      return snapshotArray[index].get(lowerKey);
27
    }
28
    return 0;
29
  }
30
}
31

32
/**
33
 * Your SnapshotArray object will be instantiated and called as such: SnapshotArray obj = new
34
 * SnapshotArray(length); obj.set(index,val); int param_2 = obj.snap(); int param_3 =
35
 * obj.get(index,snap_id);
36
 */