Algorithm to save state of array as it changes

There's an array which changes with every iteration, i.e., an element is added or deleted in every iteration. I have to save the "state" of the array for every iteration, which would later be retrieved upon querying.

For ex -

Initially, the array is [7, 8, 9]. This is version 1.
Next, 90 was added. Version 2 is [7, 8, 9, 90].
Next, 23 was added. Version 3 is [7, 8, 9, 90, 23].
Next, 90 was deleted. Version 4 is [7, 8, 9, 23].


And so on.

I need to write a function, get_version(ver_num), which returns the state of the array for each version. So, running get_version(3) should return [7, 8, 9, 23].

I have thought of saving incremental changes to the array in each iteration, in the form of an array maybe.

For ex -

[("add", [7, 8, 9]), ("add", [90]), ("add", [23]), ("subtract",[90])]


This will save space but in order to recreate the array for a specific version, I have to iterate over this array until I reach the required version. Is there a way better than this?

Thanks

• Although I don't know the details offhand, you are looking for persistent data-structures. I would start with the Wikipedia entry on persistent arrays: en.wikipedia.org/wiki/Persistent_array. – user340082710 Aug 8 at 14:50

For each element maintain an array of the form [(snap_id, value)].
If you are asked to retrieve the value of any element at any given snap_id then you can simply binary_Search over the array of (snap_id, value) and return the value corresponding to the snap_id that is the closest but lesser(lower_bound in CPP) than the requested id.