主席树-可持久化线段树

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

主席树又叫做可持久化线段树，就是说主席树可以直接利用历史已经建好的线段树节点再扩展生成新的线段树，

经典问题是解决区间第K大数的询问问题。如果直接暴力肯定是过不了的。

Kth number

又是一道不读discuss永远过不了的题，不要被题意误解，这道题是求区间第K小的数字。

一篇比较好的主席树讲解博客：主席树学习

我就简单说几点我一开始也不太理解的地方。

1.我们需要对一开始输入的a数组离散化，得到b数组，然后a数组存的是a数组原先的值在b数组里的位置。然后我们更新的时候，只是根据这个位置更新。

2.我们在查询的时候，也只是查询的位置，从query中的 return l，就可以看出。

3.一开始的时候我们要建立一颗空的rt[0]线段树，这个过程中注意那个引用符号，这个很重要，会使得ls[],rs[]不断更新，ls[]和rs[]存的是什么呢，ls[i]存的是以i为根节点的左儿子的索引。也就是说通过这个我们就能不断往下遍历各个节点了。

4.在更新的时候，我们根据ls[]，rs[]不断往下遍历，虽然ls[o] 开始被赋值 ls[last],但是往下找到递归的区间的时候，它就会被更新了，这也是引用的作用。

5.重要的就是Update函数，他真正的体现了主席树是如何利用以往的线段树的，只有这样才不会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

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <string>
#include <set>
#include <queue>

using namespace std;
const int N = 200005;
const int maxn = 2500005;
int rt[maxn], ls[maxn], rs[maxn],a[N], b[N],sum[maxn];

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

void update(int &o, int l, int r, int last, int k)
{
    o = ++tot;
    ls[o] = ls[last];
    rs[o] = rs[last];
    sum[o] = sum[last] + 1;
    if(l == r) return;
    int mid = (l + r) >> 1;
    if(k <= mid) update(ls[o], l , mid, ls[last], k);
    else  update(rs[o], mid + 1, r, rs[last], k);
}

int query(int ss, int tt, int l, int r, int k)
{
    if(l == r) return l;
    int cnt = sum[ls[tt]] - sum[ls[ss]];
    int mid = (l + r) >> 1;
    if(k <= cnt) return query(ls[ss],ls[tt],l, mid, k);
    else return query(rs[ss],rs[tt],mid + 1, r, k - cnt);
}
int main()
{
    int t,n,Q,ll,rr,k;

        tot = 0;
        scanf("%d %d",&n,&Q);
        for(int i = 1; i <= n; ++i)
        {
            scanf("%d",&a[i]);
        }
        memcpy(b,a,sizeof(a));
        sort(b + 1, b + n + 1);
        int sz = unique(b + 1, b + n + 1) - (b + 1);
        build(rt[0],1,sz);
        for(int i = 1; i <= n; ++i)
        {
            a[i] = lower_bound(b + 1, b + sz + 1, a[i]) - b;
        }
        for(int i = 1; i <= n; ++i)
        {
            update(rt[i],1,sz,rt[i - 1], a[i]);
        }
        while(Q--)
        {
            scanf("%d %d %d",&ll,&rr,&k);
            int ans = query(rt[ll - 1], rt[rr], 1 ,sz, k);
            cout << b[ans] << '\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
#include <cstdio>
#include <map>
#include <algorithm>
#include <iostream>
#include <stdio.h>
#include <string>
using namespace std;
const int N = 3e4 + 5;

struct node{
    int ls, rs, sum;
}tree[4000005];
const int maxn = 300005;
int a[maxn], b[maxn], rt[maxn];
int tot ;
void build(int &o, int l, int r)
{
    o = ++tot;
    tree[o].sum = 0;
    if(l == r) return;
    int mid = (l + r) >> 1;
    build(tree[o].ls, l, mid);
    build(tree[o].rs, mid + 1, r);
}

void update(int &o, int last, int pos, int l, int r)
{
     o = ++tot;
     tree[o].ls = tree[last].ls;
     tree[o].rs = tree[last].rs;
     tree[o].sum = tree[last].sum + 1;
     if(l == r) return;
     int mid = (l + r) >> 1;
     if(pos <= mid)  update(tree[o].ls, tree[last].ls, pos, l, mid);
     else update(tree[o].rs, tree[last].rs, pos, mid + 1, r);
}

int query(int ss, int tt, int l, int r, int k)
{
    if(l == r) return l;
    int num = tree[tree[tt].ls].sum - tree[tree[ss].ls].sum;
    int mid = (l + r) >> 1;
    if(k <= num)  return query(tree[ss].ls, tree[tt].ls, l, mid, k);
    else  return query(tree[ss].rs, tree[tt].rs, mid + 1, r, k - num);
}
int main()
{
    int n,Q,l,r,k;
    scanf("%d %d",&n,&Q);
    tot = 0;
    for(int i = 1; i <= n; ++i)
    {
        scanf("%d",&a[i]);
        b[i] = a[i];
    }
    sort(b + 1,b + n + 1);
    int sz = unique(b + 1, b + n + 1) - (b + 1);
    build(rt[0], 1, sz);
    for(int i = 1; i <= n; ++i)
    {
        a[i] = lower_bound(b + 1, b + sz + 1, a[i]) - b;
    }
    for(int  i = 1; i <= n; ++i)
    {
        update(rt[i], rt[i - 1], a[i], 1, sz);
    }
    for(int i = 1 ; i <= Q; ++i)
    {
        scanf("%d %d %d",&l,&r,&k);
        printf("%d\n",b[query(rt[l - 1], rt[r], 1 , sz ,k)]);
    }
}