主席树 笔记

发表于 | 更新于 | 阅读次数：
本文字数： 3.7k 字 | 阅读时长 ≈ 17 分钟

对于现在的我来说，只要有“可持久化”这个标签，一定伴随着 “毒瘤“，毕竟我刚学会…

好的首先介绍一下主席树是啥。主席树是“可持久化线段树”（Persistant Segment Tree）的中文民间俗称。不知道是因为有人把 Persistant 看成了 Presidant，还是因为它的发明者是 HJT（和某一任国家主席简称相同），被叫做“主席树”。

但是，可持久化是啥呢？

可持久化是啥

可持久化是亿点小优化，当你要开 $n$ 个线段树，但是线段树之间只差一次修改的时候，把空间复杂度降到 $O(n\log n)$。

如何优化呢？考虑我们现在要对一个单点进行修改，那么我们能影响到的位置（就是这个点以及它的祖先），一共才 $\log n$ ，个而其它位置都一样，所以我们可以 只新建 $\log n$ 个位置，整一个副本出来，其余位置直接继承原树即可。

蒯一张图举个例子，$n=5$，修改了第四个点：

（原作者）

（原博客）

（侵权删）（私信 3348064478@qq.com，本站评论有锅）

这样就能节省下超级多的空间！

但是，有利总有弊。这样的结构破坏的原来线段树的编号的完美特性，不能再用 index<<1 和 index<<1|1 来访问左右儿子了。我们要在线段树中多维护两个元素，左儿子和右儿子的编号。

经典题型

静态/动态区间第 $k$ 位：给定一个序列，每次给出 $l,r,k$，求 $[l,r]$ 中的数排序后，第 $k$ 个位置的数是谁。（当然，我们不会实际去排序，所以询问操作对原序列没有影响）

如果是动态的，那你还要支持单点修改的操作，会给定 $x,y$，要支持把第 $x$ 个位置上的数改成 $y$。

（假设我们离散化过了所有 $a_i$，和所有询问修改后变成的 $y$）

静态的问题

板子见 洛谷 3834

对于一个查询 $(l,r,k)$ ，（假设我们能）把 $a[l\cdots r]$ 拿出来建一颗权值线段树 $T$，查询就很容易了：把区间分成左半部分和右半部分，设左半部分中数字的个数为 $lsum$。如果 $k\le lsum$，那么就在左半部分中查找，否则就在右半部分中查找第 $k-lsum$ 个。

但是我们怎么把 $a[l\cdots r]$ 拿出来建一颗权值线段树呢？这个时空复杂度都是 $O(nlogn)$ 每次，再乘一个询问次数，肯定炸。

但是我们发现，线段树满足一种微妙的“可减性”：我们考虑建 $n$ 颗线段树 $T$，$T_i$ 表示 $a[1\cdots i]$ 组成的权值线段树。然后 $a[l\cdots r]$ 组成的权值线段树的对应位置就是 $T_r$ 的对应位置减去 $T_{l-1}$的对应位置。但是把 $T$ 建出来，光空间就够炸的了，是 $O(n^2)$ 的

考虑用上面“可持久化”的办法来优化求 $T$ 的过程：$T_i$ 和 $T_{i-1}$之间，差的只是在（离散化后的） $a_i$ 位置上加一。那么我们就让 $T_i$ 在 $T_{i-1}$ 的基础上，复制其中的 $\log$ 条链即可。这样就可以空间复杂度 $O(n\log n)$ ，时间复杂度 $O(n\log^2 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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{   
    #define N 200005
    #define F(i,l,r) for(int i=l;i<=r;++i)
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)
    #define Tra(i,u) for(int i=G.Start(u),v=G.To(i);~i;i=G.Next(i),v=G.To(i))
    #define p_b push_back
    #define sz(a) ((int)a.size())
    #define iter(a,p) (a.begin()+p)
    int I()
    {
        int x=0;char c=getchar();int f=1;
        while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
        while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
        return (x=(f==1)?x:-x);
    }
    void Rd(int cnt,...)
    {
        va_list args; va_start(args,cnt);
        F(i,1,cnt) {int* x=va_arg(args,int*);(*x)=I();}
        va_end(args);
    }
    class Persistant_Tree
    {
    public:
        struct node{int lid,rid; int l,r; int s;} t[N<<5];
        // 注意空间往死里开
        // lid,rid 存储左右儿子编号
        int rt[N],tot=0;
        // rt[i] 存第 i 颗线段树的根的编号
        #define ls(x) t[x].lid
        #define rs(x) t[x].rid
        #define L  t[rt].l
        #define R  t[rt].r
        #define S  t[rt].s
        #define up(x) t[x].s=t[t[x].lid].s+t[t[x].rid].s
        void Init() {tot=0;}
        int Build(int l,int r) // 建树，这一步和普通的线段树差别不大
        {
            int rt=++tot;
            L=l,R=r,S=0;
            if (l<r)
            {
                int mid=(l+r)>>1;
                ls(rt)=Build(l,mid); 
                rs(rt)=Build(mid+1,r); 
            }
            return rt;
        }
        int Insert(int pos,int rt) 
        // 在 rt 这个根的基础上，修改了 pos 位置
        // 把一路上修改的线段树上的链存一个副本，并返回这个链的顶端
        {
            int rr=++tot;
            t[rr].l=L; t[rr].r=R; t[rr].s=S+1;
            ls(rr)=ls(rt); rs(rr)=rs(rt); // 默认直接继承

            if (L<R)
            {
                int mid=(L+R)>>1;
                if (pos<=mid) ls(rr)=Insert(pos,ls(rt)); // 如果要修改左儿子，那么就左儿子开一个副本
                else          rs(rr)=Insert(pos,rs(rt)); // 右儿子同理
            }
            return rr;
        }
        int QueryKth(int r1,int r2,int l,int r,int k) // 在 T[r2]-T[r1] 这颗权值线段树中，查询排名为 k 的位置
        {
            if (l==r) return l;

            int mid=(l+r)>>1;
            int lsum=t[ls(r2)].s-t[ls(r1)].s; // 左边有多少数
            if (k<=lsum) return QueryKth(ls(r1),ls(r2),l,mid,k); // k<=lsum，在左边找
            else         return QueryKth(rs(r1),rs(r2),mid+1,r,k-lsum); // 否则在右边找
        }
    }T;

    int n,q,a[N];
    void Input()
    {
        Rd(2,&n,&q);
        F(i,1,n) a[i]=I();
    }

    int d[N];
    void Soviet()
    {
        F(i,1,n) d[i]=a[i];
        sort(d+1,d+n+1);
        F(i,1,n) a[i]=lower_bound(d+1,d+n+1,a[i])-d;

        T.Init();
        T.rt[0]=T.Build(1,n);
        F(i,1,n)
        {
            T.rt[i]=T.Insert(a[i],T.rt[i-1]);
            // 第 i 颗线段树的根，就是在第 i-1 颗线段树的基础上，在 a[i] 的位置上加了一
        }
        F(i,1,q)
        {
            int l=I(),r=I(),k=I();
            int pos=T.QueryKth(T.rt[l-1],T.rt[r],1,n,k);
            // 查询第 r 颗树减去第 l-1 颗树的第 k 位，就相当于 a[l...r] 中的第 k 位
            printf("%d\n",d[pos]);
        }
    }

    #define Flan void
    Flan IsMyWife()
    {
        Input();
        Soviet();
    }
}
int main()
{
    Flandre_Scarlet::IsMyWife();
    getchar();getchar();
    return 0;
}

动态的问题

板子见 洛谷 2617

做好准备，这比静态的问题要困难的多。我当时调试了 $10$ 个小时才过去。

前置芝士： 树状数组

点击

（你不会这个还来学主席树？）

（算了，还是先复习一下）

首先回顾一下树状数组的概念：

对于第 $i$ 个位置，我们维护从 $i$ 开始往前 $\operatorname{lowbit}(i)$ 个数的和。然后每次修改只需要改 $\log$ 个位置，

查询也只要求 $\log$ 个位置的和。

为了方便说明，下面设 $nex(i)=i+\operatorname{lowbit}(i)$，$pre(i)=i-\operatorname{lowbit}(i)$

（才不是因为我懒得打 $\operatorname{lowbit}$ 呢！哼╭(╯^╰)╮）

故 技 重 施

动态的问题就是我们要支持对其中一个位置进行修改了。修改 了第 $i$ 个位置后，$[i,n]$ 范围内的所有线段树都要被修改一次，时间复杂度就爆炸了。

等等，这个问题我们是不是见过一次？

把时间倒回大约一两年前，我们遇到过这样一个问题：“单点修改，求区间和”

我们当时是用的树状数组解决的问题：树状数组 $T$，第 $i$ 个位置 $T_i$ 维护 $pre(i)+1$ 到 $i$ 的和。要查询 $i$ 的前缀和，只要求 $T_i,T_{pre(i)},T_{pre(pre(i))}\cdots $ 的和即可。

那么我们可以用树状数组的思路维护主席树啊！

总体思路

那么我们怎么写呢？我们写一个“树状数组套线段树”：维护 $n$ 个线段树 $T$，其中 $T_i$ 维护 $[pre(i)+1,i]$ 之间的所有 $a_{x}$ 组成的权值线段树即可。

初始化

对于初始化操作，我们建树。先开 $n$ 颗线段树，但是初始的时候 $n$ 颗线段树 全部 和初始的线段树共用 （也就是对于每个 $i$，$root[i]=root[0]$）

然后对于第 $i$ 个位置，它只能影响到 $i,nex(i),nex(nex(i))\cdots $ 位置上的线段树。对于这些位置上的每一个线段树 $T_i$，我们在它 自己 的基础上，插入 $a[i]$ 位置（并加一）。

修改操作

对于修改第 $x$ 个位置从原来的 $a[x]$ 变成 $y$ （修改完令 $a[x]=y$），我们要找到所有包含它的线段树，$T$，在第 $a[x]$ 个位置 $-1$，在 $y$ 的位置 $+1$，这样就完成了修改操作。

查询操作

静态的问题中，查询 $[l,r]$ 的第 $k$ 大，用 $T_r$ 来减掉 $T_{l-1}$，然后判断答案在左边还是在右边。传参数只要传入 $T_{l-1}$ 和 $T_r$ 的根节点编号即可。

然而我们现在是树状数组套线段树，两者相减，可不是两颗线段树相减了，而是

第 $r,pre(r),pre(pre(r))\cdots$ 颗线段树的和，减去

第 $l-1,pre(l-1),pre(pre(l-1)) \cdots$ 颗线段树的和。

然后我们显然没法一次性传这么多参数进去（而且还是不定长度，更麻烦了）。我们的办法是，在查询之前，先把所有的 $l-1,pre(l-1),pre(pre(l-1)) \cdots$ 保存在一个数组 $R_1$ 里，再把所有的 $r,pre(r),pre(pre(r)) \cdots$ 保存在一个数组 $R_2$ 里（并记下这两个数组的长度）（从 $1$ 开始编号的同学可以考虑用第 $0$ 个位置作为长度，我就是这么写的）

每次查询前缀 $r$ 颗树减去前缀 $l-1$ 颗树的时候，就遍历 $R_1,R_2$，把第 $R_{2i}$ 颗树的对应位置都加起来，把第 $R_{1i}$ 颗树的对应位置都减掉，得到 $lsum$。然后用静态里面的做法即可。

代码
点击
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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
	#define N 100005
	#define F(i,l,r) for(int i=l;i<=r;++i)
	#define D(i,r,l) for(int i=r;i>=l;--i)
	#define Fs(i,l,r,c) for(int i=l;i<=r;c)
	#define Ds(i,r,l,c) for(int i=r;i>=l;c)
	#define MEM(x,a) memset(x,a,sizeof(x))
	#define FK(x) MEM(x,0)
	#define Tra(i,u) for(int i=G.Start(u),v=G.To(i);~i;i=G.Next(i),v=G.To(i))
	#define p_b push_back
	#define sz(a) ((int)a.size())
	#define iter(a,p) (a.begin()+p)
	int I()
	{
	    int x=0;char c=getchar();int f=1;
	    while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
	    while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	    return (x=(f==1)?x:-x);
	}
	void Rd(int cnt,...)
	{
	    va_list args; va_start(args,cnt);
	    F(i,1,cnt) {int* x=va_arg(args,int*);(*x)=I();}
	    va_end(args);
	}

	class Persistant_tree // 被卡常了的主席树...
	{
	public:
		struct node{int lid,rid,s;} t[N*400];
		// 去掉了存储左右区间的成员变量，左右区间在函数调用过程中记录
		// 从而把空间优化成原来的 3/5，然后数组开大点
		int rt[N],tot;
		#define ls(x) t[x].lid
		#define rs(x) t[x].rid
		#define S     t[rt].s
		void Init() {tot=0;}
		int Build(int l,int r)
		{
			int rt=++tot; S=0;
			if (l<r)
			{
				int mid=(l+r)>>1;
				ls(rt)=Build(l,mid);
				rs(rt)=Build(mid+1,r);
			}
			return rt;
		} // 这个一样的
		int Insert(int l,int r,int pos,int type,int rt)
		// 修改操作可能会有 -1，于是加上一个 type，type=1或-1表示加还是减
		{
			int rr=++tot;
			ls(rr)=ls(rt); rs(rr)=rs(rt); t[rr].s=S+type;
			if (l<r)
			{
				int mid=(l+r)>>1;
				if (pos<=mid) ls(rr)=Insert(l,mid,pos,type,ls(rt));
				else 		  rs(rr)=Insert(mid+1,r,pos,type,rs(rt));
				// 这些一样的
			}
			return rr;
		}
		int R2[30],R1[30];
		// R2,R1 含义见上面
		// 数组第 0 个位置保存数组长度
		int QueryKth(int l,int r,int k)
		{
			if (l==r) return l;

			int lsum=0;
			F(i,1,R2[0]) lsum+=t[ls(R2[i])].s;
			F(i,1,R1[0]) lsum-=t[ls(R1[i])].s;
			// 这个就是要遍历累加来求出 lsum 的值了
			int mid=(l+r)>>1;
			if (k<=lsum) 
			{
				F(i,1,R2[0]) R2[i]=ls(R2[i]);
				F(i,1,R1[0]) R1[i]=ls(R1[i]);
				// 跳左右儿子也要一块跳...这个复杂度活生生的多一个 log 啊
				return QueryKth(l,mid,k);
			}
			else
			{
				F(i,1,R2[0]) R2[i]=rs(R2[i]);
				F(i,1,R1[0]) R1[i]=rs(R1[i]);
				return QueryKth(mid+1,r,k-lsum);
			}
		}
	}T;

	int n,m,a[N];
	struct node{char type; int a,b,c;} q[N];
	// 如果是 C 操作，那么我们只用 a,b，表示将 a 位置变成了 b
	// 如果是 Q 操作，那么我们 a,b,c 都用，表示 [a,b] 区间排名第 c 位的数
	void Input()
	{
		Rd(2,&n,&m);
		F(i,1,n) a[i]=I();
		F(i,1,m)
		{
			char o[3]; scanf("%s",o);
			if (o[0]=='Q') 
			{
				q[i]=(node){o[0],I(),I(),I()};
			}
			else
			{
				q[i]=(node){o[0],I(),I()};
			}
		}
	}

	int d[N<<2],dcnt=0;
	#define Find(x) (lower_bound(d+1,d+dcnt+1,x)-d)
	void Insert(int pos,int type)
	{
		int x=Find(a[pos]);
		for(int i=pos;i<=n;i+=(i&(-i))) 
		{
			int lastr=T.rt[i]; // 保存原来的根
			T.rt[i]=T.Insert(1,dcnt,x,type,lastr); // 以便在原来的基础上插入
		}
	}
	int Query(int l,int r,int k)
	{
		F(i,0,22) T.R1[i]=T.R2[i]=0;
		for(int i=r;i>0;i-=(i&(-i))) T.R2[++T.R2[0]]=T.rt[i];
		for(int i=l;i>0;i-=(i&(-i))) T.R1[++T.R1[0]]=T.rt[i];
		// 先预先求好 R1,R2
		return T.QueryKth(1,dcnt,k);
	}
	void Soviet()
	{
		F(i,1,n) d[++dcnt]=a[i];
		F(i,1,m) if (q[i].type=='C') d[++dcnt]=q[i].b;
		sort(d+1,d+dcnt+1);

		T.Init();
		T.rt[0]=T.Build(1,dcnt); F(i,1,n) T.rt[i]=1;
		F(i,1,n) Insert(i,1);
		F(i,1,m)
		{
			if (q[i].type=='Q')
			{
				int pos=Query(q[i].a-1,q[i].b,q[i].c);
				printf("%d\n",d[pos]);
			}
			if (q[i].type=='C')
			{
				int x=q[i].a,y=q[i].b;
				Insert(x,-1); a[x]=y;
				Insert(x,1);
			}
		}
	}

	#define Flan void
	Flan IsMyWife()
	{
		Input();
		Soviet();
	}
}
int main()
{
	Flandre_Scarlet::IsMyWife();
	getchar();getchar();
	return 0;
}
w