归并排序树

与前面的情况不同，这里在线段树每个节点中，不再以压缩形式保存对应区间的信息（和、最小值、最大值等），而是直接保存这个区间中的所有元素。

因此：

根节点保存数组中的所有元素；
左子节点保存数组的前一半；
右子节点保存数组的后一半；
依此类推。

这种技术最简单的应用，是把这些元素按排序后的顺序保存。更复杂的版本中，元素甚至不会保存在线性表中，而会保存到更加高级的数据结构中，例如： set，map 等。

不过，这些方法都有一个共同特点：每个节点都需要线性大小的内存。也就是说，所需内存与对应区间长度成正比。

考虑这种线段树时，第一个自然的问题就是内存消耗。直观上看，它似乎需要 $O(n^2)$ 的内存。但实际上，整棵树只需要 $O(n\log n)$ 的内存。为什么？原因非常简单：数组中的每个元素只会出现在 $O(\log n)$ 个区间中——不要忘记树的高度是 $O(\log n)$ 。因此，尽管这种线段树看起来非常“奢侈”，实际上它消耗的内存只比普通线段树多一些。

下面介绍这种数据结构的一些典型应用。

值得注意的是，这类线段树与二维数据结构非常相似。实际上，它本身确实可以看成一种二维数据结构，只不过能力受到了一些限制。

查找大于等于指定值的最小数——没有修改操作

我们希望回答如下查询：

区间查询

给定三个数 $(l,r,x)$ ，找出区间 $a[l\dots r)$ 中所有大于等于 $x$ 的数中最小的一个。

构建一棵线段树。按照前面描述的方法，在每个节点中保存对应区间内所有数的有序列表。

怎样尽可能高效地构建这样的线段树？

和往常一样，我们递归解决：假设左子节点和右子节点的列表已经构建完成，现在需要构建当前节点的列表。从这个角度看，操作非常简单，并且可以在线性时间完成：只需要把两个有序列表合并成一个有序列表。

通过两个指针同时遍历两个列表即可做到这一点。C++ STL 已经提供了这种算法的实现。由于这种线段树的结构与归并排序算法十分相似，所以这种数据结构通常也被称为：

Merge Sort Tree（归并排序树）。

vector<int> t[4*MAXN];

void build(int p, int l, int r) {
    if (l == r) {
        t[p] = vector<int>(1, A[p]);
        return;
    } 
    int mid = (l + r) / 2;
    build(p*2, l, mid);
    build(p*2+1, mid + 1, r);
    merge(t[p*2].begin(), t[p*2].end(), t[p*2+1].begin(), t[p*2+1].end(), back_inserter(t[p]));
}

我们已经知道，这样构建的线段树需要 $O(n\log n)$ 的内存。得益于这种实现，它的构建过程同样需要 $O(n\log n)$ 的时间，因为每个列表的构建时间都与其自身大小成线性关系。

现在考虑如何回答查询。

像普通线段树一样向下遍历，把区间 $a[l\dots r)$ 拆分成若干个子区间，最多有 $O(\log n)$ 个。显然，整个查询的答案就是各个子查询答案中的最小值。因此，现在只需要理解如何回答对应树中某个节点的单个子区间查询。当前位于线段树中的某个节点，希望求出查询答案，也就是：找到大于等于给定数 $x$ 的最小数。

由于这个节点中的元素已经按照有序顺序保存，因此只需要在这个列表上执行一次二分查找，并返回第一个大于等于 $x$ 的数即可。因此，在树中的单个区间上回答查询需要 $O(\log n)$ 时间，整个查询需要 $O(\log^2 n)$ 时间。

int query(int v, int tl, int tr, int l, int r, int x) {
    if (r <= tl || tr <= l) return INF;
    if (l <= tl && tr <= r) {
        auto pos = lower_bound(t[v].begin(), t[v].end(), x);
        if (pos != t[v].end()) return *pos;
        return INF;
    }
    int tm = (tl + tr) / 2;
    return min(query(v*2, tl, tm, l, r, x), (v*2+1, tm, tr, l, r, x));
}

常量 INF 是一个大于数组中所有元素的足够大的数。使用它表示在这个区间中不存在大于等于 $x$ 的元素，也就是：“给定区间中不存在答案”。

查找大于等于指定值的最小数——支持修改

这个问题与上一节类似。

之前的方法有一个缺点：在回答查询之间无法修改数组。现在我们希望允许修改： $a[i]=y$ 。解决方法与上一个问题类似。但是不再在线段树的每个节点中保存普通列表，而是保存一种平衡的数据结构，使我们能够快速：

查找数；
删除数；
插入新的数。

由于数组中可能出现重复数字，因此最合适的数据结构是 multiset。构建这样的线段树与上一个问题基本相同，只不过现在需要合并的是 multiset，而不是有序列表。这会导致构建时间为 $O(n\log^2 n)$ 。

一般来说，合并两棵红黑树可以在线性时间内完成，不过 C++ STL 并不保证这种时间复杂度。

query 函数也几乎完全相同。只不过现在应该调用 multiset 自己的 lower_bound 函数。因为 std::lower_bound 只有在随机访问迭代器上使用时才能达到 $O(\log n)$ 时间。

最后考虑修改操作。

为了处理它，我们必须沿树向下，并修改所有对应区间包含被修改元素的 multiset。只需要：

删除这个元素的旧值（只删除一次出现）；
插入新的值。

void update(int v, int tl, int tr, int pos, int new_val) {
    t[v].erase(t[v].find(a[pos]));
    t[v].insert(new_val);
    if (tl != tr) {
        int tm = (tl + tr) / 2;
        if (pos < tm)
            update(v*2, tl, tm, pos, new_val);
        else
            update(v*2+1, tm, tr, pos, new_val);
    } else {
        a[pos] = new_val;
    }
}

处理这种修改查询同样需要 $O(\log^2 n)$ 时间。

查找大于等于指定值的最小数——使用“分数级联”加速

问题与之前完全相同：

问题

希望在一个区间中找到大于等于 $x$ 的最小数。

但这一次希望把时间复杂度降低到 $O(\log n)$ 。

我们使用一种称为 Fractional Cascading（分数级联） 的技术来改进复杂度。

分数级联是一种简单的技术，可以提升同时执行多次二分查找时的运行效率。

在之前的查询方法中，我们把问题分成多个子问题，而每个子问题都需要执行一次二分查找。

分数级联可以把所有这些二分查找替换成一次二分查找。

分数级联最简单、最直观的例子是：

有 $k$ 个有序数字列表，现在必须在每个列表中找出第一个大于等于给定值的数。

与其对每个列表分别执行二分查找，不如把所有列表合并成一个大的有序列表。

此外，对于每个元素 $y$ ，保存分别在这 $k$ 个列表中搜索 $y$ 得到的结果。

于是，当要找大于等于 $x$ 的最小值时，只需要执行一次二分查找，然后根据保存的下标列表，就可以确定每一个列表中的答案。不过，这种方法需要 $O(n\cdot k)$ 的内存，其中 $n$ 是所有列表合并后的长度。这可能会非常低效。

分数级联把内存复杂度降低到 $O(n)$ 。

具体做法是：

根据 $k$ 个输入列表构造 $k$ 个新的列表。每个新列表不仅包含对应的原列表，还额外包含后一个新列表中的每隔一个元素。使用这种结构后，只需要为每个元素保存两个下标：

它在原列表中的位置；
它在下一个新列表中的位置。

因此，这种方法只使用 $O(n)$ 的内存，同时仍然能够通过一次二分查找回答查询。

不过，在我们的应用中，并不需要完整使用分数级联的全部能力。

在线段树中，一个节点会包含左、右子树中所有出现元素组成的有序列表，与 Merge Sort Tree 相同。

除此之外，对于列表中的每个元素，再额外保存两个位置。

对于元素 $y$ ，保存：

最小的下标 $i$ ，使左子节点有序列表中的第 $i$ 个元素大于等于 $y$ ；
最小的下标 $j$ ，使右子节点有序列表中的第 $j$ 个元素大于等于 $y$ 。

这些值可以在构建树、合并两个列表的过程中同步计算。

那么，这如何加速查询？

回忆一下，在普通方法中，我们需要在每个节点中执行一次二分查找。

采用这种修改后，除了第一次以外，其余二分查找都可以避免。

为了回答查询，只需在根节点中执行一次二分查找。

这会得到整个数组中最小的满足

y\ge x

的元素。

与此同时，还会得到两个位置：

左子树中大于等于 $x$ 的最小元素的位置；
右子树中大于等于 $x$ 的最小元素的位置。

注意，

\ge y

与

\ge x

是相同的，因为数组中不存在位于 $x$ 与 $y$ 之间的元素。

在普通 Merge Sort Tree 中，需要用二分查找计算这些位置。

现在借助预先计算好的值，可以直接在

O(1)

时间内查到这些位置。

之后不断重复这个过程，直到访问完所有覆盖查询区间的节点。

总结来说，一次查询仍然访问

O(\log n)

个节点。

在根节点上进行一次二分查找，而其余节点只执行常数时间的操作。

因此，查询时间复杂度为

O(\log n).

不过需要注意：

这种方法消耗的内存大约是普通 Merge Sort Tree 的三倍，而普通 Merge Sort Tree 本身已经需要大量内存：

O(n\log n).

如果问题不需要修改操作，那么应用这种技术非常直接。

两个位置都只是整数，可以在合并两个有序序列时通过计数轻松计算。

实际上，也可以让这种结构支持修改操作，但代码会复杂得多。

此时：

不能使用整数下标；
必须把有序数组保存为 multiset；
必须保存迭代器而不是下标。

而在执行修改操作时，必须非常小心，确保正确地增加或减少相应的迭代器。

其他可能的变化

这种技术带来了一整类新的应用。

在线段树的每一个节点中，不一定必须保存 vector 或 multiset。

也可以保存其他数据结构，例如：

另一棵线段树（在后面的推广到更高维中会稍作讨论）；
Fenwick Tree（树状数组）；
笛卡尔树；
等等。

查找大于等于指定值的最小数——没有修改操作​

查找大于等于指定值的最小数——支持修改​

查找大于等于指定值的最小数——使用“分数级联”加速

其他可能的变化​

查找大于等于指定值的最小数——没有修改操作

查找大于等于指定值的最小数——支持修改

其他可能的变化