Retroactive data structure

These modifications can take the form of retroactive insertion, deletion or updating an operation that was performed at some time in the past.

Notice how the single operation produces a cascading effect which affects the entire data structure.

In retroactive data structures we allow changes to be made directly to previous versions.

In general the data structure involves a series of updates and queries made over some period of time.

A simple approach is to perform a roll-back on all the changes made to the structure prior to the retroactive operation that is to be applied.

Once we have rolled back the data structure to the appropriate state we can then apply the retroactive operation to make the change we wanted.

While this can work for any data structure, it is often inefficient and wasteful especially once the number of changes we need to roll-back is large.

Thus there is no general way to convert any data structure into an efficient retroactive counterpart.