A Well-known Data Structure -- Version Tree

Revision en1, by Kai29, 2020-12-22 17:26:08

Back Ground

I managed to solve CF707D and at that time I didn't know this trick. After thinking for a while, I had a really good idea about solving it. After I read the tutorial I saw that this solution is mentioned in Solution No.1. But I really learned I good way of solving data structure problems including the following operations.

$$$1.$$$ Modify based on version x and the result is assigned version x

$$$2.$$$ return ... in a state they were after applying $$$k$$$-th operation.

For these questions, we could build a tree and solve the queries by DFS if off-line solutions are allowed.

Construction

The construction is quite easy. If version $$$v$$$ is modified based on version $$$x$$$, we add an edge from version $$$x$$$ to version $$$v$$$.

Because every version only has exact one father so obviously, the graph formed a tree.

Query

The answer of a query is affected by the modifications on the path from the root to this version, so what we need is to calculate it, and the way is to maintain a structure mentioned in the task without modifications based on other versions. In other words, we only need to maintain the latest version of the structure.

When we are staying at one version, we added the modifications the version contains and move to the children of the version. After visiting all of its children, we would revoke the modifications if necessary.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English Kai29 2020-12-23 15:33:10 572
en4 English Kai29 2020-12-23 04:20:12 7 (published)
en3 English Kai29 2020-12-23 04:11:17 124
en2 English Kai29 2020-12-23 04:03:24 744
en1 English Kai29 2020-12-22 17:26:08 1479 Initial revision (saved to drafts)