线段树合并/分裂

· · 个人记录

线段树合并

一般来说，线段树合并涉及到的线段树是指动态开点线段树。

考虑如何合并两棵树。

先考虑一些简单的情况：

  1. 两棵树中有至少一颗为空。这时直接返回另一颗即可。

  2. 两棵树都只有叶子节点。直接合并叶子节点并返回即可。

否则就是一般情况，这时我们可以考虑暴力合并左右儿子，然后 pushup 出根节点的信息。

这样看起来复杂度就是错的，两颗满的线段树就能将复杂度卡到 O(n)。

但是注意到，每次执行一般情况就意味着其中一个线段树的根被合并进去了，记单次合并减少了 c 个节点，合并的复杂度就是 O(c)。（这里假设 pushup 复杂度是 O(1)）

而在题目中，总结点数是修改次数乘上 O(\log n) 的，而线段树合并的总复杂度一定不会超过总结点数，因此复杂度可以保证。

要注意一个坑点：不能先合并完所有线段树后在处理询问，要在合并后立刻处理对应的询问。

线段树分裂

这一部分或许比较类似 FHQ-Treap。

分裂时，先将根节点 copy 过来，然后根据值或排名确定一个儿子的归属，在递归另一个儿子即可。

每次最多新建 O(\log n) 个节点，复杂度是对的。

事实上，有关线段树分裂的题特别少，因为大部分可以线段树分裂的题存在其他做法，例如平衡树。

例题 1（Luogu 4556）

本题的修改操作是在链上加，直接维护十分麻烦，但单点加却可以直接使用动态开点线段树维护，相当于单点修改全局 \max。

因为查询在修改之后，所以考虑用树上差分把修改拆成单点加，在用线段树合并来优化最后树上前缀和的部分，求得每个节点所对的，真实的线段树。

这样复杂度 O(q\log n)。

例题 2（Luogu 5494）

本题的 2,3,4 操作可以直接用线段树维护，同时，本题的 1 操作相当于线段树合并，而 0 操作直接用上面的线段树分裂做即可。

总复杂度是 O(q\log n)。

你可能会发现一个事情，涉及到线段树分裂的题也会涉及到线段树合并，这是因为如果只有分裂，那么 FHQ-Treap 也可以做到。但因为 FHQ-Treap 的合并要求值域区间不能有交，所以无法替代线段树合并。（似乎存在使 FHQ-Treap 在值域有交的情况合并的方法，而且能保证均摊复杂度，不过比这个要劣）

例题 3（Codeforces 600E）

注意到如果我们同时维护最大出现次数，占重要地位的颜色编号和具有可合并性，直接上线段树合并就做完了。

复杂度 O(n\log n)。

例题 4（Luogu 2824）

这个题存在一个用二分将序列 0/1 化做的 O(q\log^2n) 做法。不过不是重点。

注意到权值线段树的结构可以求第 k 大，这本质就相当于排序。所以，初始对每一个位置开权值线段树维护。

这样，排序相当于合并若干个线段树为一个连续段。注意到可能会把两侧连续段拆开，这部分用线段树分裂来维护即可。

由颜色段均摊的结论，总复杂度为 O((n+q)\log n)。

这个做法可以做在线。

例题 5（Qoj 12325）

前两个操作直接线段树维护即可。

异或的操作相当于交换某一层的左右子树，可以通过打标记解决。

而与和或的操作相当于合并某些层的两个儿子，使用线段树合并即可。

注意这里 pushdown 和合并会相互调用，不过不影响总点数，故不影响复杂度。

在实现上，可以把所有层的同种标记压到一个 int 里。

做完了，复杂度 O((n+q)\log n)。

例题 6（Luogu 3224）

使用并查集维护联通块，对于第 k 小，不难想到权值线段树维护。

因此，我们对每一个联通块开一颗权值线段树，这样合并联通块就是线段树合并，做完了，复杂度 O((n+q)\log n)。

还有一个比较知名，而且也用了这种对联通块开权值线段树的题，这个题是 NOIP 2021 T4。

例题 7（Luogu 5327）

这个题有一个 O(n\log^3n) 做法，不过不是重点。

考虑对 u 计算满足条件的 v 的个数，发现满足条件的 v 构成一个包含 v 的连通块。

从连通块的边界点考虑，对路径 (u,v) 的修改相当于把 u 和 v 加入到 (u,v) 路径上的点的边界点集合。

这样求答案相当于求虚树边权和，设边界点集合为 S，我们考虑建虚树的过程，将 S 的点按 dfn 序排序，设排完序后为 S_1,\dots,S_k，我们知道此时虚树边权和为 \sum\limits_{i=1}^kdep_{S_i}-\sum\limits_{i=1}^{k-1}dep_{lca(S_i,S_{i+1})}-dep_{lca(S_1,S_k)}。而满足条件 v 的数量恰好就是边权和。

对于 dep_{lca(S_1,S_k)} 我们在查询时考虑，对于剩余部分，我们按 dfn 序开值域线段树，每次合并可以通过维护最小值，最大值，答案的方式做到 O(\log n) 合并（就是两边的和减掉跨过中点的部分），使用 O(1) LCA 可以优化到 O(1) 合并。

对于修改，使用树上差分拆成单点修改，线段树合并求答案即可。

复杂度 O(q\log n)。

例题 8（Luogu 5298）

考虑一个朴素的 DP，f_{u,i} 表示以 u 为根的子树中权值为 i 的概率。

对于儿子少于两个的情况，要么是叶节点，要么可以直接继承子节点的 DP 值。

否则，我们要做的事情相当于合并两个儿子的 DP 值。假设我们合并 u,v，则 f_{u,x} 的贡献系数与 \sum\limits_{y<x}f_{v,y} 和 \sum\limits_{y>x}f_{v,y} 有关。

考虑使用数据结构维护 DP 值。这里采用权值线段树，合并两个儿子的 DP 值相当于线段树合并。

在合并时，因为系数和前后缀和有关，所以我们需要在合并时维护左右两边 DP 值的和，这可以通过在线段树节点上维护 DP 值的和做到。对于一边为空的情况，我们可以通过打区间乘法 tag 来维护 DP 值的变化。

做完了，复杂度 O(n\log n)。

例题 9（Luogu 6773）

考虑如何刻画限制的形式，从深度更深的节点刻画限制显然更好做，考虑 DP，设 f_{u,i} 表示考虑完节点 u 所在的子树，限制中深度最深的点的深度为 i 的答案。直接 DP 就可以做 O(nm)。

转移可以概括为如下步骤：

  1. 先初始化 f_{u,lim_u}=1。

  2. 考虑儿子节点 v 连向父亲的边是否是重要的，即把 f_{v,*} 的和加到 f_{v,0} 上。

  3. 对 f_{u,*} 和 f_{v,*} 做 \max 卷积。

  4. 此时 f_{u,dep_u} 不合法，将其设为 0。

步骤 1，2，4 可以直接用线段树维护，步骤 3 可以线段树合并，合并时类似上题维护前缀和，把 \max 的贡献放到大的元素上即可。