线段树合并/分裂/优化 学习笔记

线段树合并

过程

顾名思义，线段树合并是指建立一棵新的线段树，这棵线段树的每个节点都是两棵原线段树对应节点合并后的结果。它常常被用于维护树上或是图上的信息。

显然，我们不可能真的每次建满一颗新的线段树，因此我们需要使用上文的动态开点线段树。

线段树合并的过程本质上相当暴力：

假设两颗线段树为 A 和 B，我们从 1 号节点开始递归合并。

递归到某个节点时，如果 A 树或者 B 树上的对应节点为空，直接返回另一个树上对应节点，这里运用了动态开点线段树的特性。

如果递归到叶子节点，我们合并两棵树上的对应节点。

最后，根据子节点更新当前节点并且返回。

线段树合并的复杂度

显然，对于两颗满的线段树，合并操作的复杂度是 $O(n\log n)$ 的。但实际情况下使用的常常是权值线段树，总点数和 $n$ 的规模相差并不大。并且合并时一般不会重复地合并某个线段树，所以我们最终增加的点数大致是 $n\log n$ 级别的。这样，总的复杂度就是 $O(n\log n)$ 级别的。当然，在一些情况下，可并堆可能是更好的选择。

实现

int merge(int a, int b, int l, int r) {
    if (!a)
        return b;
    if (!b)
        return a;
    if (l == r) {
        // do something...
        return a;
    }
    int mid = (l + r) >> 1;
    tr[a].l = merge(tr[a].l, tr[b].l, l, mid);
    tr[a].r = merge(tr[a].r, tr[b].r, mid + 1, r);
    pushup(a);
    return a;
}

另一种实现

不难发现上面的过程其实是在覆写节点 $a$ 所在的线段树，如果想要同时保存合并前后的线段树，可以参考主席树的实现方式，为每个需要合并的节点多开一个节点来存储信息，然后保存每个合并后的线段树的根节点编号（就像主席树的版本号一样），与主席树的不同之处在于一次合并可能涉及多条链上的修改

这种写法每次合并额外需要的空间开销是这次合并的两颗线段树的重叠节点数量，所以通常空间开销是和修改量成增长速度相同的，不会爆炸，但不排除题目情况特殊

线段树分裂

过程

线段树分裂实质上是线段树合并的逆过程。线段树分裂只适用于有序的序列，无序的序列是没有意义的，常用在动态开点的权值线段树。

注意当分裂和合并都存在时，我们在合并的时候必须回收节点，以避免分裂时会可能出现节点重复占用的问题。

从一颗区间为 $[1,N]$ 的线段树中分裂出 $[l,r]$，建一颗新的树：

从 1 号结点开始递归分裂，当节点不存在或者代表的区间 $[s,t]$ 与 $[l,r]$ 没有交集时直接回溯。

当 $[s,t]$ 与 $[l,r]$ 有交集时需要开一个新结点。

当 $[s,t]$ 包含于 $[l,r]$ 时，需要将当前结点直接接到新的树下面，并把旧边断开。

线段树分裂的复杂度

可以发现被断开的边最多只会有 $\log n$ 条，所以最终每次分裂的时间复杂度就是 $O(\log n)$，相当于区间查询的复杂度

实现

void split(int &p, int &q, int s, int t, int l, int r) {
    if (t < l || r < s)
        return;
    if (!p)
        return;
    if (l <= s && t <= r) {
        q = p;
        p = 0;
        return;
    }
    if (!q)
        q = New();
    int m = s + t >> 1;
    if (l <= m)
        split(ls[p], ls[q], s, m, l, r);
    if (m < r)
        split(rs[p], rs[q], m + 1, t, l, r);
    push_up(p);
    push_up(q);
}

线段树优化建图

在建图连边的过程中，我们有时会碰到这种题目，一个点向一段连续的区间中的点连边或者一个连续的区间向一个点连边，如果我们真的一条一条连过去，那一旦点的数量多了复杂度就爆炸了，这里就需要用线段树的区间性质来优化我们的建图了。

下面是一个线段树。

每个节点都代表了一个区间，假设我们要向区间 $[2,4]$ 连边。

在一些题目中，还会出现一个区间连向一个点的情况，则我们将上面第一张图的有向边全部反过来即可，上面的树叫做入树，下面这个叫做出树。

Legacy

题目大意：有 $n$ 个点、$q$ 次操作。每一种操作为以下三种类型中的一种：

• 操作一：连一条 $u\to v$ 的有向边，权值为 $w$。
• 操作二：对于所有 $i\in [l,r]$ 连一条 $u\to i$ 的有向边，权值为 $w$。
• 操作三：对于所有 $i\in [l,r]$ 连一条 $i\to u$ 的有向边，权值为 $w$。

求从点 $s$ 到其他点的最短路。

$1\le n,q\le 10^5,1\le w\le 10^9$

拓展 - 猫树

众所周知线段树可以支持高速查询某一段区间的信息和，比如区间最大子段和，区间和，区间矩阵的连乘积等等。

但是有一个问题在于普通线段树的区间询问在某些毒瘤的眼里可能还是有些慢了。

简单来说就是线段树建树的时候需要做 $O(n)$ 次合并操作，而每一次区间询问需要做 $O(\log n)$ 次合并操作，询问区间和这种东西的时候还可以忍受，但是当我们需要询问区间线性基这种合并复杂度高达 $O({\log }^{2}w)$ 的信息的话，此时就算是做 $O(\log n)$ 次合并有些时候在时间上也是不可接受的。

而所谓「猫树」就是一种不支持修改，仅仅支持快速区间询问的一种静态线段树。

构造一棵这样的静态线段树需要 $O(n\log n)$ 次合并操作，但是此时的查询复杂度被加速至 $O(1)$ 次合并操作。

在处理线性基这样特殊的信息的时候甚至可以将复杂度降至 $O(n{\log }^{2}w)$。

原理

在查询 $[l,r]$ 这段区间的信息和的时候，将线段树树上代表 $[l,l]$ 的节点和代表 $[r,r]$ 这段区间的节点在线段树上的 LCA 求出来，设这个节点 $p$ 代表的区间为 $[L,R]$，我们会发现一些非常有趣的性质：

1. $[L,R]$ 这个区间一定包含 $[l,r]$。显然，因为它既是 $l$ 的祖先又是 $r$ 的祖先。

2. $[l,r]$ 这个区间一定跨越 $[L,R]$ 的中点。由于 $p$ 是 $l$ 和 $r$ 的 LCA，这意味着 $p$ 的左儿子是 $l$ 的祖先而不是 $r$ 的祖先，$p$ 的右儿子是 $r$ 的祖先而不是 $l$ 的祖先。因此，$l$ 一定在 $[L,mid]$ 这个区间内，$r$ 一定在 $(mid,R]$ 这个区间内。

有了这两个性质，我们就可以将询问的复杂度降至 $O(1)$ 了。

实现

具体来讲我们建树的时候对于线段树树上的一个节点，设它代表的区间为 $(l,r]$。

不同于传统线段树在这个节点里只保留 $[l,r]$ 的和，我们在这个节点里面额外保存 $(l,mid]$ 的后缀和数组和 $(mid,r]$ 的前缀和数组。

这样的话建树的复杂度为 $T(n)=2T(n/2)+O(n)=O(n\log n)$ 同理空间复杂度也从原来的 $O(n)$ 变成了 $O(n\log n)$。

下面是最关键的询问了。

如果我们询问的区间是 $[l,r]$ 那么我们把代表 $[l,l]$ 的节点和代表 $[r,r]$ 的节点的 LCA 求出来，记为 $p$。

根据刚才的两个性质，$l,r$ 在 $p$ 所包含的区间之内并且一定跨越了 $p$ 的中点。

这意味这一个非常关键的事实是我们可以使用 $p$ 里面的前缀和数组和后缀和数组，将 $[l,r]$ 拆成 $[l,mid]+(mid,r]$ 从而拼出来 $[l,r]$ 这个区间。

而这个过程仅仅需要 $O(1)$ 次合并操作！

不过我们好像忽略了点什么？

似乎求 LCA 的复杂度似乎还不是 $O(1)$，暴力求是 $O(\log n)$ 的，倍增法则是 $O(\log \log n)$ 的，转 ST 表的代价又太大……

堆式建树

具体来将我们将这个序列补成 $2$ 的整次幂，然后建线段树。

此时我们发现线段树上两个节点的 LCA 编号，就是两个节点二进制编号的最长公共前缀 LCP。

稍作思考即可发现发现在 $x$ 和 $y$ 的二进制下 lcp(x,y)=x>>log[x^y]。

所以我们预处理一个 log 数组即可轻松完成求 LCA 的工作。

这样我们就构建了一个猫树。

由于建树的时候涉及到求前缀和和求后缀和，所以对于线性基这种虽然合并是 $O({\log }^{2}w)$ 但是求前缀和却是 $O(n\log n)$ 的信息，使用猫树可以将静态区间线性基从 $O(n{\log }^{2}w+m{\log }^{2}w\log n)$ 优化至 $O(n\log n\log w+m{\log }^{2}w)$ 的复杂度。