On Euler tour trees

Revision en3, by ifsmirnov, 2015-06-07 01:47:42

TL;DR: is it possible to construct an Euler tour tree which supports LCA, subtree sum and rerooting?

Euler tour tree (ETT) is a method for representing a rooted undirected tree as a number sequence. There are several common ways to build this representation. Usually only the first is called the Euler tour; however, I don't know any specific names for others and will call them Euler tours too. All of them have some pros and cons. I want to discuss if we can build an algorithm which contains benefits from each one. Maybe this post also could be a tutorial for beginners. The first way is to write down all edges of the tree, directed, in order of DFS. This is how ETT is defined on, for example, Wikipedia.

     1
    / \
   2   5
  / \
 3   4

[1-2] [2-3] [3-2] [2-4] [4-2] [2-1] [1-5] [5-1]

The second way is to store vertices. Each vertex is added to the array twice: when we descend into it and when we leave it. Each leaf (except maybe root) has two consecutive entries.

     1
    / \
   2   5
  / \
 3   4

1 2 3 3 4 4 2 5 5 1

The third way implies storing vertices too, but now each vertex is added every time when we visit it (when descending from parent and when returning from child).

     1
    / \
   2   5
  / \
 3   4

1 2 3 2 4 2 1 5 1

Further all ETT's are stored in a Cartesian tree (treap) unless other explicitly stated. first(v) and last(v) are positions of first and last occurrence of vertex v in the array (in 2nd and 3rd cases).

So, how these representation can be used?

First, you should notice that a subtree is always mapped to a segment. Thus you can solve subtree queries via segment queries. E.g. if you want to add values to nodes and find subtree sum, you just make a BIT on a 2nd type tour. add(v, x) becomes add(first(v), x) in BIT, and get_sum(v) becomes get_sum(first(v), last(v)) in BIT. There is also a trick to compute sum on path: add(v, x) becomes add(first(v), x), add(last(v),  - x) in BIT, and get_sum_on_path_from_root(v) is get_sum(0, first(v)) (you can check that it works using pencil and paper).

You can also use ETT for finding LCA. Use the 3rd type. Make an additional array h, where h[i] = height(v[i]). Then lca(u, v) = v[argmin(first(u), first(v)) in h]. Why? Because LCA(u, v) is a highest vertex which is between u and v in DFS traverse order. Sometimes I prefer this method to binary accent (not sure if translated correctly) because it proved to be faster and consumes linear memory.

The fact that a subtree is maps to a segment gives us some more benefits. With the first and third approach you can reroot the tree simply rotating the array. You may avoid some pain in the neck with the third approach if you do not store last number for the root (thus vertex v will have exactly deg(v) occurrences). You also can perform link-cut operations simply cutting the segment from the array. It is done quite straightforward when you store edges, and with vertices you should carefully deal with duplicating of the subtree's former ancestor.

However, although these simple structures proved to be powerful enough, I have some open questions. Can you simultaneously reroot a tree and query LCA? Can you query both LCA and subtree sum? and so on.

Summing up, I made a table with pros and cons of every approach.

Stores LCA Subtree sum Path sum Rerooting
1 edges + (values on edges) + + (not sure if works with sum)
2 vertices + (values on vertices) +
3 vertices + (no rerooting) + (no LCA)

So, the final question (and the main purpose of this post) is: can you add some  + 's to this table and/or tell about some other related methods?

P.S. This topic is by no means related to heavy-light decomposition and link-cut trees. I know that they may solve some proposed problems, but the idea is to squeeze as much as possible from Euler tours.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru3 Russian ifsmirnov 2015-06-07 02:13:58 32
ru2 Russian ifsmirnov 2015-06-07 02:12:49 93
en4 English ifsmirnov 2015-06-07 02:12:10 103
ru1 Russian ifsmirnov 2015-06-07 02:10:41 4065 Первая редакция перевода на Русский
en3 English ifsmirnov 2015-06-07 01:47:42 2 Tiny change: ' first(v)) in h]$. Why?' -> ' first(v))\ in\ h]$. Why?'
en2 English ifsmirnov 2015-06-07 01:46:30 5048 Tiny change: 'ooting|\n|-|-|-|-|-|-|\n|1|edge' - (published)
en1 English ifsmirnov 2015-06-07 00:33:21 1045 Initial revision (saved to drafts)