保存历史版本（可持久化线段树）

**可持久化数据结构（Persistent Data Structure）**是一种能够在每次修改之后记住自己之前状态的数据结构。

这样就能够访问任意感兴趣的历史版本，并在那个版本上执行查询。

线段树可以非常高效地转换成可持久化数据结构，无论从时间还是内存消耗来看都是如此。

我们希望：

不需要在每次修改之前复制整棵树；
同时仍然保持区间查询

O(\log n)

的时间复杂度。

事实上，线段树中的任何一次修改操作，都只会导致：

从根节点开始的一条路径上

O(\log n)

个节点的数据发生变化。

因此，如果使用指针保存线段树，也就是说，每个节点保存指向左右子节点的指针，那么执行修改操作时，不需要修改已有节点，而只需要创建新的节点。

没有受到此次修改影响的节点仍然可以继续复用：

让新的节点的指针直接指向旧节点即可。

因此，一次修改查询只会创建

O(\log n)

个新节点，其中包括一个新的根节点。

与此同时，以旧根节点为根的整棵旧版本线段树完全保持不变。

下面给出最简单线段树的一个示例实现：

只支持区间求和查询以及单点修改。

struct Vertex {
    Vertex *l, *r;
    int sum;

    Vertex(int val) : l(nullptr), r(nullptr), sum(val) {}
    Vertex(Vertex *l, Vertex *r) : l(l), r(r), sum(0) {
        if (l) sum += l->sum;
        if (r) sum += r->sum;
    }
};

Vertex* build(int a[], int tl, int tr) {
    if (tr - tl == 1)
        return new Vertex(a[tl]);
    int tm = (tl + tr) / 2;
    return new Vertex(build(a, tl, tm), build(a, tm, tr));
}

int get_sum(Vertex* v, int tl, int tr, int l, int r) {
    if (r <= tl || tr <= l)
        return 0;
    if (l <= tl && tr <= r)
        return v->sum;
    int tm = (tl + tr) / 2;
    return get_sum(v->l, tl, tm, l, r)
         + get_sum(v->r, tm, tr, l, r);
}

Vertex* update(Vertex* v, int tl, int tr, int pos, int new_val) {
    if (tr - tl == 1)
        return new Vertex(new_val);
    int tm = (tl + tr) / 2;
    if (pos < tm)
        return new Vertex(update(v->l, tl, tm, pos, new_val), v->r);
    else
        return new Vertex(v->l, update(v->r, tm, tr, pos, new_val));
}

每次修改线段树都会得到一个新的根节点。

为了能够快速切换到线段树的不同版本，需要把这些根节点保存到一个数组中。

如果想使用某个特定版本的线段树，只需要使用对应的根节点调用查询函数即可。

使用上述方法，几乎任何线段树都可以转换成可持久化数据结构。

求区间第 $k$ 小

这一次需要回答如下查询：

区间
$a[l\dots r)$
中第 $k$ 小的元素是什么？

这个问题可以使用二分查找加 Merge Sort Tree 解决，但是一次查询的时间复杂度会达到

O(\log^3 n).

我们将使用可持久化线段树，把同一个任务做到

O(\log n).

首先讨论一个更简单的问题。

暂时只考虑所有元素都满足

0\le a[i]<n

的数组。

并且只需要求数组某个前缀中的第 $k$ 小元素。

之后再把这个方法轻松扩展到：

不受限制的数组值；
任意区间查询。

注意，这里对数组 $a$ 使用从 $1$ 开始的下标。

我们使用一棵线段树来统计所有出现过的数字。

也就是说，在线段树中保存数组的频率直方图。

叶节点分别保存数字

0,1,\dots,n-1

在数组中出现了多少次。

其他节点保存某个值域范围中的数字总共在数组中出现了多少次。

换句话说，就是在数组的频率直方图上构建普通的区间求和线段树。

但是，我们不会为所有 $n$ 个可能的前缀分别建立 $n$ 棵线段树。

而是构建一棵可持久化线段树，其中包含完全相同的信息。

开始时，建立一棵空线段树：

所有计数都为 $0$ 。

它的根节点记为

root_0.

然后依次加入

a[1],a[2],\dots,a[n].

每执行一次修改都会得到一个新的根节点。

记

root_i

为插入数组 $a$ 的前 $i$ 个元素之后得到的线段树根节点。

以

root_i

为根的线段树中，保存的就是前缀

a[1\dots i]

的频率直方图。

利用这棵线段树，可以使用前面“统计零并寻找第 $k$ 个零”中介绍的相同方法，在

O(\log n)

时间内找到第 $k$ 个元素的位置。

现在考虑没有限制的完整版本。

首先取消“只能查询前缀”的限制。

希望能够查询任意区间

a[l\dots r).

此时需要一棵表示区间

a[l\dots r)

中元素频率直方图的线段树。

很容易发现，这棵线段树恰好等于：

以

root_r

为根的线段树，减去以

root_{l-1}

为根的线段树。

也就是说，区间 $[l\dots r)$ 对应线段树中的每个节点，都可以通过

root_r

对应节点的值减去

root_{l-1}

对应节点的值得到。

在 find_kth 函数的实现中，只需要同时传入两个节点指针，然后把当前区间的计数／和计算为两个节点计数／和的差即可。

下面给出修改后的 build、update 和 find_kth 函数。

Vertex* build(int tl, int tr) {
    if (tr - tl == 1)
        return new Vertex(0);
    int tm = (tl + tr) / 2;
    return new Vertex(build(tl, tm), build(tm, tr));
}

Vertex* update(Vertex* v, int tl, int tr, int pos) {
    if (tr - tl == 1)
        return new Vertex(v->sum+1);
    int tm = (tl + tr) / 2;
    if (pos < tm)
        return new Vertex(update(v->l, tl, tm, pos), v->r);
    else
        return new Vertex(v->l, update(v->r, tm, tr, pos));
}

int find_kth(Vertex* vl, Vertex *vr, int tl, int tr, int k) {
    if (tr - tl == 1)
        return tl;
    int tm = (tl + tr) / 2, left_count = vr->l->sum - vl->l->sum;
    if (left_count >= k)
        return find_kth(vl->l, vr->l, tl, tm, k);
    return find_kth(vl->r, vr->r, tm, tr, k-left_count);
}

正如前面已经说过，需要保存最初线段树的根节点，以及每次更新之后得到的所有根节点。

下面的代码为元素范围为 [0, MAX_VALUE] 的 vector a 构建可持久化线段树：

int tl = 0, tr = MAX_VALUE + 1;
std::vector<Vertex*> roots;
roots.push_back(build(tl, tr));
for (int i = 0; i < a.size(); i++) {
    roots.push_back(update(roots.back(), tl, tr, a[i]));
}
// find the 5th smallest number from the subarray [a[2], a[3], ..., a[19]]
int result = find_kth(roots[2], roots[20], tl, tr, 5);

最后解决数组元素取值范围的限制。

实际上，可以通过**下标压缩（index compression）**把任意数组转换成满足这种限制的数组。

把：

数组中的最小元素映射为 $0$ ；
第二小元素映射为 $1$ ；
依此类推。

很容易建立查询表，例如使用 map，使得：

一个值可以转换成它的压缩下标；
一个压缩下标也可以转换回原值。

这些操作都可以在

O(\log n)

时间内完成。

动态线段树

之所以称为“动态”线段树，是因为它的形状是动态的，并且节点通常也是动态分配的。

它也被称为：

隐式线段树（Implicit Segment Tree）；
稀疏线段树（Sparse Segment Tree）。

前面讨论的情况中，我们都能够提前把完整的初始线段树构建出来。

但是，如果初始值全部是某个默认值，同时值域非常大，以至于无法事先完整构建整棵线段树，该怎么办？

可以通过懒惰地、逐步地创建线段树解决这个问题。

开始时，只创建根节点。

只有真正需要某个节点时，才创建它。

这种情况下使用基于指针的实现方式：

在进入一个节点的子节点之前，先检查这些子节点是否已经创建。

如果没有，则创建它们。

每个查询的复杂度仍然只有

O(\log n),

对于大多数使用场景来说已经足够小。

例如：

\log_2 10^9\approx30.

下面的实现支持两种查询：

给某个位置加上一个值（初始所有位置的值均为 $0$ ）；
求某个区间中所有值的总和。

Vertex(0, n) 将作为隐式线段树的根节点。

struct Vertex {
    int left, right;
    int sum = 0;
    Vertex *left_child = nullptr, *right_child = nullptr;

    Vertex(int lb, int rb) {
        left = lb;
        right = rb;
    }

    void extend() {
        if (!left_child && left + 1 < right) {
            int t = (left + right) / 2;
            left_child = new Vertex(left, t);
            right_child = new Vertex(t, right);
        }
    }

    void add(int k, int x) {
        extend();
        sum += x;
        if (left_child) {
            if (k < left_child->right)
                left_child->add(k, x);
            else
                right_child->add(k, x);
        }
    }

    int get_sum(int lq, int rq) {
        if (lq <= left && right <= rq)
            return sum;
        if (max(left, lq) >= min(right, rq))
            return 0;
        extend();
        return left_child->get_sum(lq, rq) + right_child->get_sum(lq, rq);
    }
};

显然，这个思想还可以沿很多不同方向继续扩展。

例如，可以通过懒惰传播加入对区间修改的支持。

练习题

SPOJ - KQUERY
[可持久化线段树 / Merge Sort Tree]
Codeforces - Xenia and Bit Operations
UVA 11402 - Ahoy, Pirates!
SPOJ - GSS3
Codeforces - Sereja And Brackets
Codeforces - Distinct Characters Queries
Codeforces - Knight Tournament
[适合初学者]
Codeforces - Ant colony
Codeforces - Drazil and Park
Codeforces - Circular RMQ
Codeforces - Lucky Array
Codeforces - The Child and Sequence
Codeforces - DZY Loves Fibonacci Numbers
[Lazy propagation]
Codeforces - Alphabet Permutations
Codeforces - Eyes Closed
Codeforces - Kefa and Watch
Codeforces - A Simple Task
Codeforces - SUM and REPLACE
Codeforces - XOR on Segment
[Lazy propagation]
Codeforces - Please, another Queries on Array?
[Lazy propagation]
COCI - Deda
[最后一个小于等于 x 的元素 / 二分查找]
Codeforces - The Untended Antiquity
[二维]
CSES - Hotel Queries
CSES - Polynomial Queries
CSES - Range Updates and Sums

求区间第 kkk 小

动态线段树

练习题

求区间第 $k$ 小