[Tutorial] Subtree lazy propagation on the link-cut tree
source link: http://codeforces.com/blog/entry/80145
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
By QCFium, 21 month(s) ago,
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)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 !
Recommend
-
102
symfony/polyfill-mbstring: This component provides a partial, native PHP implementation for the Mbstring extension. Sk...
-
147
symfony/phpunit-bridge: Provides utilities for PHPUnit, especially user deprecation notices management. Skip to content
-
143
symfony/console: The Console component eases the creation of beautiful and testable command line interfaces. Skip to content...
-
110
symfony/debug: The Debug component provides tools to ease debugging PHP code. This repository has been archived by the owner...
-
121
symfony/finder: The Finder component finds files and directories via an intuitive fluent interface. Skip to content...
-
131
Process Component The Process component executes commands in sub-processes. Sponsor The Process component for Symfony 6.1 is backed by
-
9
题目¶ 原题地址:https://leetcode.com/problems/subtree-of-another-tree...
-
6
_Enginor_'s blog
-
1
Check if a binary tree is subtree of another binary treeSkip to content
-
5
Duplicate subtree in Binary TreeOctober 13, 2023 |970 ViewsPROBLEM OF THE DAY: 12/10/2023 | Duplicate subtree in Binary TreeProblem of the Day, Data Structure and Algorithm, binary-tree
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK