lessons/课程/08-高级线段树与树状数组/03-动态开点合并与分裂.md

动态线段树：开点、合并与按秩分裂

本节目标

掌握只为出现过的值域路径建节点的动态开点线段树，并理解两个根如何合并、一个多重集如何按第 $k$ 小边界分裂；能证明这些操作为什么只访问非空结构。

前置知识与课前自测

前置：值域线段树、逆序对、std::map 区间维护。

1. 动态开点怎样把坐标 $[1,10^9]$ 的空树空间降下来？
2. 合并两棵计数树时，叶子语义是什么？
3. 一个区间已按降序排列，从左边切前 $k$ 个位置，对应值域中的哪一部分？

答案

1. 更新访问到某区间时才创建节点，单次只建 $O(\log V)$。 2. 同一值的出现次数相加；内部节点递归合并左右值域。 3. 最大的 $k$ 个值，而非最小的 $k$ 个。

问题动机与核心知识

动态树的根代表一个值域多重集。三种基础操作：

• insert(root,value)：沿值域路径开点并加计数；
• merge(a,b)：空树直接返回另一根，否则递归合并对应儿子、计数相加；
• split(root,k)：按计数把最小的前 $k$ 个元素与其余元素拆成两根，只在分界路径复制/拆开节点。

合并的复杂度不是固定 $O(\log V)$，而与两树重叠的非空节点数有关；常见“线段树合并总复杂度”证明依赖节点合并后不再分开、每个节点被消耗常数次。若之后还反复分裂，需要把分裂新建节点数单独计入。

实现指南

• 根的所有权要明确：破坏式合并后旧的两个根不能继续作为独立版本使用。
• split(k=0)、split(k=size) 应直接返回空根/原根，避免无意义开点。
• 区间有升降序语义时，位置切分与值域第 k 小的方向必须对应。
• 极深原树递归输入可改为先读前序 token，再从后向前用栈归并。

精选例题 1：Tree Rotations

来源与题意

• HYSBZ-2212 Tree Rotations，POI 2011
• 满二叉树有 $n\le2\times10^5$ 个叶，叶权为 $1..n$ 的排列；可交换任意内部点左右子树，最小化从左到右叶序列逆序对。

Hint 1

左右子树内部最优选择与两子树谁在前无关，可递归独立完成。

Hint 2

合并两棵值域计数树时，同时统计 `左值 > 右值` 与交换后的 `右值 > 左值`。

Hint 3

当前值域节点的跨半贡献分别是 `A.right*B.left` 与 `B.right*A.left`。

Observations

• 一个内部点的旋转只改变左右子树之间的相对先后，不改变各子树内部顺序。
• 跨子树逆序数只由两个叶权多重集和左右顺序决定，与内部如何旋转无关。
• 值域递归把“大于”关系唯一分配到首次落入不同左右值域的层级，因此不会重复计数。

Editorial

每个叶子建立只含一个权值的动态计数树。从前序描述末尾向前，用栈恢复子树：遇叶压根；遇内部点弹出左右两根，合并时累计正常顺序跨逆序数 $x$ 与交换顺序跨逆序数 $y$，答案加 $\min(x,y)$，再把合并根压回。

正确性证明

归纳假设两子树已取得各自最小内部逆序数。当前点只剩两种顺序，额外逆序分别为 $x,y$；选择较小者不影响子树内部最优，也不影响祖先只关心的合并多重集。因此局部最优可独立组合成全局最优。每个动态节点在合并链上被处理常数次，总复杂度 $O(n\log n)$。

核心伪代码与附件

scan prefix tree description in reverse:
    leaf(value): push singleton_value_tree(value)
    internal:
        left, right = pop(), pop()
        merged, normal, swapped = merge_and_count(left, right)
        answer += min(normal, swapped)
        push merged

完整 C++17 附件

精选例题 2：排序

来源与题意

• HYSBZ-4552 排序，TJOI/HEOI 2016
• $n,m\le10^5$，初始为 $1..n$ 的排列；每次把区间升序或降序排序，最后询问位置 $q$ 的值。

Hint 1

维护若干互不相交、各自已经单调的块。

Hint 2

块保存值域多重集根和升/降方向；在位置处分块需要按秩分裂多重集。

Hint 3

排序区间时先在两端切块，再把覆盖块的值域树全部合并成一个新块并设置方向。

Observations

• 一次“排序”不需要显式写回每个位置，只需知道区间包含哪些值以及读取方向。
• 任意时刻序列可表示成若干单调块；操作只会切开至多两个边界块，再合并中间所有块。
• 初始是排列使计数为 0/1，但算法按多重集实现，语义更稳定。

Editorial

用有序映射按块左端点存 [l,r],root,descending。split_position(pos) 找到包含位置的块；升序块取最小的前缀计数，降序块取最大的前缀计数，调用值域树按秩分裂。每次操作切出 $l,r+1$ 后，破坏式合并中间所有根，擦除旧块，插入一个带新方向的大块。最终在 $q$ 所在块按偏移查询第 k 小/大。

正确性证明

块不变量是：根的多重集等于该位置区间全部值，按方向读取根的有序值恰等于当前序列片段。边界分裂按实际读取顺序分出前后片段，保持不变量；排序操作合并的多重集与原区间相同，重新按指定方向读取正是排序结果。归纳覆盖全部操作。

初始开点与每次两次分裂共新增 $O((n+m)\log n)$ 节点；每个被擦除块只在一次合并中消失，映射操作另有对数因子。

核心伪代码与附件

blocks = singleton monotone blocks
for sort(op, l, r):
    right_it = split_position(r + 1)
    left_it = split_position(l)
    root = destructive_merge(all roots in [left_it, right_it))
    erase old blocks; insert block(l, r, root, direction=op)
locate block containing q
answer = kth(root, offset+1 if ascending else block_size-offset)

完整 C++17 附件

扩展与联系

若只询问一个最终位置，本题也可“二分答案 + 01 Lazy Segment Tree”做得更短；本节选择合并/分裂路线是为了建立通用数据结构。可持久化要求不破坏旧根，与本节破坏式合并的所有权模型相反。

总结与自检

1. 合并总复杂度需要什么“节点不再复活”条件？
2. Tree Rotations 中为什么局部选择可独立？
3. 降序块按位置切前 k 个为何对应最大 k 个值？
4. 破坏式根为何不能再被旧版本引用？

课后训练建议

先实现只有 insert+merge 的值域树并核对多重集计数；再实现 split(k)，用排序 vector 对拍。排序题需每次操作后把所有块展开，与朴素数组比较，特别覆盖边界恰在块首/块尾。