Algorithm to save state of array as it changes

Question

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

Answer 1

In the following we assume that whenever we make a delete-operation, the value to delete is guaranteed to exist in the array, and if multiple copies of it exist, we should remove its leftmost appearance.

The problem can be solved in $\mathcal{O}(\log n)$ per update, and in linear time (with respect to the output size) per query with standard persistent trees (tree traversal is linear time). The only issue is that since our ordered set is ordered by index, not value, we need a map (that doesn't have to be persistent) that translates from index to value. To not degrade the complexity, add a two-way link between nodes representing the same value in the current persistent tree and the map. These links are easy to maintain with no overhead.

If the input values are bounded, since the only query we are interested in is outputting the entire list at a specific time, we can improve on this. If the values are at most $m$, and we can use $\mathcal{O}(n + m)$ memory, we can make $n$ operations in $\mathcal{O}(n)$ time, and answer queries in linear time (with respect to the output size). To do this, we store snapshots of the array and the incremental changes between them.

Let $k$ be the highest amount of elements that have been on the current list since we last took a snapshot. We will take a new snapshot when we have deleted at least $\lceil\frac{k+1}{2}\rceil$ elements. This way we only need to apply a linear number of operations (in output size) to produce any array: if the output size is $n$, we apply at most $n+1$ deletions (since $\frac{n + (n+1) + 1}{2} = n+1$), and thus at most $2n+1$ insertions.

How to then produce the array? Start from the latest snapshot before it, then apply all of the insert-operations. Then, for each delete-operation, increment the delete-count of its respective value (stored in an array of size $\mathcal{O}(m)$. Replacing this with a map would give a $\mathcal{O}(\log n)$ overhead to both operations and queries). Then loop through the array produced after all insertions, at each point checking if the delete count of the value there is nonzero. If it is, we delete that value and decrement the count. Otherwise we proceed as normal. This takes linear time in the size of the snapshot and the number of operations we apply, which is linear in the size of the output.

It remains to show that this method of storing snapshots only uses $\mathcal{O}(n)$ memory. We show this by induction: After $n$ operations, the total size of snapshots up to that point is at most $n$. This holds initially, since we have no operations and one snapshot of size $0$. Say the previous snapshot was at time $n_0$ and was of size $s_0$, and now after $a$ insertions and $b$ deletions, we are taking another snapshot. The size of this new snapshot is then $s_0 + (a - b)$, and by induction the total size of snapshots at most $n_0 + (s_0 + (a - b))$. Thus it suffices to prove that $n_0 + a + b \geq n_0 + s_0 + (a-b)$, but this is equivalent to $2b \geq s_0$, which trivially holds, since $2b \geq 2\lceil \frac{s_0 + 1}{2} \rceil \geq s_0 + 1$.

Answer 2

The key observation is the fact that only a single value will be changed in every operation.

For each element maintain an array of the form [(snap_id, value)].

Every time you need to snapshot the array, find out which elements have changed since their last snap_shot and update only those elements.

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.