主席树(可持久化线段树)

发表于 | 分类于 ，

咕咕咕

什么是主席树:

主席树又叫可持久化线段树. 顾名思义, 是一个以线段树为基础的可持久化数据结构.

主要是通过复用结点, 在修改的同时保留之前的结构.

大概就长这个样子:

ChairmanTree

作用:

主席树最常见的用法就是求静态区间的第k小. 即给定一个长度为$n$的序列$a$, 求区间$[l,r]$对应序列${a_l,a_{l+1},…,a_r}$中第k小(kth)的数.

要解决这个问题, 首先引出权值(值域)线段树的概念.

和值域树状数组一样(例题), 值域线段树也是将数据离散化后用线段树维护每个数的出现个数.

在解决原问题之前, 先解决几个个弱化的问题:

l=1,r=n:

方法很多, 使用值域线段树的方法和上面给出的例题有点相似, 只是将在树状数组上的二分查找变为了在线段树上的查找(类似于名次树).

l=1:

受到上一个问题的启发, 我们可以直接建立n个值域线段树. 对于不同的$r$在相应的线段树查找即可.

可以注意到, $[1,i]$的值域线段树与$[1,i+1]$的值域线段树之间只进行了一个点修改操作. 可以通过复用结点将n个线段树变为一个可持久化线段树, 从而起到节省空间的作用.

原问题:

注意到n个”分线段树”的结构相同, 意味着这些线段树是可减的. 可以利用前缀和思想, 将原问题转化为两个$l=1$的弱化问题. 即将$[1,r]$的线段树减去$[1,l-1]$的线段树, 便可得到$[l,r]$的值域线段树. 问题便迎刃而解.

预处理时间复杂度$O(nlogn)$, 每次查询时间复杂度$O(logn)$, 空间复杂度$O(nlogn)$.

代码:
(luogu3834)主席树模板

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
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
const int Mn(200500);

void qread(int &x)	//快读
{
    x = 0;
    int o(1);
    char c=getchar();
    while(!isdigit(c))
    {
        if(c=='-') o=-1;
        c = getchar();
    }
    while(isdigit(c))
    {
        x = x*10 + c-'0';
        c = getchar();
    }
    x *= o;
}

int a[Mn],vals[Mn];	//原数组与离散化数组

struct CTree_node	//主席树结点, 采用链式存储
{
    int l,r,v;	//左边界, 右边界, 结点值
    CTree_node *ls,*rs;	//左儿子, 右儿子
}*ver[Mn],*null;	//修改"版本"(version), 自定义null(方便处理)

void init_null()	//初始化null
{
    null = new CTree_node();
    null->ls = null->rs = null;
}
void build(int l,int r,CTree_node* &p)	//建第一棵线段树
{
    p = new CTree_node();
    p->l = l; p->r = r;
    if(l==r)
    {
        p->ls = p->rs = null;
        return;
    }
    int mid((l+r)>>1);
    build(l,mid,p->ls);
    build(mid+1,r,p->rs);
}
void modify(CTree_node* last_ver,CTree_node* &mod_ver,int p)	//单点修改(上个版本, 修改后的版本)
{
    mod_ver = new CTree_node();
    *mod_ver = *last_ver;
    ++(mod_ver->v);	//在"路径"上计数
    if(mod_ver->l==mod_ver->r)
        return;
    if(mod_ver->ls->r >= p)
        modify(last_ver->ls,mod_ver->ls,p);
    else
        modify(last_ver->rs,mod_ver->rs,p);
}
int query(CTree_node* ltree,CTree_node* rtree,int k)	//查找
{
    int lv = rtree->ls->v - ltree->ls->v;	//左儿子的值(判断查找区间的关键)
    if(ltree->l==ltree->r)	return vals[ltree->l];
    if(k<=lv)	return query(ltree->ls,rtree->ls,k);
    else		return query(ltree->rs,rtree->rs,k-lv);	//注意在右子树查找时要减去左子树的值
}

int main()
{
    init_null();
    int n,m;
    qread(n), qread(m);
    for(int i(1);i<=n;++i)
    {
        qread(a[i]);
        vals[i] = a[i];
    }
    sort(vals+1,vals+n+1);	//排序
    int valn = unique(vals+1,vals+n+1)-vals-1;	//离散化(unique)并找到值的个数
    build(1,valn,ver[0]);	//建第一棵树
    for(int i(1);i<=n;++i)
    {
        int apos = lower_bound(vals+1,vals+valn+1,a[i])-vals;	//二分查找a[i]在离散化数组的位置
        modify(ver[i-1],ver[i],apos);	//修改(建树)
    }
    while(m--)
    {
        int l,r,k;
        qread(l), qread(r), qread(k);
        printf("%d\n",query(ver[l-1],ver[r],k));	//查询
    }
    return 0;
}