线段树：权值？合并？动态开点？都没听说过

零、背景

《leetcode 第 258 场算法比赛》的第四题是一道很有趣的题。

比赛的时候我使用贪心，把树转化为链，然后 DFS 通过了。

上上上篇文章《树上并查集》介绍了一个万能的树上并查集方法，甚至允许有重复权重值。
上上篇文章《RMQ LCA 解决 MEX 子树问题》介绍了一个 LCA 的方法，不过不支持重复权重值。
上篇文章《树递归编号 解决 MEX 子树问题》介绍了树递归编号的方法来解决问题，也不支持重复权重值。

今天我再分享一个高端线段树的算法来解决这个问题。

一、题目

给一个有根树，每个节点有一个正整数值（互不相同）。
对于每个子树，问子树的节点值里面，最小的未出现的正整数是多少。

最小的未出现的正整数有个专业名称，叫做 mex（Minimum excludant）。

二、朋友圈

比赛后，有人给我发了一个题解。
我一看，完全看不懂。
于是发了一个朋友圈，问是啥算法。

朋友圈的大佬有人说是线段树合并，有人说是权值线段树。

我一脸懵逼，这是什么呢？怎么没听说过呢？

三、权值线段树

普通的线段树是给一个坐标位置，可以设置值。
然后可以查询区间最值或者区间和等问题。

权值线段树只关心下标这一个数据，用于统计不同下标出现的次数。

储存了这个数据后，就可以查询第 K 小/大值问题了。
当然，同样可以查询最小的未出现的正整数。

逻辑也很容易理解。
左子树区间大小与出现的数字个数相同，那显然答案在右区间，否则肯定在左区间。

int Query(int x, int l, int r){
    if(x == 0) return l;
    if(V[x] == r - l + 1) return r + 1; 

    int mid = (l + r) >> 1;
    int leftAns = Query(L[x], l, mid);
    if(leftAns <= mid) return leftAns;

    return Query(R[x], mid + 1, r);
}

四、线段树合并

一个线段树是一个不可拆分的完整的树。
前面插入的点将会影响后面插入点的查询。

而面对子树问题时，左子树与右子树往往是没关系的。
这时候就需要对左子树与右子树分别建一个线段树，等分别求出各自的答案后，再合并出当前子树的线段树。

下面的代码是合并的权值线段树，将 y 为根的线段树合并到 x 为根的线段树。

int Merge(int x, int y) {
    if(x == 0 || y == 0) return x == 0 ? y : x;
    V[x] += V[y];
    L[x] = Merge(L[x], L[y]);
    R[x] = Merge(R[x], R[y]);
    return x;
}

五、动态开点线段树

前面提到需要给每个子树创建一个线段树。

如果每个线段树初始化的时间复杂度是 O(N), 那建 n 个线段树的复杂度就是 O(N^2)的时间了。

所以这里使用普通的线段树是不可行的。

然后就有人提出，既然树可以使用一个一维数组代替二维数组，那自然线段树也可以做到。

具体来说就是，线段树的某个节点存在值时，再开辟节点的内存空间。
这样对于稀疏矩阵，只需要很小的空间就可以表示一个线段树。

有时对于那种区间很大的线段树，离散化也解决不了，就可以采用动态开点的方式来储存线段树。

当然，这里我们使用动态开点方式储存的权值线段树。
非权值线段树应该一样可以表达的。

int L[M], R[M], V[M]; 

int index;
void Insert(int& x, int l, int r, int v) {
    x = ++index;
    L[x] = R[x] = 0;
    V[x] = 1;
    if(l == r) return ;
    int mid = (l + r) >> 1;
    if(v <= mid) {
        Insert(L[x], l, mid, v);
    } else {
        Insert(R[x], mid + 1, r, v);
    }
}

六、查询 MEX

上面介绍了权值线段树、线段树的合并、动态开点线段树。
综合利用这三个数据结构或算法，我们就可以解决线段树查询子树的问题了。

一开始，先给所有节点建立一个动态开点的权值线段树。

index = 0;
root.resize(n, 0);
for(int i = 0; i < n; i++) {
    Insert(root[i], 1, N, nums[i]);
}

由于每个权值线段树高度是log(n)，所以内存空间需要申请n log(n)大小。

const int N = 100000;
const int M = 20 * N;

之后，就可以递归的查询子树字段树，并合并子树线段树，从而递归的求出答案。

void Solver(int x) {
    for(auto v: g[x]) {
        Solver(v);
        root[x] = Merge(root[x], root[v]);
    }
    ans[x] = Query(root[x], 1, N);
}

七、最后

这次一下认识三个数据结构：权值线段树、线段树合并、动态开点线段树。

可能会有人会有疑问，我曾经作为 ACMER， 为啥会没听说过过这些数据结构呢？

之前我介绍过很多次了，大学的时候天天忙着做项目，只在大一暑假学了基础数据结构与算法，之后就没学习什么算法了。
所以我只会基础的数据结构，比赛就看运气了。

考察高级算法的时候（后缀数组、树套树、树链刨分等），我就不会了。
考察基础数据结构和算法时，我就能挣扎一下可以做出来。

当然，虽然曾经自己没努力学习，但现在依旧不能放弃。
随着打比赛，遇到新的数据结构与算法，努力去学习就是了。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code