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.
If we do not use path compression, we can maintain
add[v]
— the sum of alld
added to the subtree ofv
. As the DSU are multiple trees, the weight of a vertex is the sum ofadd[p]
for each parentp
. Assume duringmerge
we need to makeparent[a] = b
. We should make weights ina
's subtree relevant byadd[a] -= add[b]
.If we want to use path compression, implementation becomes a bit more complicated. During
find(int v)
operation, we need to return not only the parent ofv
, but also the sum ofadd[u]
for allu
on path to the parent. If we know the sum, we can simply connectv
directly to its parent and add the sum toadd[v]
. Obviously, all weights inv
's subtree remain correct.Thanks. This is neat.
Your idea works, but with some minor modifications. For each component, store the vertices in that component as well (the time complexity is still $$$\mathcal{O}(n \log n)$$$ if you use small to large). Then, when merging component $$$X$$$ into component $$$Y$$$, we can first add the lazy value of component $$$X$$$ to all vertices in $$$X$$$, and subtract the lazy value of component $$$Y$$$ from all vertices in $$$X$$$, because when you are asked the value of a vertex $$$v$$$, you will output $$$\text{value}_v + \text{lazy}$$$ (where $$$\text{lazy}$$$ denotes the value of the lazy variable for the component of vertex $$$v$$$), but the lazy increment of the component $$$Y$$$ before you merged $$$X$$$ into it should not have any effect on the current vertex $$$X$$$, so in order to fix this mistake before we commit it, we will subtract $$$\text{lazy}_Y$$$ from the values of all the vertices of $$$X$$$ even before adding them to $$$Y$$$. Similarly, we should add $$$\text{lazy}_X$$$ to the values of all the vertices of $$$X$$$, because you should be adding that, but you don't (because the only thing you add right now is $$$\mathrm{lazy}_Y$$$), so in order to fix that mistake before we commit it, we will add $$$\text{lazy}_X$$$ to the values of all the vertices of $$$X$$$. The time complexity is $$$\mathcal{O}(n \log n)$$$ because of small to large.
Thanks, I didn't think of small-to-large merging.