• 参考链接

OI-wiki

Wikipedia

主席树-孤独·粲泽

主席树

  传统意义就是可持久化线段树，持久化即可以记录每一次修改的内容，为什么叫主席树呢，最早用这种方法的人黄嘉泰(HJT) 首字母和一位主席相同。

静态区间第 k 小

  以 POJ2104 K-th Number 为例

题意：给定一个长度为 \(n(1\le n\le10^5)\) 的序列，和 \(m(1\le m\le5000)\) 个询问：\(l_i,r_i,k_i\)，表示求 \(a[l_i],a[l_i+1],\cdots,a[r_i]\) 中第 \(k_i\) 小的数是多少。

  建立一颗权值线段树，维护序列 \(a\) 中有多少数在值域区间 \([L,R]\) 内(记为 \(cnt_{L,R}\))，只需比较 \(cnt_{L,mid}\) 与 k 的关系，即可确定 a 的第 k 小数 \(\le mid\) 还是 \(>mid\)，从而进入左右子树之一。

  将序列 \(a\) 离散化，\(a[i]\) 的值为 \(H[a[i]]\in[1,t]\)，在 \([1,t]\) 建立可持久化线段树，每个结点一个值 \(cnt\) 表示值域区间 \([L,R]\) 一共插入多少数。对每个 \(a[i]\)，在可持久化线段树上进行对 \(H[a[i]]\) 的单点修改。

  可持久化线段树中“以 \(root[i]\) 为根的线段树”的值域区间 \([L,R]\) 保存了 \(a\) 的前 \(i\) 个数有多少个落在值域 \([L,R]\) 内。

  对每个询问 \(l_i,r_i,k_i\)，注意到：以 \(root[l_i]\) 和 \(root[r_i]\) 为根的两棵线段树对值域的划分是相同的，即除了 \(cnt\) 值不同外两棵线段树的内部构造和每个结点代表的值域区间完全对应。我们有：\(root[r_i]\) 的值域区间 \([L,R]\) 的 \(cnt\) 值减去 \(root[l_i-1]\) 的值域区间 \([L,R]\) 的 \(cnt\) 值就等于 \(a[l_i\sim r_i]\) 中有多少个数落在值域 \([L,R]\) 内。

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
63
64
65
66
67
68
69
70
71
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 1e5 + 5;

struct Node {
    int ls, rs, cnt;
}tree[N*20];

int n, m, tot;
int a[N], b[N], root[N];

int build(int l, int r) {
    int p = ++tot; tree[p].cnt = 0;
    if (l == r) return p;
    int mid = (l + r) >> 1;
    tree[p].ls = build(l, mid);
    tree[p].rs = build(mid + 1, r);
    return p;
}

int update(int pre, int l, int r, int x, int v) {
    int p = ++tot; tree[p] = tree[pre];
    if (l == r) {
        tree[p].cnt += v;
        return p;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) tree[p].ls = update(tree[pre].ls, l, mid, x, v);
    else tree[p].rs = update(tree[pre].rs, mid + 1, r, x, v);
    tree[p].cnt = tree[tree[p].ls].cnt + tree[tree[p].rs].cnt;
    return p;
}

int query(int p, int q, int l, int r, int k) {
    if (l == r) return l;
    int mid = (l + r) >> 1;
    int lsnt = tree[tree[p].ls].cnt - tree[tree[q].ls].cnt;
    if (k <= lsnt) return query(tree[p].ls, tree[q].ls, l, mid, k);
    else return query(tree[p].rs, tree[q].rs, mid + 1, r, k - lsnt);
}

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);
    int t = unique(b + 1, b + n + 1) - (b + 1);
    root[0] = build(1, t);
    for (int i = 1; i <= n; ++i) {
        int x = lower_bound(b + 1, b + t + 1, a[i]) - b;
        root[i] = update(root[i-1], 1, t, x, 1);
    }
    int l, r, k;
    while (m--) {
        scanf("%d%d%d", &l, &r, &k);
        int ans = query(root[r], root[l-1], 1, t, k);
        printf("%d\n", b[ans]);
    }
    return 0;
}

动态区间第 k 小

以 洛谷 P2617 Dynamic Rankings 为例。

  用树状数组维护前缀和，以 \(root[i]\) 为根的线段树表示 \([i-lowbit(i)+1, i]\) 值域区间建成的线段树。

  查询时，\(L\) 数组存储拼出 \([1,l-1]\) 的所有点，\(R\) 数组存储拼出 \([1,r]\) 的所有点。需要注意的是容易 MLE。

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;

#define debug(x) cout << #x << " is " << x << endl
#define inc(i, a, b) for (int i = a; i <= b; ++i)
typedef long long ll;
const int INF = 0x3f3f3f3f, N = 1e5 + 5;

struct Op {
    int l, r, k;
}op[N];

struct Node {
    int ls, rs, cnt;
}tree[N*400]; // nlog^2(n) 大小

int n, m, tot, t, cl, cr;
int a[N], b[N<<1], root[N];
int L[20], R[20];

int build(int l, int r) {
    int p = ++tot; tree[p].cnt = 0;
    if (l == r) return p;
    int mid = (l + r) >> 1;
    tree[p].ls = build(l, mid);
    tree[p].rs = build(mid + 1, r);
    return p;
}

int update(int pre, int l, int r, int x, int v) {
    int p = ++tot; tree[p] = tree[pre];
    if (l == r) {
        tree[p].cnt += v;
        return p;
    }
    int mid = (l + r) >> 1;
    if (x <= mid) tree[p].ls = update(tree[pre].ls, l, mid, x, v);
    else tree[p].rs = update(tree[pre].rs, mid + 1, r, x, v);
    tree[p].cnt = tree[tree[p].ls].cnt + tree[tree[p].rs].cnt;
    return p;
}

int query(int l, int r, int k) {
    if (l == r) return l;
    int mid = (l + r) >> 1, sum = 0;
    for (int i = 1; i <= cl; ++i)
        sum -= tree[tree[L[i]].ls].cnt;
    for (int i = 1; i <= cr; ++i)
        sum += tree[tree[R[i]].ls].cnt;
    if (k <= sum) {
        for (int i = 1; i <= cl; ++i)
            L[i] = tree[L[i]].ls;
        for (int i = 1; i <= cr; ++i)
            R[i] = tree[R[i]].ls;
        return query(l, mid, k);
    }
    else {
        for (int i = 1; i <= cl; ++i)
            L[i] = tree[L[i]].rs;
        for (int i = 1; i <= cr; ++i)
            R[i] = tree[R[i]].rs;
        return query(mid + 1, r, k - sum);
    }
}

int lowbit(int x) { return x & -x; }

void add(int x, int v) { // [1,i] 的线段树值域为 a[x] 的次数 += v
    int id = lower_bound(b + 1, b + t + 1, a[x]) - b;
    for (; x <= n; x += lowbit(x))
        root[x] = update(root[x], 1, t, id, v);
}

int main() 
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        b[++t] = a[i];
    }
    char str[2];
    for (int i = 1; i <= m; ++i) {
        scanf("%s", str);
        if (str[0] == 'Q') scanf("%d%d%d", &op[i].l, &op[i].r, &op[i].k);
        else if (str[0] == 'C') {
            scanf("%d%d", &op[i].l, &op[i].r);
            b[++t] = op[i].r; op[i].k = 0;
        }
    }
    sort(b + 1, b + t + 1);
    t = unique(b + 1, b + t + 1) - (b + 1);
    root[0] = build(1, t);
    for (int i = 1; i <= n; ++i) add(i, 1);
    for (int i = 1; i <= m; ++i) {
        if (op[i].k) {
            cl = cr = 0;
            for (int j = op[i].l - 1; j; j -= lowbit(j))
                L[++cl] = root[j];
            for (int j = op[i].r; j; j -= lowbit(j))
                R[++cr] = root[j];
            int ans = query(1, t, op[i].k);
            printf("%d\n", b[ans]);
        }
        else {
            add(op[i].l, -1);
            a[op[i].l] = op[i].r;
            add(op[i].l, 1);
        }
    }
    return 0;
}

训练题

  打算单独开一个。