### Mayank_Pushpjeet's blog

By Mayank_Pushpjeet, 9 months ago,

I have 2 kind of operations

Update the value of all vertex in a subtree of a vertex to 1.

Update the value of all vertex which are ancestors of a vertex to 0.

I m not able to think how to do the 2nd operation in log(n) using segment tree with lazy Propagation.

• +12

 » 9 months ago, # |   0 Do you need to do these updates online or offline?
•  » » 9 months ago, # ^ |   0 Online
 » 9 months ago, # |   0 use the tree decomposition approach
 » 9 months ago, # |   +29 What are the actual queries you need to perform using the values?Here's an approach that supports updates of the type you described and point queries online and in $O(\log n)$ time. Perform a preorder traversal on the tree and number the updates in increasing order. Maintain a data structure supporting range set and point queries (a lazy segment tree or a set both work; I'll call this "Segtree 1") and a data structure supporting point updates and range max query ("Segtree 2"). If update $i$ is of the first type, set the interval corresponding to the subtree of the given vertex in Segtree 1 to $i$. If update $i$ is of the second type, set the position corresponding to the given vertex in Segtree 2 to $i$.To perform point queries, query the given vertex in Segtree 1 and the subtree corresponding to the given vertex in Segtree 2. (Observe that these queries include all type-one updates on ancestors of our vertex and all type-two updates in its subtree.) If the result from Segtree 1 is larger, the most recent update is of the first type, so the answer is $1$. Otherwise, the most recent query is of the second type, so the answer is $0$.
•  » » 9 months ago, # ^ |   0 Got it, thanks a lot. I was trying to come up with operations of type2 in range update and point query too, there I got lost.
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 That problem is the same as this one.
•  » » » 9 months ago, # ^ |   0 Thanks a lot!
 » 9 months ago, # |   +80 Read more here.
 » 9 months ago, # |   +8 I think I know the problem you are trying to solve. If you are interested in other simple approaches, we can do it in $n \cdot \sqrt{n}$. It was fast enough as $1 \leq n,q \leq 2 \cdot 10^5$.Let us have two arrays, $On, Off$ where $On[i]$ gives the maximum index of query in which $i$ was updated to $1$ and $Off[i]$ gives the maximum index of query in which $i$ was updated to $0$. Initially, take $Off[i]=0, On[i]=-1$ for all $1 \leq i \leq n$.Now if $On[i] > Off[i]$, the value of node $i$ is $1$; otherwise, its value is $0$.Let $B = \sqrt{n}$. Suppose you are at $i-$th query. If $i|B$, do dfs traversal to update $On[i], Off[i]$ for all nodes in $O(n)$.Now, suppose $i$ is not divisible by $B$. Iterate over all updates which have not been processed(not covered in any dfs traversal) and update on and off times of node in the $i-$th query accordingly. We would have atmost $O(B)$ unprocessed updates. Thus, our time complexity is $O(q \cdot B + \frac{q \cdot n}{B})$.
•  » » 9 months ago, # ^ |   0 Will this work for online updates? Also can you please elaborate the case when (i%B!=0)
•  » » » 9 months ago, # ^ | ← Rev. 2 →   0 Yes. You just need to keep track of all unprocessed queries and the last update performed by us on a vertex. Also when dealing with i which are not divisible by B, you will need to answer queries like is a an ancestor of b(can be done via binary lifting) which incurs an additional logn factor.
•  » » » » 9 months ago, # ^ |   +3 Answering whether node u is ancestor of v can be done in O(1) if you precompute tin and tout times during euler tour.
•  » » » » » 9 months ago, # ^ |   0 Nice solution sir :) thnks a lot.
•  » » » » 9 months ago, # ^ |   0 Thanks for the explanation mate :), got it clear now
 » 9 months ago, # |   -12 2nd operation is easily doable with HLD in O(log^2).
 » 9 months ago, # |   0 Just use heavy-light decomposition with a segment tree with lazytag can solve it in $O(\log^2 n)$. Or, use the link-cut tree.Or, if the data is random, you can also use Old Driver Tree.