huzaifa242's blog

How to handle updates in DSU on trees
By huzaifa242, history, 6 years ago, In English

I read this Blog on DSU on trees.

Now, I have a doubt.

Given a tree with n nodes and each node has some color c[i], following query needs to be answered

1 x y: change color of node x to y

2 u c: count all the nodes with color c in subtree of u.

How to approach this??

Thanks for help in advance.

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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by huzaifa242 (previous revision, new revision, compare).

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Do a preorder traversal/euler tour on the tree so that colors of nodes in the same subtree will be together. Now, you just need to keep a segment tree, with order statistic set in each node. I think that you can take it from here.

→ Reply
»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

actually u can solve this problem without a segment tree. Basically, u maintain n (of the n colors) binary search tree (seems difficult? Rmb pbds exits) in each of the BST, stores the order of the node in the euler tour. After that, a simple, lower_bound and upper_bound operation can solve the problem.

Memory: O(N), Time: O(N log N)

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

    Thanks for this approach.

    But I wanted to know if something can be done using that blog?? I mean ca we handle updates using the technique mentioned in the blog??

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

      I don't think so, cuz the result in each node is used by its ancestor

      Updating in this manner will be linear with a worst-case complexity of O(TN) where T is the number of updates

      → Reply