Segment tree merge notes

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$:

1. 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$.

1. 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:

 1 2 3 4 5 6 7 8 

 TreeNode * mergeTrees ( TreeNode * root1 , TreeNode * root2 ) { if ( ! root1 && ! root2 ) return NULL ; // 事实上这一个判断略显多余，仅保留后面两行也可以if ( ! root1 ) return root2 ; if ( ! root2 ) return root1 ; root1 -> left = mergeTrees ( root1 -> left , root2 -> left ); root1 -> right = mergeTrees ( root1 -> right , root2 -> right ); return root1 ; }

Array implementation:

 1 2 3 4 5 6 

 int mergeTrees ( int root1 , int root2 ) { if ( ! root1 || ! root2 ) return root1 ^ root2 ; // 非常简便的写法lc [ root1 ] = mergeTrees ( lc [ root1 ], lc [ root2 ]); rc [ root1 ] = mergeTrees ( rc [ root1 ], rc [ root2 ]); return root1 ; }

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.

 1 2 3 4 5 6 7 8 9 10 11 12 

 void up ( int root ) { maxx [ root ] = max ( maxx [ lc [ root ]], maxx [ rc [ root ]]); sum [ root ] = sum [ lc [ root ]] + sum [ rc [ root ]]; } int mergeSegTrees ( int root1 , int root2 ) { if ( ! root1 || ! root2 ) return root1 ^ root2 ; lc [ root1 ] = mergeSegTrees ( lc [ root1 ], lc [ root2 ]); rc [ root1 ] = mergeSegTrees ( rc [ root1 ], rc [ root2 ]); // 维护信息up ( root1 ); return root1 ; }

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 xy represents building a new bridge between island $x$ and island $y$.

• Q xk means 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.

RECORD

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 

 #include <bits/stdc++.h> using namespace std ; const int MAXN = 300005 ; int n , m ; int p [ MAXN ], ans [ MAXN ]; int root [ MAXN << 5 ], lc [ MAXN << 5 ], rc [ MAXN << 5 ], tree [ MAXN << 5 ], cnt = 0 ; int fa [ MAXN ]; int find ( int x ) { if ( fa [ x ] == x ) return x ; return fa [ x ] = find ( fa [ x ]); } int bcmerge ( int a , int b ) { a = find ( a ), b = find ( b ); fa [ a ] = b ; } void up ( int u ) { tree [ u ] = tree [ lc [ u ]] + tree [ rc [ u ]]; } void ins ( int & rt , int l , int r , int p ) { if ( ! rt ) rt = ++ cnt ; if ( l == r ) { tree [ rt ] = 1 ; return ; } int m = ( l + r ) >> 1 ; if ( p <= m ) ins ( lc [ rt ], l , m , p ); else ins ( rc [ rt ], m + 1 , r , p ); up ( rt ); } int merge ( int u , int v , int l , int r ) { if ( ! u || ! v ) return u ^ v ; if ( l == r ) { tree [ u ] += tree [ v ]; return u ; } int m = ( l + r ) >> 1 ; lc [ u ] = merge ( lc [ u ], lc [ v ], l , m ); rc [ u ] = merge ( rc [ u ], rc [ v ], m + 1 , r ); up ( u ); return u ; } int kth ( int u , int l , int r , int k ) { if ( l == r ) return l ; int m = ( l + r ) >> 1 ; if ( k > tree [ lc [ u ]]) return kth ( rc [ u ], m + 1 , r , k - tree [ lc [ u ]]); return kth ( lc [ u ], l , m , k ); } int main () { cin >> n >> m ; for ( int i = 1 ; i <= n ; i ++ ) { cin >> p [ i ]; ans [ p [ i ]] = i ; fa [ i ] = i ; ins ( root [ i ], 1 , n , p [ i ]); } while ( m -- ) { int u , v ; cin >> u >> v ; root [ find ( v )] = merge ( root [ find ( u )], root [ find ( v )], 1 , n ); bcmerge ( u , v ); } int q ; cin >> q ; while ( q -- ) { char op ; int x , y ; cin >> op >> x >> y ; if ( op == 'Q' ) { if ( tree [ root [ find ( x )]] < y ) cout << - 1 << endl ; else cout << ans [ kth ( root [ find ( x )], 1 , n , y )] << endl ; } else { root [ find ( y )] = merge ( root [ find ( x )], root [ find ( y )], 1 , n ); bcmerge ( x , y ); } } return 0 ; }

exercise

• Segment Tree Merging: From Beginner to Master

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.