可持久化0-1 Trie 简介
Trie树是字符串问题中应用极为广泛的一种数据结构,可以拓展出AC自动机、后缀字典树等实用数据结构。
然而在此我们考虑0-1 Trie的应用,即在序列最大异或问题中的应用。
这里的异或是指按位异或。按位异或有很多重要的性质。比如可拆分性,每个位可以进行单独处理后线性合并得到最终结果。
同时按位异或也是可减的。比如0111 ^ 1010 = 1101, 那么 1101 ^ 1010 = 0111. 证明从略。
首先我们考虑0-1 Trie的版本,也就是
给定一个序列a[i], 每次询问一个数x与a[i]中各元素能得到的按位异或的最大值。
暴力自然是O(n^2)的。但是我们想到之前的可拆分性,是否能将每个位单独考虑?但是,第一位的选择又会限定第二位的选择范围。即选择第一位是0或1后,第二位的选择就不能从a[i]中的所有元素中进行选择,而要将a[i]分为两份。我们很容易发现这是一个类似树形的问题,所以我们考虑使用树形数据结构。而鉴于多个串根据前缀进行选择性划分的特点,我们使用Trie树来从高位到低位地维护这些0-1串,即0-1 Trie。
注意到这种从高位到低位的选择一定是全局最优的。也就是说,对于异或结果,从高到低考虑,每一位能设成1就设成1. 证明可以利用反证法。
这样我们就利用一个贪心完成了这样的事情。这样的处理是O(n+m)的(常数有32倍)
什么时候需要使用可持久化0-1 Trie呢?我们想,在使用可持久化线段树维护区间K大值得时候,可持久化是否起到了限定区间的作用?同理,在这里,我们也是用可持久化来实现区间的限定。
重要性质:Trie树的节点存在性满足可减性。
我们可以把节点的存在性记录改为节点的数目记录,这样用root[r]中某节点的数目减去root[l-1]中某节点的数目,就可以得到区间中是否存在某个节点。
#include<bits/stdc++.h>
using namespace std; int ch[][],val[],cnt[],root[],ts[],ind,n,m; void insert(int p,int p0,int dep) {
ch[p][]=ch[p0][];
ch[p][]=ch[p0][];
if(dep==) return;
if(ch[p0][ts[dep+]]==) {
ch[p][ts[dep+]]=++ind;
val[ind]=ts[dep+];
cnt[ind]=;
insert(ind,ch[p0][ts[dep+]],dep+);
}
else {
ch[p][ts[dep+]]=++ind;
val[ind]=ts[dep+];
cnt[ch[p][ts[dep+]]]=cnt[ch[p0][ts[dep+]]]+;
insert(ch[p][ts[dep+]],ch[p0][ts[dep+]],dep+);
}
} void trie_insert(int rtx,int num) {
for(int i=;i<=;i++)
ts[i]=(num>>(-i))&;
insert(root[rtx],root[rtx-],);
} int xormax(int rtx,int rty,int num) {
int p=root[rtx], q=root[rty], ans=;
for(int i=;i>=;i--) {
if((num>>i)&) {
if(cnt[ch[q][]]-cnt[ch[p][]]) ans=ans*+, p=ch[p][], q=ch[q][];
else ans=ans*, p=ch[p][], q=ch[q][];
}
else {
if(cnt[ch[q][]]-cnt[ch[p][]]) ans=ans*+, p=ch[p][], q=ch[q][];
else ans=ans*, p=ch[p][], q=ch[q][];
}
}
return ans;
} int main() {
cin>>n;
for(int i=;i<=n;i++) {
int t;
cin>>t;
root[i]=++ind;
trie_insert(i,t);
}
cin>>m;
for(int i=;i<=m;i++) {
int t1,t2,t3;
cin>>t1>>t2>>t3;
t1--;
cout<<xormax(t1,t2,t3)<<endl;
}
}
最新文章
- 关于安卓APP的启动界面
- 2.4使用属性在 ASP.NET Web API 2 路由创建一个 REST API
- Install latest R for ubuntu
- MAC上python+Eclipse+pydev环境搭建
- PHP的加密解密字符串函数
- [快速数论变换 NTT]
- codereview
- 对于java反射的理解
- ACCESS-delphi向中插入一条记录报错,但ACCESS不会
- C++ 约瑟夫环
- webuploader限制只上传图片文件
- ps-色彩饱和度的设计
- mysql5.7在windows不能启动的方法及查看数据库大小命令
- Alpha冲刺(4/10)——2019.4.26
- 《Serverless架构-无服务单页应用开发》读后感
- Android数据保存之SharedPreference
- 通用权限管理系统多语言开发标准接口 - java,php 调用标准接口程序参考
- xcode 编译或者打包的时候 找不到图片的错误
- docker 基本操作
- 第三百六十八节,Python分布式爬虫打造搜索引擎Scrapy精讲—elasticsearch(搜索引擎)用Django实现搜索的自动补全功能