A Well-known Data Structure -- Version Tree
Difference between en4 and en5, changed 572 character(s)
## Back Ground↵

I managed to solve [CF707D](https://codeforces.ml/contest/707/problem/D) 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, query for the answer and move to the children of the version.↵

After visiting all of its children, we should revoke the modifications if necessary.↵

The code goes like this:↵

```cpp↵
void DFS(int u) {↵
  add modifications of version u↵
  query the ans at version u if there are queries.↵
  visit the children of version u↵
  revoke the modificationis of version u↵
```}↵
```cpp


## Examples↵

1. [CF707D](https://codeforces.ml/contest/707/problem/D)No.1 [problem:707D]

Solution: we build a tree mentioned above and use a bitset to maintain the latest version and update the answers.↵

2.No.2 GYM100431 G↵

Solution: build a tree mentioned above and use vector to maintain the latest version and update the answers.↵

There is a trick that we do not need to actually pop the first element, we only need to maintain the position of the first element and move it.↵

Some times the graph may not form a tree, we may use something like $dp$ to solve that, but I could not find tasks about itNo.3 Found by [user:jonathanesmuyguapo,2020-12-23]↵

[CSES.fi 1737](https://cses.fi/problemset/task/1737/)↵

Solution: In this problem the modifications are not assigned a new version. So we try to record every history version. Use $lat[x]$ to record the index of the latest version of array $x$.↵

If we have queries, just add it to the latest version of array $x$ at that moment.↵

If we have modifications, just create a new version and add the modifications on the new version. Then update $lat[x]$.↵

Therefore we could solve this by **DFS** a tree
.

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)