可持久化线段树是支持访问历史版本的线段树

内存空间

初始建树需开 \(2n-1\) 个节点，\(n\)次修改，每次修改最多开 \(logn+1\) 个节点，所以节点总数为 \(2n-1+n(logn+1)\)

动态开点

不再用 \(u<<1\)和\(u<<1|1\) 记录左儿子和右儿子，而是使用 \(ls[u]\) 和 \(rs[u]\) 来表示，每个版本的根节点用 \(root\) 数组来维护

例题

Luogu P3919 【模板】可持久化线段树 1（可持久化数组）

有了可持久化数组，便可以实现很多衍生的可持久化功能

题目描述

如题，你需要维护这样的一个长度为 \(N\) 的数组，支持如下几种操作

  1. 在某个历史版本上修改某一个位置上的值
  2. 访问某个历史版本上的某一位置的值

此外，每进行一次操作(对于操作2，即为生成一个完全一样的版本，不作任何改动)，就会生成一个新的版本。版本编号即为当前操作的编号(从1开始编号，版本0表示初始状态数组)

输入格式

输入的第一行包含两个正整数 \(N,M\)，分别表示数组的长度和操作的个数。

第二行包含 \(N\) 个整数，依次为初始状态下数组各位的值(依次为 \(a_i,1<i< N\))。

接下来 \(M\) 行每行包含3或4个整数，代表两种操作之一(\(i\) 为基于的历史版本号):

  1. 对于操作 \(1\)，格式为 \(v_i\ 1\ loc_i\ value\)，即为在版本 \(v_i\) 的基础上，将 \(a_{loa_i}\) 修改为 \(value_i\)。
  2. 对于操作 \(2\)，格式为 \(v_i\ 2\ loc_i\)，即访问版本 \(v_i\) 中的 \(a_{loa_i}\) 的值，注意:生成一样版本的对象应为 \(v_i\)。

输出格式

输出包含若干行，依次为每个操作 \(2\) 的结果。

数据范围

\(1 \le N,\ M \le 10^6,\ 1 \le loc_i \le N,\ 0 \le v_i \le i,\ -10^9 \le a_i,\ value_i \le 10^9\)

code:

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
#include <bits/stdc++.h>

using namespace std;

const int N = 1000010;

int n, m;
int a[N];
int root[N], tot;
int ls[N * 25], rs[N * 25], val[N * 25];

void build(int &u, int l, int r)
{
    u = ++tot;
    if (l == r) val[u] = a[l];
    else
    {
        int mid = l + r >> 1;
        build(ls[u], l, mid);
        build(rs[u], mid + 1, r);
    }
}

void modify(int &u, int v, int l, int r, int p, int x)
{
    u = ++tot;
    ls[u] = ls[v], rs[u] = rs[v], val[u] = val[v];
    if (l == r) val[u] = x;
    else
    {
        int mid = l + r >> 1;
        if (p <= mid) modify(ls[u], ls[v], l, mid, p, x);
        else modify(rs[u], rs[v], mid + 1, r, p, x);
    }
}

int query(int u, int l, int r, int p)
{
    if (l == r) return val[u];
    int mid = l + r >> 1;
    if (p <= mid) return query(ls[u], l, mid, p);
    else return query(rs[u], mid + 1, r, p);
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

    build(root[0], 1, n);

    for (int i = 1; i <= m; i++)
    {
        int ver, st, p, x;
        scanf("%d%d%d", &ver, &st, &p);
        if (st == 1) 
        {
            scanf("%d", &x);
            modify(root[i], root[ver], 1, n, p, x);
        }
        else 
        {
            root[i] = root[ver];
            printf("%d\n", query(root[i], 1, n, p));
        }
    }

    return 0;
}

Luogu【模板】可持久化线段树 2

这是个非常经典的可持久化权值线段树入门题——静态区间第 \(k\) 小

题目描述

如题，给定 \(n\) 个整数构成的序列 \(a\)，将对于指定的闭区间 \([l,r]\) 查询其区间内的第 \(k\) 小值。

输入格式

第一行包含两个整数，分别表示序列的长度 \(n\)，和查询的个数 \(m\)。

第二行包含 \(n\) 个整数，第i个整数表示序列的第 \(i\) 个元素 \(a_i\)。

接下来 \(m\) 行每行包含三个整数 \(l,r,k\)，表示査询区间 \([l,r]\) 内的第 \(k\) 小值。

输出格式

对于每次询问，输出一行一个整数表示答案。

数据范围

\(1 < n, m < 2 \times 10^5, \ 0 \leq a < 10^9, \ 1 \leq l \leq r \leq n, \ 1 \leq k \leq r - l + 1\)

code:

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
#include <bits/stdc++.h>

using namespace std;

const int N = 200010;

int n, m;
int a[N], b[N];
int root[N], tot;
int ls[N * 25], rs[N * 25], sum[N * 25];

void modify(int &u, int v, int l, int r, int p)
{
    u = ++tot;
    ls[u] = ls[v], rs[u] = rs[v], sum[u] = sum[v] + 1;
    if (l == r) return;
    int mid = l + r >> 1;
    if (p <= mid) modify(ls[u], ls[v], l, mid, p);
    else modify(rs[u], rs[v], mid + 1, r, p);
}

int query(int u, int v, int l, int r, int k)
{
    if (l == r) return l;
    int s = sum[ls[u]] - sum[ls[v]];
    int mid = l + r >> 1;
    if (k <= s) return query(ls[u], ls[v], l, mid, k);
    else return query(rs[u], rs[v], mid + 1, r, k - s);
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int i = 1; i <= n; i++) b[i] = a[i];
    sort(b + 1, b + 1 + n);

    int bn = unique(b + 1, b + 1 + n) - b - 1;
    for (int i = 1; i <= n; i++)
    {
        int l = 1, r = bn;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (b[mid] < a[i]) l = mid + 1;
            else r = mid;
        }
        modify(root[i], root[i - 1], 1, bn, l);
    }

    while (m--)
    {
        int l, r, k;
        cin >> l >> r >> k;
        int p = query(root[r], root[l - 1], 1, bn, k);
        cout << b[p] << endl;
    }

    return 0;
}