brdy's blog

Euler Tour Magic
By brdy, history, 5 years ago, In English

I recently read this article which summarizes cool cp tricks.

Trick 12 is something uses Euler Tour to solve algorithmic problems on trees. The thing is, I don't know what the difference is between euler tour 1 and 2? If in one euler tour for each node we store when it enters and exits, that gives us continuous segments = subtrees. But what about a path? Apparently another euler tour solves this, but I don't know how it should be represents/how to do it. Could someone please elaborate, preferrably with a diagram?

UPD: Many thanks to saharshluthra for leading me to idea.

I will now try to explain idea in my own words (with hope that it will help others in the future). The idea I was already familiar was this: we create events when we enter a node but not when we exit. We can then query subtrees and update a node in O(logn) with some tree to maintain prefix sums.

The way to query paths is not much different, instead of creating an event for when you enter, you must also create an event for when you exit the node (2 copies). This is because you want to ignore nodes not in the path: nodes with event that end before current one begins in the euler tour. Why are these not in path? Because an exit/ending event indicates backtracking, and if it backtracked from some node A before going into the current node B, node A can't possibly be on path from root to B.

Tree picture

If we visit the nodes in the order [1,2,3,4,5,6] the euler tour we build is [1,2,3,3,4,4,2,5,5,6,6,1]. Notice each number appears twice, one to represent entering and one for exiting (backtracking). Updating a node can be done by adding v in the start position and subtracting v from the end position of a node. Updating subtrees can be done with some range update ideas/keeping track of frequency of starts/ends in some interval. Querying can be done by finding the sum of numbers up to the first position the number shows up.

  • Vote: I like it
  • +29
  • Vote: I do not like it

Comments Comments (11)
| Write comment?
»
5 years ago, # |
  Vote: I like it +15 Vote: I do not like it

I'm too lazy to draw a diagram, so I'll try my best without that :P

Consider 2 copies for a single node in the Euler tour, one for entry and one for exit. When you want to add a value v to the subtree, maintain a fenwick tree, and do +=v on in[node] and -=v on out[node]. Path sum query can be broken down to sum from root to any node. For the root to node sum query, just return prefix sum of in[node] from BIT.

Now why does this work? Think about a single subtree update and then querying for prefix sum. Let's assume you updated subtree of node x with value v. Now, if you query for some node which is not in the subtree of x, the answer will be 0, either in[node]<in[x] then it's obviously 0, or in[node]>out[x] then in[x] and out[x] cancel out, so it's still 0. For the nodes inside the subtree of x, in[x]<in[node]<out[x]. So, they'll all return the value v. So effectively we've updated the subtree of x with value v.

→ Reply
»
5 years ago, # |
  Vote: I like it -13 Vote: I do not like it

Logic not magic

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    Logic is just the magic we don't understand yet

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    I named it "euler tour magic" for consistency (if you look in the other blog it is the same as adamant named it)

    Of course, I am also a bruno mars fan and huge fan of his album "24K magic", and "twen-ty-four" rhymes with "eu-ler-tour" so I thought damn this euler tour trick slick as magic

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by brdy (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Picture in your post is not showing.

Update: now the picture is showing

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Please upgrade your codeforces to view it correctly.

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

Just to add to this blog, there are two types of Euler Tour+Segment Tree tricks that I've found to be useful, one of them being the one included here. Note: The one you've shown it can also be used to update values at each node in time and query the sum from a node all the way to the root in time. Simply create two segment trees over the Euler Tour, one where the values of each node are stored in the positions of their first appearance, and one where the values of each node are stored in the positions of their second appearance. For example, on your tree, the two segment trees would look something like:

[1,2,3,0,4,0,0,5,0,6,0,0]

[0,0,0,3,0,4,2,0,5,0,6,1]

Then, if you wanted to get the sums of the numbers from node 3 to the root, you would simply take two range sum queries:

[1,2,3, 0,4,0,0,5,0,6,0, 0]

[0,0,0, 3,0,4,2,0,5,0,6, 1]

and subtract the first query from the second query, giving us 3+2+1!

Another type of Euler Tour that's useful is one where you add in the node every time its stack frame reappears in the DFS. For the given tree, the Tour would look like:

[1,2,3,2,4,2,1,5,1,6,1]

Then, one nice thing about this tour is that you can compute LCA using it, by creating a segment tree with the nodes in this order, and stores pairs of {depth, node}. So, the segment tree would be created over the array

[{0, 1}, {1, 2}, {2, 3}, {1, 2}, {2, 4}, {1, 2}, {0, 1}, {1, 5}, {0, 1}, {1, 6}, {0, 1}]

If you create a Range Min Query over this, and want to find, say, the LCA of nodes 3 and 4, then you just take a Range Min Query of the indices that they appear at:

[{0, 1}, {1, 2}, {2, 3}, {1, 2}, {2, 4}, {1, 2}, {0, 1}, {1, 5}, {0, 1}, {1, 6}, {0, 1}]

And the lowest {depth, node} pair we find is {1, 2}, meaning that node 2 is the LCA.

→ Reply