引入

来源：主席树的学名是可持久化权值线段树，为什么被叫做主席树是因为发明者叫做黄嘉泰（ HJT ），恰巧是我们国家某个主席的缩写

主席树和可持久化线段树是否是同一个数据结构存在一些争论，不过可以肯定的是函数式线段树是指使用函数式编程思想的线段树。在函数式编程思想中，将计算机运算视为数学函数，并避免可改变的状态或变量。不难发现，函数式线段树是 完全可持久化 的

适用范围：动态查找区间第 k 小的问题

约定：本文后面的 kth 代表区间内第 k 小

静态求区间 kth

博客参考主要讲的是静态主席树不带修改的

前缀知识

线段树，权值线段树，前缀和思想等

解决方法

  • 暴力：对于每一个询问，排个序就行了，时间复杂度 O(nmlogn)
  • 莫队+树状数组：树状数组可以求给定区间 kth，使用二分+树状数组，具体不展开，但是多个区间的话，需要不断地进行树状数组的 add/del 操作，那么使用莫队来优化区间端点的移动问题，时间复杂度 O((n+m)√nlogn)，莫队复杂度*树状数组复杂度
  • 莫队+平衡树：把树状数组的部分替换成二叉查找树，用 splay 的一部分操作，需要用到 kth 操作，不用翻转标记什么的，时间复杂度和上面相同

三种方法暴力时间复杂度太高可以在线操作，后面两种方法还行但是只能离线操作，一种可行的方案就是使用时间复杂度为 O(logn) 的主席树

思想优化

结构

对于给出的一列数，将每个位置都建一棵权值线段树——维护 1~i 这些数每个不同的数的出现次数（权值线段树以值域作为区间）

如此建立 n 棵上述的线段树，第 i 棵线段树代表 1~i 这个区间。根节点就是总区间 1~i ，线段树的子区间记录序列 A[1~i] 中处于子区间范围内数的总个数（权值）

一列数 n=6 ，分别为 1 3 2 3 6 1 ，以第四棵线段树为例

因为是同一个问题， n 棵线段树的形状是一摸一样的，只有节点的权值不一样所以这样的两棵线段树是可以相加减的（两棵线段树的相加减就是每个节点的权值相加减）

本质

第x棵线段树代表的区间是 [1,x] ，第 y 棵线段树代表的区间是 [1,y] 两棵线段树一减，设 x>y,[1,x]−[1,y]=[y+1,x][1,x]-[1,y]=[y+1,x][1,x]−[1,y]=[y+1,x] 所以这两棵线段树相减可以产生一个新的区间对应的线段树！

核心思想：到这里不难发现主席树利用的就是前缀和的思想

空间问题

现在还有一个严峻的问题就是 n 棵线段树的空间太大了需要优化，方法就是在建树的过程中减少重复节点

假设现在已经有一棵线段树，那么在给序列下一个点建立线段树的时候对于其儿子节点的如果权值有变化那么就新建一个节点，否则就连到原来节点上

一列数n=6 ，分别为 1 3 2 3 6 1 ，以建立前三个点的线段树为例

  • 序列 [1,1] 的线段树在空树的基础上建立
  • 序列 [1,2] 的线段树在 [1,1] 的线段树的基础上建立
  • 序列 [1,3] 的线段树在 [1,2] 的线段树的基础上建立

每一次加开的节点权值都是新的线段树不同于前一个线段树的位置确保了空间大幅度减少，同时还把问题的历史信息全部记录了下来实现了可持久化

复杂度分析

单点修改的时间是 O(n) ，又要在权值线段树上修改时间是 O(logn) ，所以单次修改总的时间复杂度是 O(nlogn) ，空间复杂度为 O(n)

代码实现

准备变量

  • a[] ，b[] 数组：一般一个用来记录原始数列一个记录离散后的序列

  • cnt：节点的个数（初始为 0 作为寄存指针）

  • rt[] ：存储每棵线段树根节点的编号

  • lc[] ，rc[] 数组：记录左儿子和右儿子的编号，类似于类似于动态开店

  • sum[] 数组：记录节点的权值（区间内序列中数出现的次数）

  • p ：记录离散化后序列长度，也就是线段树的区间的最大长度

变量声明

一般需要的数组要开 32 倍，可以用个快读加快读取速度

1
2
3
4
5
6
7
8
9
10
11
12
13
int n,m;//n个节点m个区间查询
int q,p,cnt;//离散化后序列长度,建树用到的中间变量，节点序号的寄存指针(统计节点个数)
int a[maxn],b[maxn];//a是存储原始数组权值,b存储去重后权值
int lc[maxn<<5],rc[maxn<<5],sum[maxn<<5],rt[maxn<<5];//节点左孩子,节点右孩子,节点权值,每颗线段树的根节点编号
//空间要注意:主席树一般开32倍

inline int read(){//快读
	int s=0,w=1;
	char c=getchar();
	for(;!isdigit(c);c=getchar())if(c=='-')w=-1;
	for(;isdigit(c);c=getchar())s=(s<<1)+(s<<3)+(c^48);
	return s*w;
}

提前建一棵空树，不建也没有关系为了以防万一还是规矩着来

1
build(rt[0],1,q);

离散化操作

一般序列的数可能会很大，但是数组线段树空间不可能开那么大，所以一般在存入线段树的时候将数离散化，因为查找返还的是序列的位置不影响最终查找结果

离散化确定区间最大边界值

1
2
3
4
5
6
for(int i=1;i<=n;++i)
a[i]=read(),b[i]=a[i];

//离散化
sort(b+1,b+1+n);//排序
q=unique(b+1,b+1+n)-b-1;//获去重后区间最大边界值

序列 1~n 位置依次建树，插入的数也要离散化

1
2
3
4
for(int i=1;i<=n;++i){//每次存入都相当于更新操作
	p=lower_bound(b+1,b+1+q,a[i])-b;//获取数离散化后的大小,p是全局变量
	rt[i]=update(rt[i-1],1,q);//给第i个节点建树
}

build函数

1
2
3
4
5
6
void build(int &rt,int l,int r){//以rt为根节点建立区间为[l,r]的线段树
	rt=++cnt,sum[rt]=0;//新的节点
	if(l==r)return;//找到相应的叶子节点退出
	int mid=(l+r)>>1;//否则往下走
	build(lc[rt],l,mid);build(rc[rt],mid+1,r);
}

update函数

1
2
3
4
5
6
7
8
9
int update(int o,int l,int r){//更新操作并返还新的节点的编号
	int tot=++cnt;//新的节点
	lc[tot]=lc[o],rc[tot]=rc[o],sum[tot]=sum[o]+1;
	if(l==r)return tot;//叶子结点，退出
	int mid=(l+r)>>1;
	if(mid>=p)lc[tot]=update(lc[tot],l,mid);
	else rc[tot]=update(rc[tot],mid+1,r);
	return tot;
}

query操作

1
2
3
4
5
6
7
int query(int u,int v,int l,int r,int k){//u,v为两棵线段树当前节点编号，相减就是询问区间
	int mid=(l+r)>>1,x=sum[lc[v]]-sum[lc[u]];//sum相减，前缀和思想
	if(l==r)return l;//叶子结点,找到kth目标，退出
	if(x>=k)return query(lc[u],lc[v],l,mid,k);
	else return query(rc[u],rc[v],mid+1,r,k-x);
	//kth操作，排名<=左儿子的数的个数，说明在左儿子，进入左儿子；反之，目标在右儿子，排名需要减去左儿子的权值
}

模板

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

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
#include<bits/stdc++.h>
using namespace std;
const int maxn=200010;//最大节点数

int n,m;//n个节点m个区间查询
int q,p,cnt;//离散化后序列长度,建树用到的中间变量，节点序号的寄存指针(统计节点个数)
int a[maxn],b[maxn];//a是存储原始数组权值,b存储去重后权值
int lc[maxn<<5],rc[maxn<<5],sum[maxn<<5],rt[maxn<<5];//节点左孩子,节点右孩子,节点权值,每颗线段树的根节点编号
//空间要注意:主席树一般开32倍

inline int read(){//快读
	int s=0,w=1;
	char c=getchar();
	for(;!isdigit(c);c=getchar())if(c=='-')w=-1;
	for(;isdigit(c);c=getchar())s=(s<<1)+(s<<3)+(c^48);
	return s*w;
}

void build(int &rt,int l,int r){//以rt为根节点建立区间为[l,r]的线段树
	rt=++cnt,sum[rt]=0;//新的节点
	if(l==r)return;//找到相应的叶子节点退出
	int mid=(l+r)>>1;//否则往下走
	build(lc[rt],l,mid);build(rc[rt],mid+1,r);
}

int update(int o,int l,int r){//更新操作并返还新的节点的编号
	int tot=++cnt;//新的节点
	lc[tot]=lc[o],rc[tot]=rc[o],sum[tot]=sum[o]+1;
	if(l==r)return tot;//叶子结点，退出
	int mid=(l+r)>>1;
	if(mid>=p)lc[tot]=update(lc[tot],l,mid);
	else rc[tot]=update(rc[tot],mid+1,r);
	return tot;
}

int query(int u,int v,int l,int r,int k){//u,v为两棵线段树当前节点编号，相减就是询问区间
	int mid=(l+r)>>1,x=sum[lc[v]]-sum[lc[u]];//sum相减，前缀和思想
	if(l==r)return l;//叶子结点,找到kth目标，退出
	if(x>=k)return query(lc[u],lc[v],l,mid,k);
	else return query(rc[u],rc[v],mid+1,r,k-x);
	//kth操作，排名<=左儿子的数的个数，说明在左儿子，进入左儿子；反之，目标在右儿子，排名需要减去左儿子的权值
}

signed main(){
	n=read(),m=read();
	for(int i=1;i<=n;++i)
	a[i]=read(),b[i]=a[i];

	//离散化
	sort(b+1,b+1+n);//排序
	q=unique(b+1,b+1+n)-b-1;//去重

	build(rt[0],1,q);

	for(int i=1;i<=n;++i){//每次存入都相当于更新操作
		p=lower_bound(b+1,b+1+q,a[i])-b;//全局变量update()操作用到
		rt[i]=update(rt[i-1],1,q);//给第i个节点建树
	}
    
	while(m--){
		int l=read(),r=read(),k=read();
		printf("%d\n",b[query(rt[l-1],rt[r],1,q,k)]);//在[l,r]查找第k大的数
	}
	return 0;
}

另一个模板

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=100100;//最大节点数

inline ll read(){
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}

int n,m,cnt;//n个节点m个查询，线段树节点的寄存指针
int a[maxn],root[maxn];//原始序列，根节点编号

vector<int> vec;//离散化后序列

struct Node{
    int l,r,val;
}tr[maxn*40];//左孩子和右孩子，以及统计的次数

int getid(int x){//获得离散化后的数
	return int(lower_bound(vec.begin(),vec.end(),x)-vec.begin())+1;
}

void update(int l,int r,int &x,int y,int val){
    cnt++;tr[cnt]=tr[y];tr[cnt].val++;x=cnt;
    if(l==r) return;
    int md=(l+r)>>1;
    if(val<=md) update(l,md,tr[x].l,tr[y].l,val);
    else update(md+1,r,tr[x].r,tr[y].r,val);
}

int query(int l,int r,int x,int y,int val){
    if(l==r)return l;
    int md=(l+r)>>1;
    int nw=tr[tr[y].l].val-tr[tr[x].l].val;
    if(val<=nw) return query(l,md,tr[x].l,tr[y].l,val);
    else return query(md+1,r,tr[x].r,tr[y].r,val-nw);
}

signed main(){
    n=read(),m=read();

    for(int i=1;i<=n;i++)
    a[i]=read(),vec.push_back(a[i]);

	//离散化
    sort(vec.begin(),vec.end());
	vec.erase(unique(vec.begin(),vec.end()),vec.end());//先用unique将重复的数放在后面，然后用erase删除

    for(int i=1;i<=n;i++)
    a[i]=getid(a[i]),update(1,n,root[i],root[i-1],a[i]);

    for(int i=1;i<=m;i++){
        int l=read(),r=read(),k=read();
        printf("%d\n",vec[query(1,n,root[l-1],root[r],k)-1]);
    }
    return 0;
}

动态求区间 kth

在求区间 kth同时还要求可以动态维护主席树，相当于要求主席树可以在区间查询的过程中进行单点修改。不可能让静态主席树区区一棵一棵的改，但是我们之前学过用树状数组和线段树来解决单点修改区间查询问题。下文以树状数组为例讲解树状数组套权值线段树来解决动态求区间 kth

静态求区间 kth 的主席树实际上是维护权值线段树的前缀和，我们用 T(i) 表示第 i 棵线段树，那么主席树 T(i)=T(i-1)+a[i] ，也就是说主席树是暴力的前缀和 T(i)=a[1]+a[2]+...+a[i] 。如果利用这个来解决动态求区间kth，则修改某个点 ai 需要进行 nlogn 个时间复杂度为 O(nlogn) 的修改，总的时间复杂度为 O(n2log2n) 很容易 TLE

动态求区间 kth 是在上述基础上进一步优化，将每棵线段树放在树状数组节点中，那么如此，每次修改某个点ai的时候只需要进行 logn 个时间复杂度为 O(logn) 的修改，总的时间复杂度和空间复杂度都是 O(log2n) 。查询时依旧是利用前缀和做差但不再是两棵线段树做差，而是 log 棵线段树与 log 棵线段树做差（树状数组查询区间的性质）

注意：用到离散化建树要先知道区间的范围，所以只能选择离线操作处理问题

在做题的时候可以把每棵树看做一个结点，用自顶向下的方法进行分析更容易理解

模板

模板题：给定一个含有 n 列 a1,a2,...,,an ，需要支持两种操作：

  • Q l r k 表示查询下标在区间 [l,r] 中的第k小的数
  • C x y 表示将ax改为 y

代码存在问题，11 测试点往后 TLE

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
//离线操作
#include<bits/stdc++.h>
using namespace std;
const int N=2e5;//最大顶点数

int n,m,tot,cnt;//n个节点m个操作、节点序号寄存指针以及原始序列的长度（寄存指针）
int rt[N],root[N],q[N],a[N],b[N];

struct node{//线段树结构体
	int l,r,val;//左孩子，右孩子和权值
}t[N*100];

struct data{
	int x,y,k;//区间左端、右端和操作的值
}Q[N];

inline int read(){//快读
	int s=0,w=1;
	char c=getchar();
	for(;!isdigit(c);c=getchar())if(c=='-')w=-1;
	for(;isdigit(c);c=getchar())s=(s<<1)+(s<<3)+(c^48);
	return s*w;
}

inline int getid(int x){//获得离散化后数的大小
	return lower_bound(b+1,b+1+cnt,x)-b;
}

void update(int l,int r,int &x,int y,int pos,int v){//权值线段树修改
    t[x=++tot]=t[y];t[x].val+=v;
    if(l==r)return;int mid=(l+r)>>1;
    if(pos<=mid)update(l,mid,t[x].l,t[y].l,pos,v);
    else update(mid+1,r,t[x].r,t[y].r,pos,v);
}

inline void change(int p,int v){//树状数组单点修改
    for(int i=p;i<=n;i+=i&-i)update(1,cnt,rt[i],rt[i],a[p],v);
}

inline int getsum(int x){//树状数组求和
    int sum=0;
    for(int i=x;i;i-=i&-i)sum+=t[t[q[i]].l].val;
	return sum;
}

inline int query(int x,int y,int k){
    for(int i=x;i;i-=i&-i)q[i]=rt[i];
    for(int i=y;i;i-=i&-i)q[i]=rt[i];
    int l=1,r=cnt,qx=x,qy=y;x=root[x];y=root[y];
    while(l<r){
        int sum=getsum(qy)-getsum(qx)+t[t[y].l].val-t[t[x].l].val;
        int mid=(l+r)>>1;
        if(k<=sum){
            for(int i=1;i<=n;i++)q[i]=t[q[i]].l;
            x=t[x].l;y=t[y].l;r=mid;
        }
        else{
            for(int i=1;i<=n;i++)q[i]=t[q[i]].r;
            x=t[x].r;y=t[y].r;l=mid+1;k-=sum;
        }
    }
    return l;
}

signed main()
{
	n=read();m=read();
	for(int i=1;i<=n;i++)
	a[i]=read(),b[i]=a[i];
	cnt=n;
	
	for(int i=1;i<=m;i++){//录入问题
		char ch;cin>>ch;
		if(ch=='Q')Q[i].x=read(),Q[i].y=read(),Q[i].k=read();//读入查询区间进而k值
		if(ch=='C')Q[i].x=read(),Q[i].k=read(),b[++cnt]=Q[i].k;//读入修改位置和修改的k值，相当于减去Q[i].x的序列数再加上Q[i].y的序列数
	}
	
	//离散化
    sort(b+1,b+1+cnt);
	cnt=unique(b+1,b+1+cnt)-b-1; 
	for(int i=1;i<=n;i++)a[i]=getid(a[i]);
    for(int i=1;i<=n;i++)update(1,cnt,root[i],root[i-1],a[i],1);

    for(int i=1;i<=m;i++){
        if(Q[i].y==0){//单点更改
            change(Q[i].x,-1);//减去原有序列数
			a[Q[i].x]=getid(Q[i].k);
			change(Q[i].x,1);//加上新的序列数
        }
        else printf("%d\n",b[query(Q[i].x-1,Q[i].y,Q[i].k)]);//区间查询
    }
	//system("pause");
  return 0;
}