精华内容
下载资源
问答
  • 可持久化数据结构

    2020-11-27 21:35:52
    文章目录可持久化数据结构两句闲话可持久化 TrieTrieTrie实现例题可持久化线段树(主席树)实现例题 可持久化数据结构 两句闲话 可持久化的前提:该数据结构本身的拓扑结构在操作时保持不变 常见的可持久化:堆,线段树,...

    可持久化数据结构


    两句闲话

    可持久化的前提:该数据结构本身的拓扑结构在操作时保持不变

    常见的可持久化:堆,线段树,树状数组,trietrie\dots

    常见的不支持持久化:平衡树…

    那么可持久化能解决什么问题呢?

    • 保存数据结构的所有历史版本 git

    暴力备份?肯定不行 MLE+TLE

    类似于git,可持久化数据结构只会记录每一个版本和前一个版本不一样的地方

    以线段树为例,每次操作最多改变了$4logn $个节点,复杂度就成了 O(mlogn)O(mlogn) 级别

    可持久化 TrieTrie

    实现

    先放图:

    在这里插入图片描述

    比较值得注意的一点:每次记录和上一版本的不同

    若是该节点有变化,就把他裂开(克隆),裂开一个新的路径

    对于插入操作:

    p=root[i-1];

    先让指针指向上一个版本

    q=root[i]=++idx;

    开个节点

    if(!p)那么说明了 pp 是一个船新节点,与前一个版本一点关系都没有

    if(p)和上一个版本有关系,克隆下来:tr[q]=tr[p],裂开,指过去

    tr[q][si]=++idx

    p=tr[p][si],q=tr[q][si]

    然后接着搞

    例题

    P4735最大异或和

    首先搞个前缀和:

    $S_0=0,s_1=A_1,s_2=A_1\oplus A_2,s_3=A_1 \oplus A_2 \oplus A_3,\dots $

    那么 ApAp+1AnxA_p \oplus A_{p+1} \dots A_n \oplus x \Longleftrightarrow Sp1SnxS_{p-1} \oplus S_n \oplus x

    目标,在区间内找到一个 pp 使上面这个式子最大

    c=Snxc=S_n \oplus x

    要找到 Sp1cS_{p-1} \oplus c 最大

    c=110010101...c=110010101...

    我们从首位向后枚举,是0尽量选1,是1尽量选0,这样就最大了

    考虑用 trietrie 来维护

    若考虑在 [1,R][1,R] 中选,可以用可持久化 trietrie 记录下每个历史版本

    这样这棵树就存下了1~R 中的每个数的前缀和(历史版本)

    若限制变成了 [L,R][L,R] 那么我们在搜的时候,相当于问我们选的子树中,是否至少存在一个数,大于等于 LL

    \Longleftrightarrow 左子树下标最大值是否大于等于 L

    于是我们可以记录一个maxid,记录当前子树下标的最大值

    每次递归用maxid和L比

    然后就行了吧

    代码:

    /*************************************************************************
        > File Name: p4735鏈€澶у紓鎴栧拰.cpp
        > Author: typedef
        > Mail: 1815979752@qq.com 
        > Created Time: 2020/11/25 22:38:07
     ************************************************************************/
    #include<bits/stdc++.h>
    using namespace std;
    const int N=6e5+7,M=N*25;
    int n,m;
    int tr[M][2],maxid[M];
    int root[N];
    int s[N];
    int idx=0;
    void insert(int i,int k,int p,int q){//i鏄墠缂€鍜屼笅鏍噋鏄笂涓€涓増鏈?q鏄柊鐨勭増鏈琸鏄綋鍓嶅鐞嗗埌绗嚑浣?
    	if(k<0){
    		maxid[q]=i;
    		return;
    	}
    	int v=s[i]>>k&1;//褰撳墠浣?
    	if(p) tr[q][v^1]=tr[p][v^1];//璇存槑q鏄痯鐨勫鍒?
    	tr[q][v]=++idx;
    	insert(i,k-1,tr[p][v],tr[q][v]);
    	maxid[q]=max(maxid[tr[q][0]],maxid[tr[q][1]]);
    	return;
    }
    int query(int root,int c,int l){
    	int p=root;
    	for(int i=23;i>=0;i--){
    		int v=c>>i&1;
    		if(maxid[tr[p][v^1]]>=l) p=tr[p][v^1];
    		else p=tr[p][v];
    	}
    	return c^s[maxid[p]];
    }
    int main(){
    	scanf("%d%d",&n,&m);
    	maxid[0]=-1;
    	root[0]=++idx;
    	insert(0,23,0,root[0]);
    	for(int i=1;i<=n;i++){
    		int x;
    		scanf("%d",&x);
    		s[i]=s[i-1]^x;
    		root[i]=++idx;
    		insert(i,23,root[i-1],root[i]);
    	}
    	char op[2];
    	int l,r,x;
    	while(m--){
    		scanf("%s",op);
    		if(*op=='A'){
    			scanf("%d",&x);
    			n++;
    			s[n]=s[n-1]^x;
    			root[n]=++idx;
    			insert(n,23,root[n-1],root[n]);
    		}
    		else{
    			scanf("%d%d%d",&l,&r,&x);
    			printf("%d\n",query(root[r-1],s[n]^x,l-1));
    		}
    	}
    	system("pause");
    	return 0;
    }
    

    可持久化线段树(主席树)

    实现

    思想类似于可持久化 trietrie 每次修改存下新的版本,只存下变化的地方

    如果说某一次修改导致一些节点发生了变化,那么久存下来

    没有变化的节点就不用了

    struct president_tree{
        int l,r;//表示左右子节点的下标
        int cnt;//当前区间中一共有多少个数   
    }
    

    主席树难以进行区间修改操作,毕竟标记下传太难写了,而且会T掉

    标记永久化?我不会QAQQAQ

    放个图:

    在这里插入图片描述

    基本没啥区别吧

    例题

    P3834 【模板】可持久化线段树 2

    特点:静态问题

    经典做法:划分树(好像只能解决区间第K小 O(nlogn)O(nlogn) ) , 树套树(线段树套平衡树 套set(支持修改操作O(nlog2n))O(nlog^2n)),还有就是可持久化线段树 O(nlogn)O(nlogn)

    数据比较大,由于只是查询排名,我们可以搞一个离散化

    我们可以在数值上建立线段树,维护每个数值区间中一共有多少个数

    那么问题来了,如何求整体的第k小数?

    我们可以把二分做到树里面去

    0          mid         n-1
    |-----------|-----------|
    首先查询[0,mid] 
    得到cnt
    cnt>=k?递归左边:递归右边
    复杂度 O(logn)
    

    那么如果加了限制 [l,r][l,r] 该怎么办呢?

    先考虑 [1,r][1,r]

    我们记录下从加上第一个数到第 r 个数的线段树的历史版本

    root[R]表示只加前 r 个数的线段树

    那么再考虑左端点

    主席树有个很好的性质,每一颗树的结构都是一样的

    因此每个树中,每个节点都能与另一个版本的这个节点对应(一一对应)

    因此可以利用一个类似前缀和的性质

    同时二分左端点和右端点

    代码:

    /*************************************************************************
        > File Name: p3834[妯℃澘]鍙寔涔呭寲绾挎鏍?.cpp
        > Author: typedef
        > Mail: 1815979752@qq.com 
        > Created Time: 2020/11/27 19:58:02
     ************************************************************************/
    #include<bits/stdc++.h>
    using namespace std;
    const int N=200010,M=20010;
    int n,m;
    int a[N];
    vector<int> nums;
    struct node{
    	int l,r;
    	int cnt;
    }tr[N*4+N*17];
    int root[N],idx;
    int find(int x){
    	//杩斿洖鍘熸暟鐨勭鏁e€?
    	return lower_bound(nums.begin(),nums.end(),x)-nums.begin();
    }
    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 insert(int p,int l,int r,int x){//p鏄巻鍙茬増鏈殑绾挎鏍?l鏄尯闂村乏绔偣,r鏄尯闂村彸绔偣,x鏄鍔犲叆鐨勬暟
    	//鏂板缓涓€棰楃嚎娈垫爲
    	int q=++idx;
    	tr[q]=tr[p];//澶嶅埗
    	if(l==r){
    		tr[q].cnt++;
    		return q;
    	}
    	int mid=l+r>>1;
    	//鍒ゆ柇鍝釜瀛愯妭鐐瑰彂鐢熶簡鍙樺寲
    	if(x<=mid) tr[q].l=insert(tr[p].l,l,mid,x);
    	else tr[q].r=insert(tr[p].r,mid+1,r,x);
    	//update
    	tr[q].cnt=tr[tr[q].l].cnt+tr[tr[q].r].cnt;
    	return q;
    }
    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);
    }
    int main(){
    //	freopen("testin.txt","r",stdin);
    //	freopen("testout.txt","w",stdout);
    	scanf("%d%d",&n,&m);
    	for(int i=1;i<=n;i++){
    		scanf("%d",&a[i]);
    		nums.push_back(a[i]);
    	}
    	sort(nums.begin(),nums.end());
    	nums.erase(unique(nums.begin(),nums.end()),nums.end());
    	root[0]=build(0,nums.size()-1);
    	for(int i=1;i<=n;i++) root[i]=insert(root[i-1],0,nums.size()-1,find(a[i]));
    	while(m--){
    		int l,r,k;
    		scanf("%d%d%d",&l,&r,&k);
    		printf("%d\n",nums[query(root[r],root[l-1],0,nums.size()-1,k)]);
    	}
    	system("pause");
    	return 0;
    }
    
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,284
精华内容 1,313
关键字:

可持久化数据结构

数据结构 订阅