线段树合并学习笔记

前言

我是一个什么什么傻卵啊啊啊啊啊啊啊啊，连线段树合并都学不明白qaq

正文

权值线段树

含义：

是用来维护好多好多桶的线段树. 桶是一个用来计数的东西.

与普通线段树的区别

普通线段树是用来维护区间和、积、最值等一系列的东西.

权值线段树是用来维护某个区间内的数出现了多少次的。它还可以插入数据，维护第 \(k\) 小(大)值.

动态开点

有时候题目给的数据范围很大，用普通的线段树可能会MLE时，我们就会选择动态开点。动态开点，就是什么时候需要某个点，什么时候把它建出来。所以动态开点线段树的编号法则不符合普通线段树的“父子二倍法”。我们选择用一个非常普通的计数变量(例如 \(cnt\) )来表示线段树的节点编号.

代码实现

void insert(int& p, int l, int r, int x, int v) {
    // p是节点编号, 要引用传参, [l, r]是值域, x ∈ [l, r], v是增量.
    if (!p) p = ++cnt; // 如果不存在这个节点, 就把这个节点开出来.
    if (l == r) { // 递归到叶子结点.
        t[p].data += v;
        return;
    }

    int mid = (l + r) >> 1;
    // 判断x在哪一半区间内
    if (x <= mid) insert(t[p].l, l, mid, x, v);
    else insert(t[p].r, mid + 1, r, x, v);
    pushup(p);
}

线段树合并

就是把若干棵线段树合并到一起. 合并操作是求和(积)还是求最值取决于个人需要.

合并的两棵线段树的大的值域应当是相同的.

如何合并

• 先递归到叶子结点.
• 若两棵线段树的相同位置都存在节点, 则合并两个节点作为新的节点.
• 若某一刻线段树的相应节点不存在, 则取那个存在的节点作为新的节点.

代码实现

void merge(int& a, int b, int l, int r) {
    // a需要引用传参, 因为将b合并到a上.
    if (!a || !b) {
        a = a ? a : b;
        return;
    }
    if (l == r) {
        t[a].data += t[b].data;
        // 这里是对值的合并操作. 这里以两棵线段树求和为例.
        return;
    }

    int mid = (l + r) >> 1;
    // 左子树和左子树合并, 右子树和右子树合并.
    merge(t[a].l, t[b].l, l, mid);
    merge(t[a].r, t[b].r, mid + 1, r);
    pushup(a);
}