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.
Please anyone let me know your approaches.
Thanks in advance.
Do you need to do these updates online or offline?
Online
use the tree decomposition approach
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$$$.
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.
That problem is the same as this one.
Thanks a lot!
Read more here.
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})$$$.
Will this work for online updates? Also can you please elaborate the case when (i%B!=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.
Answering whether node u is ancestor of v can be done in O(1) if you precompute tin and tout times during euler tour.
Nice solution sir :) thnks a lot.
Thanks for the explanation mate :), got it clear now
2nd operation is easily doable with HLD in O(log^2).
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.