抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

可持久化trie学习笔记

发布于：2019年10月3日

可持久化trie是一种和最大异或和关系非常紧密的算法。

例题1

给你一个数列ai\\{a_i\\}，每次询问给你l,r,xl,r,x，要你计算max⁡{a[i]⊕x}(i∈[l,r])\max\{ a[i]\oplus x\}(i \in [l,r])

如何考虑？

从高位往低位贪心！

举个例子：

a[i]:100,110,101,010a[i]:100,110,101,010

x=010x=010

首先，发现a[i]a[i]的第最高位必须是11，即使a[i]⊕xa[i] \oplus x最大的a[i]a[i]只可能是100,110100,110中的一个。

再看第二位，如果第二位是11的话，1⊕1=01\oplus1=0，不是最大的，a[i]a[i]就确定为100100。

于是我们可以设计出如下算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
procedure get_max(l,r,x){
    s={a[l],a[l+1],a[l+2]...a[r]};
    for (k in [log2(max(a[i])),1]){
        if (x第k位是1){
            if (s里面有数第k位是0) s=>s中所有第k位为0的数
            else s不变
        }
        else {
            if (s里面有数第k位是1) s=>s中所有第k位为1的数
            else s不变
		}
    }
}

发现此算法效率极慢，甚至比不上暴力。

如何优化？

发现一个重要的性质，每次操作之后，ss中所有数的二进制表示中，[log⁡2(max⁡(a[i])),k][\log_2(\max(a[i])),k]的位上面都是一样的。

这让我们想到了trie树。

考虑用trie维护ss，如何马上求出a[l],a[l+1],a[l+2]...a[r]{a[l],a[l+1],a[l+2]...a[r]}呢？

我们需要可持久化，实现时类似于主席树前缀和做差即可。

1
Print(Query(31,rt[l-1],rt[r],x),'\n');

如何快速查询ss中有没有二进制kk位上面是0/10/1的数，只要查询这个子树的大小即可。

1
2
3
4
5
6
7
8
9
10
11
int Query(int index,int l,int r,int x){
	if (index<0) return 0;
	bool pos=(x>>index)&1;
	int k=tree[ch(r,pos^1)].sz-tree[ch(l,pos^1)].sz;//子树大小
	if (k>0){//有pos^1子树，根据贪心，必须往那里去
		return Query(index-1,ch(l,pos^1),ch(r,pos^1),x)+(1<<index);
	}
	else {
		return Query(index-1,ch(l,pos),ch(r,pos),x);
	}
}

插入也非常简单：

1
2
3
4
5
6
7
8
9
10
11
void Insert(int &i,int pre,int index,int x){
	tree[i=++tot].sz=tree[pre].sz;//新建节点
	if (index<0){
		tree[i].sz++;
		return ;
	}
	bool pos=(x>>index)&1;
	ch(i,pos^1)=ch(pre,pos^1);//继承子节点
	Insert(ch(i,pos),ch(pre,pos),index-1,x);//继续插入
	tree[i].sz=tree[ch(i,0)].sz+tree[ch(i,1)].sz;//更新子树大小
}

总的代码：

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
#include <bits/stdc++.h>
#define MAXN 200005
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while (ch<'0'||ch>'9'){
		if (ch=='-') f=-1;
		ch=getchar();
	}
	while (ch>='0'&&ch<='9'){
		x=(x<<3)+(x<<1)+(ch^'0');
		ch=getchar();
	}
	return x*f;
}
void print(int x){
	if (x>9) print(x/10);
	putchar('0'+x%10);
}
inline void Print(int x,char ch){
	if (x==0) return putchar('0'),void();
	if (x<0) x=-x,putchar('-');
	print(x);
	putchar(ch);
}
int rt[MAXN];
namespace Trie{
	struct node{
		int ch[2];
		int sz;
	}tree[MAXN<<5];
	#define ch(i,p) tree[i].ch[p]
	int tot;
	void Insert(int &i,int pre,int index,int x){
		tree[i=++tot].sz=tree[pre].sz;
		if (index<0){
			tree[i].sz++;
			return ;
		}
		bool pos=(x>>index)&1;
		ch(i,pos^1)=ch(pre,pos^1);
		Insert(ch(i,pos),ch(pre,pos),index-1,x);
		tree[i].sz=tree[ch(i,0)].sz+tree[ch(i,1)].sz;
	}
	int Query(int index,int l,int r,int x){
		if (index<0) return 0;
		bool pos=(x>>index)&1;
		int k=tree[ch(r,pos^1)].sz-tree[ch(l,pos^1)].sz;
		if (k>0){
			return Query(index-1,ch(l,pos^1),ch(r,pos^1),x)+(1<<index);
		}
		else {
			return Query(index-1,ch(l,pos),ch(r,pos),x);
		}
	}
}
using namespace Trie;
int a[MAXN];
int main(){
	int n=read(),m=read();
	for (register int i=1;i<=n;++i){
		a[i]=read();
	}
	for (register int i=1;i<=n;++i){
		Insert(rt[i],rt[i-1],31,a[i]);
	}
	for (register int i=1;i<=m;++i){
		int x=read(),l=read()+1,r=read()+1;
		Print(Query(31,rt[l-1],rt[r],x),'\n');
	}
}

例题2

P4735 最大异或和

A x：添加操作，表示在序列末尾添加一个数xx，序列的长度变为N+1N+1。

Q l r x：询问操作，你需要找到一个位置pp，满足l≤p≤rl \le p \le r，使得： a[p]⊕a[p+1]⊕...⊕a[N]⊕xa[p] \oplus a[p+1] \oplus ... \oplus a[N] \oplus x最大，输出最大是多少。

令sum[p]=a[1]⊕a[2]⊕...⊕a[p]sum[p]=a[1] \oplus a[2] \oplus ... \oplus a[p]。

考虑转换a[p]⊕a[p+1]⊕...⊕a[N]a[p] \oplus a[p+1] \oplus ... \oplus a[N]为sum[N]⊕sum[p−1]sum[N] \oplus sum[p-1]。

问题变为找到一个sum[p−1],(l≤p≤r)sum[p-1],(l \le p \le r)，使得(sum[N]⊕x)⊕sum[p−1](sum[N] \oplus x) \oplus sum[p-1]最大。

于是这个问题也可以可持久化trie解决。

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
#include <bits/stdc++.h>
#define MAXN 1000005
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while (ch<'0'||ch>'9'){
		if (ch=='-') f=-1;
		ch=getchar();
	}
	while (ch>='0'&&ch<='9'){
		x=(x<<3)+(x<<1)+(ch^'0');
		ch=getchar();
	}
	return x*f;
}
void print(int x){
	if (x>9) print(x/10);
	putchar('0'+x%10);
}
inline void Print(int x,char ch){
	if (x==0) return putchar('0'),putchar(ch),void();
	if (x<0) x=-x,putchar('-');
	print(x);
	putchar(ch);
}
int rt[MAXN];
namespace Trie{
	struct node{
		int ch[2];
		int sz;
	}tree[MAXN<<5];
	#define ch(i,p) tree[i].ch[p]
	int tot;
	void Insert(int &i,int pre,int index,int x){
		tree[i=++tot].sz=tree[pre].sz;
		if (index<0){
			tree[i].sz++;
			return ;
		}
		bool pos=(x>>index)&1;
		ch(i,pos^1)=ch(pre,pos^1);
		Insert(ch(i,pos),ch(pre,pos),index-1,x);
		tree[i].sz=tree[ch(i,0)].sz+tree[ch(i,1)].sz;
	}
	int Query(int index,int l,int r,int x){
		if (index<0) return 0;
		bool pos=(x>>index)&1;
		int k=tree[ch(r,pos^1)].sz-tree[ch(l,pos^1)].sz;
		if (k>0) return Query(index-1,ch(l,pos^1),ch(r,pos^1),x)+(1<<index);
		else return Query(index-1,ch(l,pos),ch(r,pos),x);
	}
}
using namespace Trie;
inline char gc(){
	char ch=getchar();
	while (ch!='A'&&ch!='Q') ch=getchar();
	return ch;
}
int a[MAXN];
int main(){
	int n=read(),m=read();
	for (register int i=1;i<=n;++i){
		a[i]=read()^a[i-1];
	}
	for (register int i=1;i<=n;++i){
		Insert(rt[i],rt[i-1],31,a[i]);
	}
	for (register int i=1;i<=m;++i){
		char ch=gc();
		if (ch=='A'){
			int x=read();
			a[n+1]=x^a[n];
			Insert(rt[n+1],rt[n],31,a[n+1]);
			++n;
		}
		else {
			int l=read()-1,r=read()-1,x=read();
			if (l==0&&l==r) Print(a[n]^x,'\n');//特判qwq
			else {
				if (!l) Print(Query(31,0,rt[r],x^a[n]),'\n');//这里也要
				else Print(Query(31,rt[l-1],rt[r],x^a[n]),'\n');
			}
		}
	}
}

例题3

P4098 [HEOI2013]ALO

枚举次小值a[i]a[i]，这题的重点是找到minl,maxrminl,maxr，使得a[i]a[i]是[minl,maxr][minl,maxr]中的次小值。

这个可以使用set或者平衡树或主席树之类的实现，也可以用双向链表O(n)O(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
#include <bits/stdc++.h>
#define MAXN 1000005
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while (ch<'0'||ch>'9'){
		if (ch=='-') f=-1;
		ch=getchar();
	}
	while (ch>='0'&&ch<='9'){
		x=(x<<3)+(x<<1)+(ch^'0');
		ch=getchar();
	}
	return x*f;
}
void print(int x){
	if (x>9) print(x/10);
	putchar('0'+x%10);
}
inline void Print(int x,char ch){
	if (x==0) return putchar('0'),putchar(ch),void();
	if (x<0) x=-x,putchar('-');
	print(x);
	putchar(ch);
}
int rt[MAXN];
namespace Trie{
	struct node{
		int ch[2];
		int sz;
	}tree[MAXN<<5];
	#define ch(i,p) tree[i].ch[p]
	int tot;
	void Insert(int &i,int pre,int index,int x){
		tree[i=++tot].sz=tree[pre].sz;
		if (index<0){
			tree[i].sz++;
			return ;
		}
		bool pos=(x>>index)&1;
		ch(i,pos^1)=ch(pre,pos^1);
		Insert(ch(i,pos),ch(pre,pos),index-1,x);
		tree[i].sz=tree[ch(i,0)].sz+tree[ch(i,1)].sz;
	}
	int Query(int index,int l,int r,int x){
		if (index<0) return 0;
		bool pos=(x>>index)&1;
		int k=tree[ch(r,pos^1)].sz-tree[ch(l,pos^1)].sz;
		if (k>0) return Query(index-1,ch(l,pos^1),ch(r,pos^1),x)+(1<<index);
		else return Query(index-1,ch(l,pos),ch(r,pos),x);
	}
}
using namespace Trie;
inline char gc(){
	char ch=getchar();
	while (ch!='A'&&ch!='Q') ch=getchar();
	return ch;
}
int a[MAXN],id[MAXN],pre[MAXN],nex[MAXN];
inline int cmp(int i,int j){
	return a[i]<a[j];
}
int L[MAXN],R[MAXN];
int main(){
	int n=read();
	for (register int i=1;i<=n;++i){
		a[i]=read(),pre[i]=i-1,nex[i]=i+1;
	}
	pre[0]=1,nex[n]=n;
	for (register int i=1;i<=n;++i){
		Insert(rt[i],rt[i-1],31,a[i]);
	}
	for (register int i=1;i<=n;++i){
		id[i]=i;
	}
	sort(id+1,id+1+n,cmp);
	for (register int i=1;i<=n;++i){
		nex[pre[id[i]]]=nex[id[i]];
		pre[nex[id[i]]]=pre[id[i]];
		L[id[i]]=pre[pre[id[i]]];
		R[id[i]]=nex[nex[id[i]]];
	}
	int ans=0;
	for (register int i=1;i<=n;++i){
		ans=max(ans,Query(31,rt[L[i]],rt[R[i]-1],a[i]));
	}
	printf("%d\n",ans);
}
相关文章
CF464E The Classic Problem 主席树LOJ #2402. 「THUPC 2017」天天爱射击 / ShootingP2839 [国家集训队]middle（可持久化线段树+二分）P3168 [CQOI2015]任务查询系统基本概念

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://gaisaiyuno.github.io/archives/af85b329.html

更新于：2022年6月20日

可持久化

trie

评论