By svaderia, history, 5 weeks ago,

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.

• +8

 » 5 weeks ago, # |   +3 If we do not use path compression, we can maintain add[v] — the sum of all d added to the subtree of v. As the DSU are multiple trees, the weight of a vertex is the sum of add[p] for each parent p. Assume during merge we need to make parent[a] = b. We should make weights in a's subtree relevant by add[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 of v, but also the sum of add[u] for all u on path to the parent. If we know the sum, we can simply connect v directly to its parent and add the sum to add[v]. Obviously, all weights in v's subtree remain correct.
•  » » 5 weeks ago, # ^ |   0 Thanks. This is neat.
 » 5 weeks ago, # | ← Rev. 2 →   +3 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.
•  » » 5 weeks ago, # ^ |   0 Thanks, I didn't think of small-to-large merging.