【数据结构】函数式（可持久化）线段树

引言

函数式线段树也叫主席树，恩，原因嘛，不知道！

函数式线段树非常之吊，可以支持历史版本的查询。

关键是写起来很简单！

函数式线段树

核心思想

函数式线段树本质上很多棵线段树，即有很多的根节点。

这些线段树之间，通过共用一些子树以节省空间开销和时间开销。

更具体的说，在现在的基础上每增加一棵树的开销是logn。

函数式线段树需要满足一定的条件才能使用：维护的数据必须具有区间可减性。

更详细的讲解请看：http://www.cnblogs.com/zyf0163/p/4749042.html

模板

模板同样看应用吧～

应用

HDU2665，区间第k大。

可以用划分树写，但是，你们懂得，太麻烦了，而主席树完美解决这个问题。

将数组的n个前缀看做n棵线段树，将数字区间作为线段树维护的区间范围～

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
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <algorithm>

using namespace std;

#define N 100010
#define LN 17

int cas;
int n, m;
int a[N], b[N], rt[N];
int uni_num;
int sum[N * LN + 4 * N], ls[N * LN + 4 * N], rs[N * LN + 4 * N];
int cnt;

int newnode(int l, int r, int s) {
    cnt++;
    ls[cnt] = l;
    rs[cnt] = r;
    sum[cnt] = s;
    return cnt;
}

void build(int l, int r, int &x) {
    x = newnode(0, 0, 0);
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(l, mid, ls[x]);
    build(mid + 1, r, rs[x]);
}

void update(int l, int r, int &x, int px, int val) {
    x = newnode(ls[px], rs[px], sum[px] + 1);
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (val > mid ) update(mid + 1, r, rs[x], rs[px], val);
    else update(l, mid, ls[x], ls[px], val);
}

int query(int l, int r, int y, int x, int k) {
    if (l == r) return l;
    int mid = (l + r) >> 1;
    int dt = sum[ls[y]] - sum[ls[x]];
    if (dt < k) return query(mid + 1, r, rs[y], rs[x], k - dt);
    return query(l, mid, ls[y], ls[x], k);
}

int main() {
    scanf("%d", &cas);
    while (cas--) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            b[i] = a[i];
        }
        // 离散化
        sort(b + 1, b + 1 + n);
        uni_num = unique(b + 1, b + 1 + n) - b - 1;
        for (int i = 1; i <= n; i++)
            a[i] = lower_bound(b + 1, b + 1 + uni_num, a[i]) - b;
        // 建立可持久化线段树
        cnt = 0;
        build(1, uni_num, rt[0]);
        for (int i = 1; i <= n; i++)
            update(1, uni_num, rt[i], rt[i - 1], a[i]);
        int s, t, k;
        while (m--) {
            scanf("%d%d%d", &s, &t, &k);
            printf("%d\n", b[query(1, uni_num, rt[t], rt[s - 1], k)]);
        }
    }
    return 0;
}