Applying Difference Array To DSU

Revision en1, by draid, 2024-08-21 17:46:18

i was tackling C. Experience the other day and had a "clever" idea (well it's perhaps the intended but whatever) to support all the queries mentioned in the problem in $$$O(\alpha(n))$$$, using both union by size/rank and path compression, i thought it was nice and didn't see it documented elsewhere so here it is, the idea is to basically notice that if we merge two teams (with union by size/rank ofc), we can set the experience of the child representative node to that of it self minus of it's parent representative experience, so basically:

now if we want the experience of B, we can traverse the tree up and sum, so $$$x-y+y = x$$$ and if we at some point added some value m to A, we'll have B equal x + A, and when path compression we'll just add experience of the recursion, let's describe what each dsu part will do:

sunion(a, b): regular union by size, but we set experience of the children representative to itself minus of it's parent

void sunion(int a, int b) {
  a = find(a);
  b = find(b);
  if(a == b) return;
  if(size[a] > size[b]) {
    parents[b] = a;
    size[a] += size[b];
    exp[b] -= exp[a];
  }
  
  else {
    parents[a] = b;
    size[b] += size[a];
    exp[a] -= exp[a];
  }
}

find(v): regular path compression, we go up the tree and move the link, but we add a twist that for each move up we sum the experience, code: (**incorrect code but the idea is there, can anyone help me figure out what's wrong? i spent two days on this :sob:**)

pair<int, int> find_backend(int v) {
  if(v == parents[v]) return {v, exp[v]};
  else {
    parents[v] = find_backend(parents[v]).first;
    exp[v] += find_backend(parents[v]).second;
    return {parents[v], exp[v]};
  }
}

int find(int v) {
  return find_backend(v).first;
}

get_exp(v): and add_exp(v, m) both trivial

int get_exp(int v) {
  return find_backend(v).second;
}

void add_exp(int v, int m) {
  exp[find(v)] += m; 
}

and yes that's it, we solved the problem in $$$O(\alpha(n))$$$! very cleanly, very nicely! i'd really appreciate some debugging help to make the code correct, sorry for my lack of implementation skills!

Tags dsu, dsu on tree, disjoint-set, idk some random tag

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English draid 2024-08-21 17:46:18 2377 Initial revision (published)