QCFium's blog

By QCFium, 22 months ago, In English

The link-cut tree is a data structure that can maintain dynamic forest (that is, we can add/remove edges as long as the graph remains a forest) and handle various types of queries efficiently. It can handle not only path aggregation/update queries but also subtree aggregation queries. Let's go further and try subtree lazy propagation !

Note that there is a limitation of the lazy propagation operator to be used in this link-cut tree trick : invertibility. For example, subtree add query meets this condition, but subtree bitwise-or update doesn't.

Alternative ways

The top tree can perform subtree update queries quite naturally, without requiring invertibility, but it's a bit hard to implement and has a relatively big constant in running time. The euler tour tree can perform subtree update/aggregation queries efficiently but can't handle path queries.

Terms

auxiliary tree : the splay tree used to represent the original tree, not the original tree itself

Content

As stated above, we can handle any update operators that are invertible, but we will focus on subtree add + subtree sum here. Every node has a variable called added, which denotes the amount of subtree addition on the node.
We can't naively propagate added because the number of children (in original tree) can be huge, so we "pull down" the update information to a single child instead of "pushing down" it to all the children. Roughly, we want to propagate added when we access (some people call it expose), which brings a specific node to the root of the auxiliary tree. When we are doing access and we are at node x, whose parent (in the auxiliary tree) is p, we can apply p.added to x, without touching other children of p.
Now, we have a problem; since we do not propagate added to all the children at once, we can't clear added and we sometimes fetch the same addition from the same parent multiple times. To avoid this, we introduce a new variable cancel on every node. When we apply x.parent.added to x, we set x.cancel to x.parent.added. The next time we apply x.parent.added, we only apply the diff : x.parent.added - x.cancel. This is why we need invertibility.
In this way, we can avoid double addition and achieve the same time complexity as the original link-cut tree since we can propagate in $$$O(1)$$$.
Finally, sum can be properly updated using size information and the 'maintaining subtree information' technique.

Notes

  • We never clear added.
  • Whenever we change the parent of a node x in the auxiliary tree, we have to set x.cancel to x.parent.added to avoid fetching unnecessary addition from the new parent. This is required even when manipulating heavy edges, so the rotate function will be a bit messy.
  • Of course, we can perform path sum/add and similar types of queries at the same time.(haven't implemented yet)

Implementation

Here is some code that is not needed to process subtree sum queries but is needed to process subtree add queries. You can see the whole code here.

	void add(int64_t add_val) {
		val += add_val;
		sum += add_val * size;
		added += add_val;
		light_sum += add_val * light_size;
	}
	void flush() {
		if (p != NONE) {
			add(p->added - cancel);
			cancel = p->added;
		}
		if (rev) {
			std::swap(l, r);
			l->rev ^= 1;
			r->rev ^= 1;
			rev = false;
		}
	}
	void rotate(int dir) {
		Node *new_root = ch[!dir];
		assert(new_root != NONE);
		if (new_root->ch[dir] != NONE) new_root->ch[dir]->flush(); // <---
		ch[!dir] = new_root->ch[dir];
		ch[!dir]->p = this;
		ch[!dir]->cancel = added; // <---
		new_root->ch[dir] = this;
		if (p->l == this) p->l = new_root;
		if (p->r == this) p->r = new_root;
		new_root->p = p;
		new_root->cancel = p->added; // <---
		p = new_root;
		cancel = new_root->added; // <---
		fetch(), new_root->fetch();
	}
	void link(Node *parent) {
		parent->expose();
		expose();
		p = parent;
		cancel = parent->added; // <- Here, we adjust 'cancel' to avoid fetching unnecessary addition
		p->r = this;
		p->fetch();
	}

Problems

More problems are welcome !

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

»
6 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

Thanks, this is pretty neat. It's also pretty interesting how your fetch method both pulls information from parent and pushes it down to children.

You can also do this with the usual down-propagation: just store two "push" variables in each node — one for propagating down the splay tree and another for propagating to your "light" children. cancel then only makes sense for splay tree roots so maintaining it in rotate is much simpler: just copy parent's value to the child. On the flip side you need to handle the actual "light" children propagation during expose but you're already doing some extra work there because of subtree sum queries.