主席树

firstlight Lv2
  2024-01-15 11:08 2024-01-15 11:08 创建   2025-01-22 22:41:04 2025-01-22 22:41:04 更新      

概念：

主席树的全称为可持久化权值线段树，用于维护每一个数在插入线段树后的历史版本，从而进行区间 大数查询等操作

基本形态：

如果为每一历史版本新开一棵线段树，空间复杂度将达到 ，是不可接受的

而对于一棵线段树，每一次操作仅会对树上的一条链产生影响，所以每一次新建一条链，再将其余不在链上的点用指针指向即可

第一版本：

主席树的建链式存储_1

第二版本：

主席树的链式建树_2

第三版本：

主席树的链式建树_3

写法：

首先建立第一个版本的线段树，然后用链的形式向线段树中插入数字，形成一棵完整的主席树

1.build(l, r)

建立空的线段树作为初始版本

主席树每一个节点可以有多余两个节点的情况，所以不能用堆式建树，只能以动态开点的形式进行建树

该步有时不必要，尤其是值域太大且不能离散化时

1.定义结构体：

1
2
3
4
struct Node{
    int l, r;
    int cnt;
} tr[M];      // 可持久化数据结构有内存占用大的通病,数组一定开足,能开多大开多大!!!

2.建树函数：

1
2
3
4
5
6
7
8
9
int build(int l, int r)
{
    int p = ++ idx;                                       //插入新节点
    if(l == r) return p;

    int mid = l + r >> 1;
    tr[p].l = build(l, mid), tr[p].r = build(mid + 1, r); //建立左右两子树,与传统线段树相似
    return p;
}

2.update(p, l, r, x)

建立每一个历史版本

为上一个版本的当前位置上节点的编号， 为区间的左右端点 (在结构体中存储不现实, 需要传入)， 为插入的值

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int update(int p, int l, int r, int x)
{
    int q = ++ idx;
    tr[q] = tr[p];                                      // q 是 p 的复制,直接将其信息进行复制

    if(l == r)
    {
        { 维护所需信息 };
        return q;
    }

    int mid = l + r >> 1;
    if(x <= mid) tr[q].l = update(tr[p].l, l, mid, x); // 建立左子树
    else tr[q].r = update(tr[p].r, mid + 1, r, x);     // 建立右子树
        // 这两步操作时,q 与 p 一定为同步的节点,同时向左或向右即可
    pushup(q);                                         // 将左右子树的信息整合到父节点上
    return q;
}

query(q, p, l, r, k)

以区间 大数查询为例

表示右端点的版本的根， 表示左端点的版本的根， 表示值域区间的左右端点， 表示查询的数的排名

代码释义详见这里

Code:

1
2
3
4
5
6
7
8
int query(int q, int p, int l, int r, int k)
{
    if(l == r) return r;
    int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt; 
    int mid = l + r >> 1;
    if(k <= cnt) return query(tr[q].l, tr[p].l, l, mid, k);
    else return query(tr[q].r, tr[p].r, mid + 1, r, k - cnt);
}

Attention:

  1. 使用主席树时大部分情况需要离散化使值域变小，离散后值域长度为离散化数组的大小
  2. 注意 和 时传入的是每一个版本的根

例题：

1.P3834 [模板] 可持久化线段树 2

裸的区间 大数查找，建树查询即可

题解链接

2.P4587 [FJOI2016] 神秘数

设当前已考虑的数可组成的所有连续自然数的集合 的元素个数为

根据题目发现每一次加入一个数 时，若 ，则它一定为神秘数，否则区间长度变为

所以只需要维护一段区间即可

该区间满足：

  1. 左端点为
  2. 右端点为 可达到的最大范围

每一次对这样的权值区间进行区间内权值和 的查询 (与传统线段树的区间查询类似)

将左端点变为右端点+1，右端点累加 即可完成区间的转移

此题的值域较大且无法离散化，但是求区间权值和时建立完全树不必要，动态开点即可，舍去

Code:

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
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define gcu getchar_unlocked
using namespace std;

const int N = 100010, M = 18000010, len = 1e9;
typedef long long ll;
namespace fastread {
	void read(int &x)
	{
		x = 0; int f = 1; char c = gcu();
		while(c < '0' || c > '9') {if(c == '-') f = -1; c = gcu();}
		while(c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = gcu();
		x *= f;
	}
} using fastread::read;

int n, m;
int s[N]; 
struct Node{
	int l, r;
	int sum;
} tr[M];
int root[N], idx;

int update(int p, int l, int r, int x)
{
	int q = ++ idx;
	tr[q] = tr[p];
	if(l == r)
	{
		tr[q].sum += x;
		return q;
	}
	
	ll mid = (ll)(l + r) >> 1ll;
	if(x <= mid) tr[q].l = update(tr[p].l, l, mid, x);
	else tr[q].r = update(tr[p].r, mid + 1, r, x);
	tr[q].sum = tr[tr[q].l].sum + tr[tr[q].r].sum;
	return q;
}

int query(int p, int q, int l, int r, int suml, int sumr)
{
	if(suml <= l && sumr >= r) return tr[q].sum - tr[p].sum;
	
	ll mid = (ll)(l + r) >> 1ll;
	int sum = 0;
	if(suml <= mid) sum = query(tr[p].l, tr[q].l, l, mid, suml, sumr);
	if(sumr > mid) sum += query(tr[p].r, tr[q].r, mid + 1, r, suml, sumr);
	return sum;
}

int main()
{
	read(n);
	for(int i = 1; i <= n; i ++ ) read(s[i]);
	
	root[0] = ++ idx;
	for(int i = 1; i <= n; i ++ ) root[i] = update(root[i - 1], 1, len, s[i]);
	
	read(m);
	int l, r;
	while(m -- )
	{
		read(l), read(r);
		int suml = 0, sumr = 0;
		while(true)
		{
			int sum = query(root[l - 1], root[r], 1, len, suml + 1, sumr + 1);
			if(sum == 0) break;
			suml = sumr + 1, sumr += sum;
		}
		printf("%d\n", sumr + 1);
	}
	return 0;
}

拓展：动态主席树

思想：

如果对主席树进行单点修改，用静态主席树的时间复杂度为 ，显然不可行

但是，由静态主席树可知，主席树具有前缀和的特性，所以可以用树状数组代替本来的线性存储，即使用树状数组套主席树

此时修改的时间复杂度为

例题：

1.P2617 Dynamic Rankings

查询时预先将要查找的树记下，节点下传时一起下传即可实现查找

仅仅是将静态主席树中数组的操作全部更换为树状数组的操作而已

可以参考这篇文章

code:
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
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define gcu getchar_unlocked 
using namespace std;
const int N = 100010, M = 40000100, Log = 20;
typedef long long ll;

namespace fastread {
	void read(int &x)
	{
		x = 0; int f = 1; char c = gcu();
		while(c < '0' || c > '9') {if(c == '-') f = -1; c = gcu();}
		while(c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = gcu();
		x *= f;
	}
} using fastread::read;

int n, m;
int s[N], len;
vector<int> all;
char op[N][2];
struct QUERY{
	int a, b, kth;
} que[N];

namespace president_tree {
	struct Node{
		int l, r;
		int cnt;
	}tr[M];
	int root[N], idx;
	int x[Log], cntx, y[Log], cnty;
	
	int find(int w) {return lower_bound(all.begin(), all.end(), w) - all.begin();}
	
	int lowbit(int w) {return w & -w;}
	
	int build(int l, int r)
	{
		int p = ++ idx;
		if(l == r) return p;
		
		int mid = l + r >> 1;
		tr[p].l = build(l, mid), tr[p].r = build(mid + 1, r);
		return p;
	}
	
	int update(int pre, int l, int r, int w, int v){
	    int p = ++ idx;
	    tr[p] = tr[pre];
	    if(l == r)
	    {
	        tr[p].cnt += v;
	        return p;
	    }
	    
	    int mid = l + r >> 1;
	    if(w <= mid) tr[p].l = update(tr[pre].l, l, mid, w, v);
	    else tr[p].r = update(tr[pre].r, mid + 1, r, w, v);
	    tr[p].cnt = tr[tr[p].l].cnt + tr[tr[p].r].cnt;
	    return p;
	}
	
	void add(int w, int v)
	{
		int pos = find(s[w]);
		for(; w <= n; w += lowbit(w))
			root[w] = update(root[w], 0, len - 1, pos, v);
	}
	
	int query(int l, int r, int k)
	{
		if(l == r) return l;
		int mid = l + r >> 1;
		int sum = 0;
		
		for(int i = 1; i <= cntx; i ++ ) 
			sum -= tr[tr[x[i]].l].cnt;
		for(int i = 1; i <= cnty; i ++ ) 
			sum += tr[tr[y[i]].l].cnt;
		
		if(k <= sum)
		{
			for(int i = 1; i <= cntx; i ++ ) 
				x[i] = tr[x[i]].l;
			for(int i = 1; i <= cnty; i ++ ) 
				y[i] = tr[y[i]].l;
			return query(l, mid, k);
		}
		else 
		{
			for(int i = 1; i <= cntx; i ++ ) 
				x[i] = tr[x[i]].r;
			for(int i = 1; i <= cnty; i ++ ) 
				y[i] = tr[y[i]].r;
			return query(mid + 1, r, k - sum);
		}
	}
} using namespace president_tree;

int main()
{
	read(n), read(m);
	for(int i = 1; i <= n; i ++ ) 
	{
		read(s[i]);
		all.push_back(s[i]);
	}
	
	int a, b, c;
	for(int i = 1; i <= m; i ++ ) 
	{
		scanf("%s", op[i]);
		if(*op[i] == 'Q') 
		{
			read(a), read(b), read(c);
			que[i] = {a, b, c};
		}
		else 
		{
			read(a), read(b);
			all.push_back(b);
			que[i].a = a, que[i].b = b;
		}
	}
	
	sort(all.begin(), all.end());
	all.erase(unique(all.begin(), all.end()), all.end());
	len = all.size();
	
	root[0] = build(0, len - 1);
	
	for(int i = 1; i <= n; i ++ ) add(i, 1);
	
	for(int i = 1; i <= m; i ++ ) 
	{
		if(*op[i] == 'Q') 
		{
			cntx = cnty = 0;
			int l = que[i].a, r = que[i].b, k = que[i].kth;
			for(int j = l - 1; j; j -= lowbit(j))
				x[ ++ cntx] = root[j];
			for(int j = r; j; j -= lowbit(j))
				y[ ++ cnty] = root[j];
			printf("%d\n", all[query(0, len - 1, k)]);
		}
		else 
		{
			int a = que[i].a, val = que[i].b;
			add(a, -1);
			s[a] = val;
			add(a, 1);
		}
	}
	return 0;
}

2.P3380 [模板] 二逼平衡树 (树套树)

只是上一题加入了一些操作

所谓 查询 在区间 的排名即为将所有权值小于 的权值的个数累加即可

而查询前驱只需找到 的排名 后输出 的值即可

查询后继是需要找到 的排名 后输出 的值即可 (可以避免出现 不在区间内的情况)

为了判断边界，将两边界值也插入树中即可

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
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010, M = 37000010, INF = 2147483647, Log = 25;
typedef long long ll;

namespace getchar_unlocked_fastread {
	const void read(int &x)
	{
		x = 0; int f = 1; char c = getchar_unlocked();
		while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar_unlocked();}
		while(c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar_unlocked();
		x *= f;
	}
}using getchar_unlocked_fastread::read;

int n, m;
int s[N];
vector<int> all;
struct Node{
	int l, r;
	int cnt;
} tr[M];
struct QUERY{
	int op, a, b, c;
} que[N];
int root[N], idx;
int x[Log], cntx, y[Log], cnty, len;

int find(int w) {return lower_bound(all.begin(), all.end(), w) - all.begin();}

int lowbit(int w) {return w & -w;}

int build(int l, int r)
{
	int p = ++ idx;
	if(l == r) return p;
	
	int mid = l + r >> 1;
	tr[p].l = build(l, mid), tr[p].r = build(mid + 1, r);
	return p;
}

int update(int p, int l, int r, int ver, int v)
{
	int q = ++ idx;
	tr[q] = tr[p];
	if(l == r)
	{
		tr[q].cnt += v;
		return q;
	}
	
	int mid = l + r >> 1;
	if(ver <= mid) tr[q].l = update(tr[p].l, l, mid, ver, v);
	else tr[q].r = update(tr[q].r, mid + 1, r, ver, v);
	tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt;
	return q;
}

void add(int ver, int v)
{
	int p = find(s[ver]);
	for(; ver <= n; ver += lowbit(ver))
		root[ver] = update(root[ver], 0, len - 1, p, v);
}

void move(int l, int r)
{
	cntx = cnty = 0;
	for(int i = l - 1; i; i -= lowbit(i))
		x[ ++ cntx] = root[i];
	for(int i = r; i; i -= lowbit(i))
		y[ ++ cnty] = root[i];
}

int query_rank(int l, int r, int k)
{
	if(l == k && r == k) return 1;
	
	int cnt = 0;
	for(int i = 1; i <= cntx; i ++ ) 
		cnt -= tr[tr[x[i]].l].cnt;
	for(int i = 1; i <= cnty; i ++ ) 
		cnt += tr[tr[y[i]].l].cnt;
	
	int mid = l + r >> 1;
	if(k <= mid)
	{
		for(int i = 1; i <= cntx; i ++ ) 
			x[i] = tr[x[i]].l;
		for(int i = 1; i <= cnty; i ++ ) 
			y[i] = tr[y[i]].l;
		
		return query_rank(l, mid, k);
	} 
	else
	{
		for(int i = 1; i <= cntx; i ++ ) 
			x[i] = tr[x[i]].r;
		for(int i = 1; i <= cnty; i ++ ) 
			y[i] = tr[y[i]].r;
		
		return cnt + query_rank(mid + 1, r, k);
	}
}

int query_val(int l, int r, int k)
{
	if(l == r) return l;
	
	int cnt = 0;
	for(int i = 1; i <= cntx; i ++ ) 
		cnt -= tr[tr[x[i]].l].cnt;
	for(int i = 1; i <= cnty; i ++ ) 
		cnt += tr[tr[y[i]].l].cnt;
	
	int mid = l + r >> 1;
	if(k <= cnt)
	{
		for(int i = 1; i <= cntx; i ++ ) 
			x[i] = tr[x[i]].l;
		for(int i = 1; i <= cnty; i ++ ) 
			y[i] = tr[y[i]].l;
			
		return query_val(l, mid, k);
	}
	else 
	{
		for(int i = 1; i <= cntx; i ++ ) 
			x[i] = tr[x[i]].r;
		for(int i = 1; i <= cnty; i ++ ) 
			y[i] = tr[y[i]].r;
			
		return query_val(mid + 1, r, k - cnt);
	}
}

int query_pre(int a, int b, int l, int r, int k)
{
	int rank = query_rank(0, len - 1, k);
	move(a, b);
	return all[query_val(0, len - 1, rank - 1)];
}

int query_suc(int a, int b, int l, int r, int k)
{
	int rank = query_rank(0, len - 1, k + 1); // 直接查找 k + 1 的排名可以避免判断值是否在当前序列中
	move(a, b);
	return all[query_val(0, len - 1, rank)];
}

int main()
{
	read(n), read(m);
	for(int i = 1; i <= n; i ++ )
	{
		read(s[i]);
		all.push_back(s[i]);
	}
	
	int op, a, b, c;
	for(int i = 1; i <= m; i ++ ) 
	{
		read(op);
		if(op == 1)
		{
			read(a), read(b), read(c);
			que[i] = {op, a, b, c};
			all.push_back(que[i].c);
		}
		else if(op == 2)
		{
			read(a), read(b), read(c);
			que[i] = {op, a, b, c};
		}
		else if(op == 3)
		{
			read(a), read(b);
			que[i].op = op, que[i].a = a, que[i].b = b;
			all.push_back(b);
		}
		else if(op == 4)
		{
			read(a), read(b), read(c);
			que[i] = {op, a, b, c};
			all.push_back(c);
		}
		else 
		{
			read(a), read(b), read(c);
			que[i] = {op, a, b, c};
			all.push_back(c);
		}
	} 
	all.push_back(-INF), all.push_back(INF);
	
	sort(all.begin(), all.end());
	all.erase(unique(all.begin(), all.end()), all.end());
	len = all.size();
	
	root[0] = build(0, len - 1);
	
	for(int i = 1; i <= n; i ++ ) add(i, 1);
	
	int l, r, k;
	for(int i = 1; i <= m; i ++ ) 
	{
		l = que[i].a, r = que[i].b, k = que[i].c;
		
		if(que[i].op != 3) move(l, r);
		
		if(que[i].op == 1) printf("%d\n", query_rank(0, len -1, find(k)));
		else if(que[i].op == 2) printf("%d\n", all[query_val(0, len - 1, k)]);
		else if(que[i].op == 3)
		{
			add(l, -1);
			s[l] = r;
			add(l, 1);
		}
		else if(que[i].op == 4) printf("%d\n", query_pre(l, r, 0, len - 1, find(k)));
		else if(que[i].op == 5) printf("%d\n", query_suc(l, r, 0, len - 1, find(k)));
	}
	
	return 0;
}
  • 标题: 主席树
  • 作者: firstlight
  • 创建于 : 2024-01-15 11:08:00
  • 更新于 : 2025-01-22 22:41:04
  • 链接: https://blog.firstlightport.top/posts/zhu-xi-shu/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
目录
主席树
  1. 概念：
  2. 基本形态：
  3. 写法：
    1. 1.build(l, r)
    2. 2.update(p, l, r, x)
    3. query(q, p, l, r, k)
  4. Attention:
  5. 例题：
    1. 1.P3834 [模板] 可持久化线段树 2
    2. 2.P4587 [FJOI2016] 神秘数
  6. 拓展：动态主席树
    1. 思想：
    2. 例题：