Persistent Segment Tree Version Copy Lite

Problem

Simulate a persistent array where each point update creates a new version.

Version 0 is the initial array. operations is a list of ["set", version, index, value] or ["get", version, index]. A set copies the given version, changes one index, appends the new version, and records its version id; a get returns the value in that version.

Return the list of recorded results.

Hint

Each set creates a new version id equal to its position in the version list.

Test cases

case 1

in: [[1,2,3],[["set",0,1,9],["get",0,1],["get",1,1],["set",1,2,7],["get",2,2],["get",0,2]]]

expected: [1,2,9,2,7,3]

case 2

in: [[5],[["get",0,0],["set",0,0,1],["get",1,0]]]

expected: [5,1,1]

case 3

in: [[1,2],[["set",0,0,9],["set",0,1,8],["get",1,0],["get",2,1],["get",0,0]]]

expected: [1,2,9,8,1]

case 4

in: [[],[]]

expected: []

Starter codePython

def persistent_point_set(initial, operations):
    # Your code here
    pass

4 test cases · run your code against them in the editor