Original link: https://blog.chungzh.cn/articles/merge-seg-tree/
Pre-knowledge: Dynamic open point line segment tree.
Binary tree merge
Merging is a recursive process. First merge two binary trees rooted at $u, v$:
- Consider the left subtree
- If neither $u nor v$ has a left subtree, leave it blank;
- If only $u$ has a left subtree, then the left subtree of $u$ remains unchanged;
- If only $v$ has a left subtree, then take over the left subtree of $v$ to become the left subtree of $u$;
- If $u, v$ have left subtrees, then recursively merge the left subtrees of $u, v$, and assign the result to the left subtree of $u$.
- Consider the right subtree
- If neither $u nor v$ has a right subtree, then leave it blank;
- If only $u$ has a right subtree, then the right subtree of $u$ remains unchanged;
- If only $v$ has a right subtree, then take over the right subtree of $v$ to become the right subtree of $u$;
- If both $u and v$ have right subtrees, then recursively merge the right subtrees of $u, v$, and assign the result to the right subtree of $u$.
Finally, we merge the two binary trees into a binary tree rooted at $u$.
Complexity analysis : In the above process, recursion is performed only when $u and v$ have left (right) children, and this left (right) child is accessed. Time complexity is the number of duplicate nodes in two binary trees.
Program implementation:
The pointer is implemented as follows:
|
|
Array implementation:
|
|
This way of writing is directly modified on the basis of the original tree, and another way of writing is to dynamically open a point to form a new line segment tree.
Maintenance information for line segment tree merging
Segment trees are also binary trees in nature, so merging segment trees is similar to merging binary trees. The difference is that each node of the line segment tree also maintains other information, such as the maximum value of the interval, the sum, and so on.
We know that the information of a node on the line segment tree needs to be obtained from its child nodes, so as long as the left subtree and right subtree of a node are merged, the information of the left and right child nodes is taken out for maintenance. That’s it. Leaf nodes are even simpler.
|
|
The modification operation of line segment tree merge
When we modify the segment tree interval, we usually use lazy tags. Once accessed down, the tag of the current node is pushed down. But when we want to support line segment tree merging, what to do with the markers of the two trees?
The key point is that the mark on a line segment tree only represents the modification of the node of this line segment tree, and has nothing to do with the other one. Therefore, before merging the two nodes, the two flags are dropped first .
Example Question “HNOI2012” Never Home
Luogu-P3224 “HNOI2012” Never Home
meaning of the title
Neverland contains $n$ islands, numbered from $1$ to $n$, each island has its own unique importance, these $n$ islands can be ranked according to their importance, and the rankings are from $1$ to $ n$ to represent. Some of the islands are connected by huge bridges through which one can go from one island to another. Island $a$ and island $b$ are said to be connected if the island $a$ can reach the island $b$ through several (including $0$) bridges.
There are now two operations:
-
B xyrepresents building a new bridge between island $x$ and island $y$. -
Q xkmeans to ask which island is the most important $k$ among all the islands currently connected to the island $x$, that is, which island is the $k$ least important island among all the islands connected to the island $x$ , please output the number of that island.
$1 \leq m \leq n \leq 10^5$, $1 \leq q \leq 3 \times 10^5$, $p_i$ is a permutation of $1 \sim n$, $op \in {\texttt Q, \texttt B}$, $1 \leq u, v, x, y \leq n$.
analyze
Just look at the query operation first, which is actually a kth largest problem, which can be solved with a weighted segment tree .
By building bridges, we can get several connected blocks, and at the same time merge operations. It is easy to think of and check the set .
In this process, each connected block should have a weight segment tree, so a weight segment tree is established for each island at the beginning, and then the importance of this island is dynamically opened. When building a bridge, the line segment tree is merged first, and then the merge check is performed.
Note that during the merging process, the direction of the line segment tree merging should be the same as that of the merged set. For example, fa[a] = b; , then root[b] points to the root of the line segment tree merging. Or just to be on the safe side, it’s okay to point both root[a] and root[b] to the new root.
|
|
exercise
This article is reprinted from: https://blog.chungzh.cn/articles/merge-seg-tree/
This site is for inclusion only, and the copyright belongs to the original author.