svaderia's blog

By svaderia, history, 5 months ago, In English

Original Question here.

The question is as follows: Let all elements in sets have some weights. Add the following operations to Disjoint Sets: 1) increase all weights in the given set by d, 2) find the current weight of the element x.

I thought of maintaining a lazy value on the representative node of the component for Query 1. For query 2, we can add the weight of node x + accumulated weight on the representative node. However, I am unable to think of how to maintain this when I merge two components. The already accumulated weights on one node needs to get transferred to it's current subtree and not the future one.

I thought of not using Path Compression at all, and then we will calculate the weight of node x as the sum of weights of all its parent but again I am not sure what to do when we perform the merge operation.

Full text and comments »

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

By svaderia, history, 5 years ago, In English

100513C - Component Tree is mentioned as a problem that can be solved using Segment Tree with vectors in Algorithm Gym :: Everything About Segment Trees by PrinceOfPersia.

Although this post gives a hint about how to solve the problem, I am unable to understand how to solve using the Segment tree. Can anyone give some hints?

Thanks :)

Full text and comments »

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