线段树分裂 学习笔记

过程

线段树分裂是线段树合并的逆操作，即将一个区间信息分裂到新的树中，新的树一般需要新建。

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

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

实现

//将 x 分裂出 [p, q] 到 now 上
void split(int &x, int &now, int l, int r, int p, int q){
        if (!x) {
            return;
        }
        
        if (p <= l && r <= q) {
            now = x;
            x = 0;
            return;
        }
        
        if (!now) {
            New(now);
        }

        int mid = l + r >> 1;
        if (p <= mid) {
            split(s[x].l, s[now].l, l, mid, p, q);
        }

        if (q > mid) {
            split(s[x].r, s[now].r, mid + 1, r, p, q);
        }

        pushup(x), pushup(now);
    }