线段树合并 学习笔记

过程

合并并不困难，对于两棵线段树，合并无疑就是就两棵线段树维护的区间信息进行合并。

就比如，有两棵线段树如下图：

将第二棵树合并到第一棵树，就是把除了维护 \([2, 2]\) 的全部对应加，而 \([2, 2]\) 则新开节点维护。

时间复杂度显然 \(\mathcal{O}(n \log n)\)。

实现

int Merge(int x, int y, int l, int r){
        if (!x || !y) {
            return x + y;
        }

        if (l == r) {
        //merge segment
            return x;
        }
        
        int mid = l + r >> 1;

        s[x].l = Merge(s[x].l, s[y].l, l, mid);
        s[x].r = Merge(s[x].r, s[y].r, mid + 1, r);
        
        pushup(x);
        
        return x;
    }

当然，也可以开新树维护合并结果。