The link to the post about this algorithm which I have a question for is here: https://cp-algorithms.com/data_structures/disjoint_set_union.html
My question is specifically about this section
We have a segment of length $L$ , each element initially has the color 0. We have to repaint the subarray $[l, r]$ with the color $c$ for each query $(l, r, c)$ . At the end we want to find the final color of each cell. We assume that we know all the queries in advance, i.e. the task is offline.
The solution is
void make_set(int v) {
parent[v] = v;
}
int find_set(int v) {
if (v == parent[v])
return v;
return parent[v] = find_set(parent[v]);
}
for (int i = 0; i <= L; i++) {
make_set(i);
}
for (int i = m-1; i >= 0; i--) {
int l = query[i].l;
int r = query[i].r;
int c = query[i].c;
for (int v = find_set(l); v <= r; v = find_set(v)) {
answer[v] = c;
parent[v] = v + 1;
}
}
My confusion lies in parent[v] = v + 1
. How I thought about this question is that we should instead do parent[v] = parent[v] + 1
. Since we can assume that everything between v and parent[v] are already painted.
From my testing, it seems that this change doesn't change the answer but I'm not sure if I might be missing some edge cases.
Would it be correct for me to write parent[v] = parent[v] + 1
and are there any implications for the time complexity if I were to make this change?