How to implement "Add weight to component" operation in DSU?

Правка en1, от svaderia, 2024-06-13 06:14:55

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.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский svaderia 2024-06-13 06:14:55 978 Initial revision (published)