Mayank_Pushpjeet's blog

How to range update on ancestors of a vertex in a tree
By Mayank_Pushpjeet, 15 months ago, In English

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.

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

»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Do you need to do these updates online or offline?

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

use the tree decomposition approach

→ Reply
»
15 months ago, # |
  Vote: I like it +29 Vote: I do not like it

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$$$.

→ Reply
»
15 months ago, # |
  Vote: I like it +80 Vote: I do not like it

Read more here.

→ Reply
»
15 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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})$$$.

→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Will this work for online updates? Also can you please elaborate the case when (i%B!=0)

    → Reply
    • »
      »
      »
      15 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

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

        Answering whether node u is ancestor of v can be done in O(1) if you precompute tin and tout times during euler tour.

        → Reply
      • »
        »
        »
        »
        15 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thanks for the explanation mate :), got it clear now

        → Reply
»
15 months ago, # |
  Vote: I like it -12 Vote: I do not like it

2nd operation is easily doable with HLD in O(log^2).

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply