洛谷 P3834 【模板】可持久化线段树 1（主席树）

缘起

本文研究非常经典的主席树入门题——静态区间第K小 洛谷 P3834 【模板】可持久化线段树 1（主席树）

其实在【1】和【2】中我们分别使用 平方分割和线（归）段（并）树切了它. 现在学习主席树姿势来切它 而且主席树的姿势将比【1】和【2】都快!

分析

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
Description:
这是个非常经典的主席树入门题——静态区间第K小

数据已经过加强，请使用主席树。同时请注意常数优化

如题，给定N个整数构成的序列，将对于指定的闭区间查询其区间内的第K小值。

Input:
第一行包含两个正整数N、M，分别表示序列的长度和查询的个数。

第二行包含N个整数，表示这个序列各项的数字。

接下来M行每行包含三个整数 l,r,k , 表示查询区间 [l,r] 内的第k小值。

对于100%的数据满足：1≤N,M≤20w
 

对于数列中的所有数 ai  均满足 −10^9≤ai≤10^9
 

样例数据说明：

N=5，数列长度为5，数列从第一项开始依次为 [25957,6405,15770,26287,26465]

第一次查询为 [2,2] 区间内的第一小值，即为6405

第二次查询为 [3,4] 区间内的第一小值，即为15770

第三次查询为 [4,5] 区间内的第一小值，即为26287

第四次查询为 [1,2] 区间内的第二小值，即为25957

第五次查询为 [4,4] 区间内的第一小值，即为26287

Output:
输出包含k行，每行1个整数，依次表示每一次查询的结果

Sample Input:
5 5
25957 6405 15770 26287 26465
2 2 1
3 4 1
4 5 1
1 2 2
4 4 1

Sample Output:
6405
15770
26287
25957
26287

时间限制
1s
内存限制
125MB

主席树的结构是我研读了 【4】和【5】得到的. 其实有了【3】的基础, 主席树还是相当好懂的~

先八卦一下, 为啥叫主席树? 传说是因为有一个名叫黄佳泰（HJT，当时主席胡锦涛的缩写）的神犇考场不会写归并树解决区间kth，所以就现场写了主席树 or2.

在认识主席树之前，我们先来看一种特殊的线段树——值域线段树（对，没错, 就是高中数学学习过的函数的值域）

假设我们有一个数组序列a[4]= [1,4,3,2], 即 a[1] = 1, a[2] = 4, a[3] = 3, a[4] = 2. 注意哈, 这里我们的序列的取值恰好就是1~n，通过离散化, 这是很好办到的（事实上, 这是经常要使用的技巧, 因为一般的题目的值域范围都太大了, 必须离散化）

我们对值域[1,n] （注意，一般的线段树都是对下标索引构建线段树, 从函数的角度来看, 就是对自变量构建线段树，但是值域线段树是对函数的值域构建线段树）构建线段树——线段树的每个节点表示相应的值域范围. 例如下图. 根节点的表示的值域范围就是 [1,4], 它的两个子节点的值域范围分别是 [1,2] 和 [3,4]. 然后对于 a[1,2,3,4], 我们统计线段树每个节点拥有的a中元素的个数——这很好办到， 只需要将每个a中的元素从线段树根节点打进去, 进行统计即可.

下图中每个节点上方的文字表示这个节点表示的值域范围, 例如根节点对应的值域范围是 大于等于1且小于等于4

​ 图1

上图中，根节点表示值域范围是[1,4]，它里面有4个（圈圈中的数字）a[1,2,3,4]中的元素. 叶子节点2 表示的值域范围是 [2,2], 它里面有1个a[1,2,3,4]中的元素.

这就是值域线段树

上图是统计值域线段树中每个节点对应值域包含a[1,2,3,4]中元素的个数. 如果是统计包含a[1,2,3]中元素的个数呢? 那么这棵线段树结构自然不变（都表示的是值域 [1,4]）, 但是圈圈中的数字就会变（毕竟少了a[4]=2）

​ 图2

注意图2和图1的区别. 区别就在下图3中的红色节点.

​ 图3

即图2和图1大部分节点都是相同的, 区别仅仅是图3中的红色节点, 而红色节点的个数是O(logn)的. 其中n是a中元素的个数（因为我们已经对a中的元素离散化了）等一下，好熟悉啊~ 这不就是【3】中可持久化的味道么? 所以对于图2，即在图1的基础上加入了a[4]=2, 我们没必要复制整棵图1中的(值域)线段树 而只需新增图3中的红色节点就行了. 就像下面这个样子

​ 图4

而图4就是传说中的主席树了. or2

【3】中我们已经写了可持久化线段树. 纵观本文, 其实主席树借鉴了可持久化线段树的精髓思想——复用节点（所以有的文章直接将主席树和可持久化线段树看做一个东西）. 可以这么说,

主席树=可持久化线段树(这种线段树还是值域线段树)+前缀思想

而且，通过本题和【3】的学习，我们意识到了一种”可持久化”的思想——即只新建改节点的思想，每次新建的节点个数仅仅是O(logn)级别的. 显然可持久化数据结构的时空复杂度均为O(nlogn).

类比可持久化线段树，我们还可以维护可持久化Trie、可持久化并查集、可持久化平衡树等数据结构，除了可持久化树状数据结构外，也有可持久化栈、可持久化块状链表等数据结构. 其实本质上都是借鉴了可持久化思想.

回到本题，我们怎么使用主席树解决静态区间kth问题呢?

首先, 因为本题值域范围太大（正负10亿）, 所以必须离散化，离散化之后对[1,n]建立线段树（就是值域线段树）. 然后遍历原数组, 即

1
2
3
4
for(int i = 1;i<=n; i++)
{
	加入a[i].
}

而每次加入a[i], 将导致O(logn)个节点的数字（即圆圈中的数字）发生改变. 我们仅仅对这O(logn)个节点进行新建. 这和【3】是一样的. 将每次加入a[i]构成的值域线段树视作一个版本. 那么一共n棵值域线段树, 从版本i-1到版本i新增O(logn)个节点. 通过可持久化的节点复用思想，主席树的空间复杂度是O(nlogn)的.

主席树的构建完毕之后, 我们开始回答询问[l,r,k], 即区间 [l,r]上的从小到大排名第k的元素. 将a[1,…i]构建的值域线段树称之为第i棵值域线段树. 则我们只需从第l-1棵值域线段树和第r棵值域线段树的根节点出发往下走. 注意, 从两棵线段树根节点同时出发, 每次都是往下走一层（即如果将树看做一种层状结构的话，就是每次都下一层楼）. 而且如果第l-1棵线段树往左（右）子树走的话, 则第r棵线段树也往左（右）子树走, 反之亦然. 即走法一致. 假设现在已经到达的第l-1棵线段树的节点是A, 而到达第r棵线段树的节点是B, 则其实A和B代表的值域范围是相同的（因为第l-1棵线段树和第r棵线段树从根节点出发的走法是相同的）, 令A的左子节点的圈圈中的数字是x, 令B的左子节点的圈圈中的数字是y, 考察 d = y-x, 并且令W为A（B）左子节点表示的值域范围（同样，A和B的左子节点表示的范围也是一样的）.

1
2
3
4
5
1. 如果d<k, 表明a[l,...,r]中在W中的元素的个数<k, 则下一步就应该往右子节点走.
2. 如果d>=k,表明a[l,...,r]中在W中的元素的个数>=k,则下一步就应该往左子节点走.

注意往右子节点走的时候, k要减去d
最后当值域区间长度为1的时候, 则就找到了答案

注意, 上述x和y要是A和B的左子节点的圈圈中的数字，而不能是A和B自己的圈圈中的数字. 不然就是错误的. 你想啊, 如果是根据A和B自身圈圈中的数字的话, 则比如A和B是各自值域线段树的根节点的话, 则B中圈圈的数字必然是j（假设B表示的是第j棵线段树）, A中圈圈的数字必然是i（假设i表示的是第i棵线段树）, 则j-i不就是a[i-1,..,j]中数字的个数嘛~ 你怎么能用这个”个数” 和k的大小来判断下一步要往左还是往右子树跳呢? 当然是不对的, 应该根据A和B的左子节点的圈圈中的数字的差值来确定到底是往左走还是往右走。

根据上述思想，我们不难写下如下ac代码（代码风格和【3】基本一致）

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
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
//#define LOCAL

const int maxn = 200005;
int n,m,a[maxn],b[maxn], cnt, num; // 则 [1,num]是值域

void discrete()
{
	memcpy(b,a, sizeof(a));
	sort(b+1, b+n+1);
	num = unique(b+1, b+n+1) - b-1; // 最后 b 就记录了 离散化之后的 [1~n] 分别对应原先的a中的哪个值
	for (int i = 1; i<=n; i++)
	{
		a[i] = lower_bound(b+1, b+num+1, a[i])-b;
	}
}

struct HJTTreeNode // 主席树
{
	int begin, end, x,l,r; // x是当前值域线段树中属于本节点的元素个数, l,r是左右孩子的索引
}hjt[maxn*20]; // nlogn的空间复杂度, 一定要大~ 不然RE

int ver[maxn]; // ver[i]是第i棵值域线段树根节点的索引

int newnode(int i) // 以hjt[i]为模板制作一个新的主席树节点, 返回此节点的索引
{
	int root = ++cnt;
	hjt[root].begin = hjt[i].begin;
	hjt[root].end = hjt[i].end;
	hjt[root].l = hjt[i].l;
	hjt[root].r = hjt[i].r;
	return root;
}

int build(int begin, int end) // 建（空）树，所谓空树指的是没有插入任何a[i]
{
	int root = ++cnt;
	hjt[root].begin = begin;
	hjt[root].end = end;
	hjt[root].x = 0;
	if (!(begin^end))
	{
		return root;
	}
	int mid = begin+end>>1;
	hjt[root].l = build(begin, mid);
	hjt[root].r = build(mid+1, end);
	return root;
}

int insert(int cur, int x) // 插入x, 返回的是树的根节点索引
{
	if (hjt[cur].begin==hjt[cur].end)
	{
		int root = newnode(cur); // 新建一个节点
		hjt[root].x = hjt[cur].x+1;
		return root;
	}
	int mid = hjt[cur].begin+hjt[cur].end>>1, other, me; // other 是cur的另一个孩子, 例如x在 cur的左（右）子树中, 则other和me就分别是cur的右（左）子树、左（右）子树
	bool flag; // true 表示 other是cur的左子树, false表示other是cur的右子树
	if (x<=mid)
	{
		other = hjt[cur].r;
		flag = false;
		me = insert(hjt[cur].l, x);
	}
	else
	{
		other = hjt[cur].l;
		flag = true;
		me = insert(hjt[cur].r, x);
	}
	int root = newnode(cur); // copy出新的节点
	hjt[root].l = flag?other:me;
	hjt[root].r = flag?me:other;
	hjt[root].x = hjt[cur].x+1;
	return root;
}

int query(int cur1, int cur2, int k, int l, int r)
{
	if (!(l^r))
	{
		return l;
	}
	int mid = l+r>>1, d = hjt[hjt[cur2].l].x - hjt[hjt[cur1].l].x; // d是差
	if (d>=k) // 两棵值域线段树都往左走
	{
		return query(hjt[cur1].l, hjt[cur2].l, k, l, mid);
	}
	else // 两棵值域线段都往右走
	{
		return query(hjt[cur1].r, hjt[cur2].r, k-d, mid+1, r);
	}
}

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d%d", &n,&m);
	for (int i = 1; i<=n; i++)
	{
		scanf("%d", a+i);
	}
	discrete(); // 值域离散化
	ver[0] = build(1,num); // 注意, 这里的num才是值域, 而不是n 因为可能有重复元素. 版本0的树的根节点索引存入ver[0], 版本为0的值域线段树尚未插入任何a[i],是一棵空树
	for (int i = 1;i<=n; i++)
	{
		ver[i] = insert(ver[i-1], a[i]); // 开始逐个插入a[i]构建主席树, 而且每次都是在前一个版本的值域线段树的基础上插入, 得到新的版本的值域线段树之后将此版本的值域线段树的根节点索引存入ver[i]中
	}
	while(m--)
	{
		int l,r,k; // 询问 [l,r] 上的从小到大第k小
		scanf("%d%d%d", &l, &r, &k);
		printf("%d\n", b[query(ver[l-1], ver[r], k, 1, num)]); // 从两棵值域线段树的根节点进入, 注意, 最后打印的是离散化之后的值, 要想得到题意
	}
	return 0;
}

ac情况

1
2
3
4
5
6
所属题目
P3834 【模板】可持久化线段树 1（主席树）
评测状态
Accepted
评测分数
100

喜提主席树模板一枚!

参考

【1】https://yfsyfs.github.io/2019/09/04/poj-2104-K-th-Number-%E5%B9%B3%E6%96%B9%E5%88%86%E5%89%B2/

【2】https://yfsyfs.github.io/2019/09/04/poj-2104-K-th-Number-%E7%BA%BF%E6%AE%B5%E6%A0%91/

【3】https://yfsyfs.github.io/2019/10/15/%E6%B4%9B%E8%B0%B7-P3919-%E3%80%90%E6%A8%A1%E6%9D%BF%E3%80%91%E5%8F%AF%E6%8C%81%E4%B9%85%E5%8C%96%E6%95%B0%E7%BB%84%EF%BC%88%E5%8F%AF%E6%8C%81%E4%B9%85%E5%8C%96%E7%BA%BF%E6%AE%B5%E6%A0%91-%E5%B9%B3%E8%A1%A1%E6%A0%91%EF%BC%89/

【4】https://blog.csdn.net/chenxiaoran666/article/details/81501461

【5】https://blog.csdn.net/hzk_cpp/article/details/87022264