A trick for DSU (disjoint set union) that I recently came across:↵
↵
We have elements on which we need to perform two types of queries:↵
↵
1. Union — merge the sets containing elements v1 and v2.↵
2. Add — for all i in the set containing element v, add some value x to a[i].↵
↵
To support this efficiently, we can store implicit modifications in the nodes, similar to lazy propagation in a segment tree, but without explicitly pushing updates down.↵
↵
For an add query, we find the root of the tree containing vertex v and add the modification to that root.↵
When we need to get the actual value of a[i], we first compress the path to the root and apply the root’s modification. During path compression (in the recursive process of reattaching the nodes), we also apply the parent’s modification to the current node.↵
↵
For the union operation, we can either:↵
↵
1. create a new virtual node to act as the parent of both components.↵
2. attach one root under the other and apply the inverse modification to the subtree that now becomes a child.↵
↵
The second approach is a bit trickier to implement when the modifications are more complex.↵
↵
code:↵
↵
<spoiler summary="Spoiler">↵
~~~~~↵
void apply(int v, long long add) {↵
res[v] += add;↵
lazyAdd[v] += add;↵
}↵
↵
int getPar(int v) {↵
if (v == comp[v]) return v;↵
int p = getPar(comp[v]);↵
if (comp[v] != p) apply(v, lazyAdd[comp[v]]);↵
return comp[v] = p;↵
}↵
↵
long long getVal(int v) {↵
int p = getPar(v);↵
if (v == p) return res[v];↵
return res[v] + lazyAdd[p];↵
}↵
↵
void add(int v, long long x) {↵
v = getPar(v);↵
apply(v, x);↵
}↵
↵
void unionSet(int v1, int v2) {↵
v1 = getPar(v1);↵
v2 = getPar(v2);↵
if (v1 == v2) return;↵
↵
int p = ++allNodes;↵
comp[v1] = p;↵
comp[v2] = p;↵
↵
res[p] = 0;↵
lazyAdd[p] = 0;↵
sz[p] = sz[v1] + sz[v2] + 1;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
↵
We have elements on which we need to perform two types of queries:↵
↵
1. Union — merge the sets containing elements v1 and v2.↵
2. Add — for all i in the set containing element v, add some value x to a[i].↵
↵
To support this efficiently, we can store implicit modifications in the nodes, similar to lazy propagation in a segment tree, but without explicitly pushing updates down.↵
↵
For an add query, we find the root of the tree containing vertex v and add the modification to that root.↵
When we need to get the actual value of a[i], we first compress the path to the root and apply the root’s modification. During path compression (in the recursive process of reattaching the nodes), we also apply the parent’s modification to the current node.↵
↵
For the union operation, we can either:↵
↵
1. create a new virtual node to act as the parent of both components.↵
2. attach one root under the other and apply the inverse modification to the subtree that now becomes a child.↵
↵
The second approach is a bit trickier to implement when the modifications are more complex.↵
↵
code:↵
↵
<spoiler summary="Spoiler">↵
~~~~~↵
void apply(int v, long long add) {↵
res[v] += add;↵
lazyAdd[v] += add;↵
}↵
↵
int getPar(int v) {↵
if (v == comp[v]) return v;↵
int p = getPar(comp[v]);↵
if (comp[v] != p) apply(v, lazyAdd[comp[v]]);↵
return comp[v] = p;↵
}↵
↵
long long getVal(int v) {↵
int p = getPar(v);↵
if (v == p) return res[v];↵
return res[v] + lazyAdd[p];↵
}↵
↵
void add(int v, long long x) {↵
v = getPar(v);↵
apply(v, x);↵
}↵
↵
void unionSet(int v1, int v2) {↵
v1 = getPar(v1);↵
v2 = getPar(v2);↵
if (v1 == v2) return;↵
↵
int p = ++allNodes;↵
comp[v1] = p;↵
comp[v2] = p;↵
↵
res[p] = 0;↵
lazyAdd[p] = 0;↵
sz[p] = sz[v1] + sz[v2] + 1;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
