svaderia's blog

By svaderia, history, 6 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.

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

»
6 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

»
6 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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.

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

    Thanks, I didn't think of small-to-large merging.