静态区间第 K 大问题

发表于 更新于 分类于 阅读次数：

静态区间第K大问题是主席树的经典应用，这里参考洛谷3834（不带修改的主席树）。

本文是博主的学习笔记，不是教程，如读者希望寻找教程，请移步其他博客。

原理

主席树是一种值域线段树，即每个节点 \([x_l,x_r]\) 存的是当前出现的区间 \([l,r]\) 中的数的个数。一般情况下，值域我们先要进行离散化，因为它往往范围很大，那么这里的 \(x_i\) 就是 \(i\) 离散化之后的值。那么主席树中的叶子节点 \([x_u, x_u]\) 就存的是当前阶段 \(u\) 出现的个数。主席树是一种可持久化线段树。之所以说它可持久化是因为它可以保留线段树中每个节点的历史版本，这也是解决静态区间第 K 大问题的一个关键。当我们试图做单点修改的时候，影响到的是从这个点向上走到根节点的这条链，也就是说如果我们要保存这个版本的线段树，只需要新建一条链出来，让这条链上的没有动的左子树指针和右子树指针依旧指向原来的地方，保存当前状态新的根节点。解决静态区间第K大问题的方法是，将所有的 \([1,i]\) 的子区间（一共 \(n\) 个）看成是 \(n\) 个阶段，然后对于这 \(n\) 个阶段去更新线段树，每次会出现一个新的根节点。那么我们在询问区间\([l,r]\)的区间第K大的时候，实际上就是拿\(r\)状态的线段树和 \(l-1\) 状态的线段树相减，得到 \([l,r]\) 之间的值域中每个值出现的次数。于传统线段树相比，主席树的实现需要动态开点，而传统线段树只需要利用堆式存储即可。传统线段树一般开 \(4n\) 倍的空间（当然实际上可以更少），而主席树考虑到对于 \(n\) 个点就有 \(n\) 个阶段，对于第 \(0\) 阶段，需要 \(4n\) 的空间建立传统线段树，对于阶段 \(i \in [1,n]\)，每次需要一条链的空间，即线段树的层数 \(\log_2 n\)，也就是我们需要 \(n \log_2 n + 4 n\) 的空间。

实现

建树

建树操作只有在第 \(0\) 状态的时候才会使用到，这个时候值域里没有任何点，那么当前每个点的值都为 0，然后动态开点建一颗传统线段树即可。

更新

从 \(i\) 状态到 \(i+1\) 状态需要更新线段树（意义是把 \(a_{i+1}\) 添加到值域当中），那么我们在更新后面状态的时候，会把前面的状态传参传到update函数中，一开始先复制前状态，然后根据这个值和当前枚举的值域中点的大小关系修改。

查询

对于区间 \([l,r]\)，查询状态 \(l-1\) 和 \(r\)，然后相减，这里利用了前缀和思想。如果说左子树相减的结果（状态区间 \([l,r]\) 中新增的点在每个区间节点的个数）大于等于 K，那么说明第 K 大在左边找，否则如果当前左子树大小为 \(s\)，则在右边找第 \(k-s\) 大的数，这里的查询结果是离散化完之后第 K 大数的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int MAX_N = 200000 + 5;
int n, m, a[MAX_N], b[MAX_N], tot, root[MAX_N];
int cnt, tree[MAX_N * 40], lson[MAX_N * 40], rson[MAX_N * 40];

int build(int l, int r) {
    int o = ++cnt;
    tree[o] = 0;
    if (l < r) {
        int mid = (l + r) >> 1;
        lson[o] = build(l, mid);
        rson[o] = build(mid + 1, r);
    }
    return o;
}

int update(int pre, int l, int r, int pos) {
    int o = ++cnt;
    lson[o] = lson[pre]; rson[o] = rson[pre]; tree[o] = tree[pre] + 1;
    if (l < r) {
        int mid = (l + r) >> 1;
        if (pos <= mid) lson[o] = update(lson[pre], l, mid, pos);
        else rson[o] = update(rson[pre], mid + 1, r, pos);
    }
    return o;
}

int query(int bef, int aft, int l, int r, int k) {
    if (l == r) return l;
    int x = tree[lson[aft]] - tree[lson[bef]];
    int mid = (l + r) >> 1;
    if (x >= k) return query(lson[bef], lson[aft], l, mid, k);
    else return query(rson[bef], rson[aft], mid + 1, r, k - x);
}

inline int getId(int u) {
    return lower_bound(b + 1, b + tot + 1, u) - b;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", a + i), b[i] = a[i];
    sort(b + 1, b + n + 1);
    tot = unique(b + 1, b + n + 1) - b - 1;
    root[0] = build(1, tot);
    for (int i = 1; i <= n; ++i) {
        root[i] = update(root[i - 1], 1, tot, getId(a[i]));
    }
    
    int l, r, k;
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d%d", &l, &r, &k);
        printf("%d\n", b[query(root[l - 1], root[r], 1, tot, k)]);
    }

    return 0;
}