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

发表于 分类于 ，

咕咕咕

什么是主席树:

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

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

大概就长这个样子:

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;
}