Блог пользователя Mayank_Pushpjeet

Автор Mayank_Pushpjeet, 11 месяцев назад, По-английски

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.

  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Do you need to do these updates online or offline?

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

use the tree decomposition approach

»
11 месяцев назад, # |
  Проголосовать: нравится +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$$$.

»
11 месяцев назад, # |
  Проголосовать: нравится +80 Проголосовать: не нравится

 Read more here.

»
11 месяцев назад, # |
  Проголосовать: нравится +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})$$$.

  • »
    »
    11 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      11 месяцев назад, # ^ |
      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.

»
11 месяцев назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится

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

»
11 месяцев назад, # |
  Проголосовать: нравится 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.