线段树合并

pig1121 · 2024-12-24 19:54:13 · 算法·理论

众所周知，线段树在处理很多问题时都有较高的效率。

引入

考虑这么一个问题：

• 有一棵 n 个结点的以 1 号结点为根的有根树。
• 每个结点都有一个颜色，颜色是以编号表示的， i 号结点的颜色编号为 c_i。
• 对于每一个 i\in[1,n]，求出以 i 为根的子树中，编号在 [l_i,r_i] 的颜色的出现次数和。
• n\le 10^5,c_i\le n

啊，这不是可以用 DSU on tree 套一棵线段树/树状数组水过吗，复杂度 O(n\log^2n) 比刚刚那题还要水……

• 那如果 n\le 10^6,c_i\le n 呢？

我们发现 DSU on tree 虽然可以做到只进行 O(n\log n) 次数据结构的插入操作，但对于大部分 O(\log n) 往上插入的数据结够，该复杂度在某些毒瘤出题人眼里还不够优秀。

DSU on tree 的本质还是暴力合并，没有利用具体的数据结构进行优化，对于线段树这种复杂的树形结构，有没有什么方法实现单次/均摊 O(\log n) 合并的方法？

分析

考虑直接对两棵线段树进行“合并”操作，这里我们默认“合并”为对应位置相加。

最暴力的想法：直接 DFS，复杂度 O(n)，实现：

int merge(int u,int v){
    if(!tr[u].ls&&!tr[u].rs){
        tr[u].sum+=tr[v].sum;
        return u;
    }
    tr[u].ls=merge(tr[u].ls,tr[v].ls)
    tr[u].rs=merge(tr[u].rs,tr[v].rs);
    update(u);
    return u;
}

然鹅我们发现，如果其中一棵树是空的，那么直接返回另一棵树就行了。

int merge(int u,int v){
    if(!u||!v)return u|v;
    if(!tr[u].ls&&!tr[u].rs){
        tr[u].sum+=tr[v].sum;
        return u;
    }
    tr[u].ls=merge(tr[u].ls,tr[v].ls)
    tr[u].rs=merge(tr[u].rs,tr[v].rs);
    update(u);
    return u;
}

还能怎么优化呢？看来不太好办哦？

不过你抱着试一试的心态将这个玩意交到了 DSU on tree 模版。

过了。。。

难道它的复杂度是正确的？

让我们分析一下：

首先单次合并的复杂度显然为两颗线段树重叠的节点数（每访问 1 个重叠的节点最多访问 2 个未重叠的节点），即 O(siz_u+siz_v-siz_{u\cup v})。归纳可知合并 k 棵树总复杂度为 O(\sum siz_i-siz_{\bigcup i})<O(\sum siz_i)

由于我们一共只有 n 次插入，所以节点总数 O(n\log n)，复杂度正确。

延伸

观察模板代码，我们发现它只应用到了两个对线段树的操作：

1. 合并叶子节点
2. 由子节点更新父节点的信息

所以我们可以认为大部分能用线段树维护的信息都能在树上（子树内）用线段树合并维护了……吗？

注意到前面的应用仅限于单点操作，如果你试图在上面的代码上使用懒标记并加入 pushdown……

由于 pushdown 操作会清空父节点的标记，所以在动态开点线段树中 pushdown 时需要建出子节点，然后……你的动态开点线段树在一通 pushdown 操作后成功变成了一棵完全二叉树，它点数是 O(n) 的……

所以对于区间修改，在合并时需要对标记进行合并，但有些“良心”出题人总能给你弄出一些不好裸合并的东西，所以可以考虑对于没有儿子的节点直接合并，这样因为要合并区间是同一个值/有同一个规律的值，通常可以较为轻松地将一个一致的区间并到另一个区间上，并且这种方式最多多递归一层，一次操作的节点数仍是 O(\log n) 的。实现大致如下：

int merge(int u,int v,int l,int r){
    if(!u||!v)return u|v;
    if(l==r){
        //合并叶子
        return u;
    }
    if((!tr[u].ls&&!tr[u].rs)){
        //将区间 u 并到 v 上
        return v;
    }
    if((!tr[v].ls&&!tr[v].rs)){
        //将区间 v 并到 u 上
        return u;
    }
    pushdown(u);
    pushdown(v);
    int mid=(l+r)>>1;
    tr[u].ls=merge(tr[u].ls,tr[v].ls,l,mid);
    tr[u].rs=merge(tr[u].rs,tr[v].rs,mid+1,r);
    return u;
}

现在我们就可以快乐地以均摊 O(\log n) 的复杂度合并带区间修改的信息了。