### mujtabax's blog

By mujtabax, history, 3 weeks ago, ,

I recently got to know about Tree Flattening using a DFS Traversal. Can someone suggest some nice problems on the same. Thanks!

• +8

 » 3 weeks ago, # | ← Rev. 3 →   +1 Recent,very good problem from July long challenge.Chef and Dragon Dens
•  » » 3 weeks ago, # ^ |   0 I solved that one using 3 Segment Trees :/
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   +1 It can be done with two Binary Indexed Trees.
•  » » » » 3 weeks ago, # ^ |   0 Yeah actually the third SegTree was for RMQ ...
•  » » » » » 3 weeks ago, # ^ |   +1 Uh? It is just saying the value at some position and update a range by adding a value to all elements in the range. It just a BIT/SegmentTree; since there are queries forward and backward you need two BIT/ST.
•  » » » » » » 3 weeks ago, # ^ |   0 Yeah, I used 2 Lazy Segment Trees for Queries (Foward and Backward).I used 3rd Segment tree for finding Largest Height between any range [L, R]. (Which is basically a RMQ — Range Maximum Query)
•  » » » 3 weeks ago, # ^ |   +1 After flattening?
•  » » » » 3 weeks ago, # ^ |   +1 No, I did not flatten the Tree in that question. I used a Prefix-Sum Like Approach to solve the problem.
•  » » » » » 3 weeks ago, # ^ |   0 Initially I tried to do same, but I wasn't able to handle update query in log(n) so I got only 45 pts. What was your logic?
•  » » » » » » 3 weeks ago, # ^ |   0 Lazy Updates can be done in O(logN).And also, it is important to notice that heights are fixed.The updates are on the tastiness only.
•  » » » » 3 weeks ago, # ^ |   +1 let's say $dp[u]$ is the sum of values of nodes on the path from root downto $u$. When an updates comes (sum a value of $x$ to the value of node $u$), $dp[v] \ \forall v\in subtree(u)$ are affected with a $+x$ increase, and when a query $u\rightarrow v$ comes (with $u$ ancestor of $v$), you just have to return $dp[v]-dp[parent[u]]$. So, by performing a preorder trasversal each subtree becomes a subarray of the euler tour array, so the operations become now: sum $x$ to all values in a range $[l\dots r]$ and get the value at some position $p$; this can be done with Binary Indexed Tree + Difference Array or with Segment Tree + Lazy Propagation (both in $O(\log n)$ time and $O(n)$ space).
•  » » » » » 3 weeks ago, # ^ |   0 If I'm not wrong this is what we do in tree flatenning.
•  » » » » » » 3 weeks ago, # ^ |   +1 yes, that is a way of flatenning the tree. There are other ways with different uses. For example: to query LCA in $O(1)$ with SparseTable-preprocessing, you can insert each node $u$ on the array when you visit it by first time and after you finish processing each one of $u$'s children; let's say $pos[u]$ is a position of $u$ on the euler-tour array. then the $LCA(u,v)$ is the node with lowest level in the subarray $[pos[u]\dots pos[v]]$.Another way of doing it is with BFS, so the nodes of same level form a subarray of the built array.Another way of doing it is with DFS inserting the nodes the first time we visit it and when we goes out of its subtree. This is used to apply Mo's algorithm on treesAnother way is HLD, this is very useful to apply queries and updates over paths on a tree.
•  » » » » » » » 3 weeks ago, # ^ |   +2 Thanks for this knowledge.
•  » » » » » » » 3 weeks ago, # ^ |   +1 Thanks !
 » 3 weeks ago, # | ← Rev. 2 →   +1 try this, this and this
•  » » 3 weeks ago, # ^ |   0 Thanks a lot !
 » 3 weeks ago, # |   +21 Hey bro I got a good one https://oj.uz/problem/view/APIO13_toll it uses tree flattening.
•  » » 3 weeks ago, # ^ |   0 Thanks !