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 setx.cancel
tox.parent.added
to avoid fetching unnecessary addition from the new parent. This is required even when manipulating heavy edges, so therotate
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
- https://judge.yosupo.jp/problem/dynamic_tree_subtree_add_subtree_sum
You can see English statement by pressing the LANG button at the top right corner
You can also use the top tree or the euler tour tree to solve this problem
My submission
More problems are welcome !