首页 > 其他分享 >可持久化数据结构

可持久化数据结构

时间：2025-01-02 22:09:11浏览次数：1  
标签：持久 val rs int tree ls 数据结构

可持久化平衡树

复习了一下fhq。

普通可持久化平衡树

和主席树类似地，可持久化数据结构的精髓在于对每次进行次数为 \(polylog\) 级别的操作进行重开点，以此用尽可能小的时空损耗来保存每次操作完的全树状态。国内常用的可持久化平衡树是fhq，容易想到地，就是将它的split和merge操作进行可持久化。

	inline int merge(int x,int y){
		if(!x||!y)return x^y;
		if(tree[x].key<tree[y].key){
			int p=newnode();
			tree[p]=tree[x];
			rs(p)=merge(rs(p),y);
			update(p);
			return p;
		}
		else{
			int p=newnode();
			tree[p]=tree[y];
			ls(p)=merge(x,ls(p));
			update(p);
			return p;
		}
	}
	inline void split(int p,int k,int &x,int &y){
		if(!p){
			x=y=0;
			return ;
		}
		if(tree[p].val<=k){
			x=newnode();
			tree[x]=tree[p];
			split(rs(x),k,rs(x),y);
			update(x);
		}
		else{
			y=newnode();
			tree[y]=tree[p];
			split(ls(y),k,x,ls(y));
			update(y);
		}
	}

再用 \(rt\) 数组存一下每个版本的起始根就好了。

文艺可持久化平衡树

带着区间（反转）tag的平衡树要求在所有“从上到下”类型的操作中进行下传，进而把下传操作放到merge和split里，同时进行可持久化。

	inline int merge(int x,int y){
		if(!x||!y)return x^y;
		spread(x);
		spread(y);
		if(tree[x].key<tree[y].key){
			rs(x)=merge(rs(x),y);
			update(x);
			return x;
		}
		else{
			ls(y)=merge(x,ls(y));
			update(y);
			return y;
		}
	}
	inline void split(int p,ll val,int &x,int &y){
		if(!p){
			x=y=0;
			return ;
		}
		spread(p);
		if(tree[ls(p)].siz<val){
			x=copy(p);
			split(rs(x),val-tree[ls(p)].siz-1,rs(x),y);
			update(x);
		}
		else{
			y=copy(p);
			split(ls(y),val,x,ls(y));
			update(y);
		}
	}

Rikka with Sequence

严厉谴责学校题单前一题还在板子后一题直接拉泡大的的罪恶行为。

发现后两个操作很有想象力，而且本题以足足64mb的空间限制被放入了一个可持久化数据结构题单中，太菜了于是果断被击败并查看题解。

先不管神秘的空间限制，对于操作二，相当于是取k个元素循环地填充满区间，可以考虑倍增地merge那k个元素所属的区间直到装不下，这个时候拆一段长度匹配的散块即可，这一过程有大量的重复节点，就可以用可持久化平衡树，对于操作三，可以在一开始建立rt0的可持久化树，每次操作3直接把当前根1的那段区间赋值成0的那一部分即可。

理想很美好，但是操作2中的复制操作会复制大量同样的fhq中的随机平衡因子key，这样我们直接就平衡了个寂寞。题解提出合并时用随机值判断：让子树大小大的成为父亲的概率高一些，能相对平衡一些。

	inline void split(int p,int k,int &x,int &y){
		if(!p){
			x=y=0;
			return ;
		}
		if(tree[ls(p)].siz+1<=k){
			x=newnode();
			tree[x]=tree[p];
			split(rs(x),k-tree[ls(p)].siz-1,rs(x),y);
			update(x);
		}
		else{
			y=newnode();
			tree[y]=tree[p];
			split(ls(y),k,x,ls(y));
			update(y);
		}
	}
	inline int merge(int x,int y){
		if(!x||!y)return x^y;
		if(rnd()%(tree[x].siz+tree[y].siz)<tree[x].siz){
			int p=newnode();
			tree[p]=tree[x];
			rs(p)=merge(rs(p),y);
			update(p);
			return p;
		}
		else{
			int p=newnode();
			tree[p]=tree[y];
			ls(p)=merge(x,ls(p));
			update(p);
			return p;
		}
	}

大概就是上面这个样子。

但是空间问题还没解决！所以提出：每当节点个数超过一半的空间最大值就直接暴力重构，这样好像很大的时间限制就说的通了。放一下全代码。

#include<bits/stdc++.h>
#define MAXN 200005
#define MAXM 2000005
#define LIM 1000000
#define ll long long
using namespace std;
int n,m,mem;
const int inf=2e9;
int a[MAXN],top;
mt19937 rnd(time(0));
struct FHQ_Treap{
	#define ls(p) tree[p].lson
	#define rs(p) tree[p].rson
	struct node{
		int lson,rson;
		ll sum;
		int val,siz;
	}tree[MAXM];
	inline void update(int p){
		tree[p].siz=tree[ls(p)].siz+tree[rs(p)].siz+1;
		tree[p].sum=tree[ls(p)].sum+tree[rs(p)].sum+tree[p].val;
	}
	int tot,rt[2];
	inline int newnode(ll val=0){
		tree[++tot].val=val;
		tree[tot].sum=val;
		tree[tot].siz=1;
		ls(tot)=rs(tot)=0;
		return tot;
	}
	inline void split(int p,int k,int &x,int &y){
		if(!p){
			x=y=0;
			return ;
		}
		if(tree[ls(p)].siz+1<=k){
			x=newnode();
			tree[x]=tree[p];
			split(rs(x),k-tree[ls(p)].siz-1,rs(x),y);
			update(x);
		}
		else{
			y=newnode();
			tree[y]=tree[p];
			split(ls(y),k,x,ls(y));
			update(y);
		}
	}
	inline int merge(int x,int y){
		if(!x||!y)return x^y;
		if(rnd()%(tree[x].siz+tree[y].siz)<tree[x].siz){
			int p=newnode();
			tree[p]=tree[x];
			rs(p)=merge(rs(p),y);
			update(p);
			return p;
		}
		else{
			int p=newnode();
			tree[p]=tree[y];
			ls(p)=merge(x,ls(p));
			update(p);
			return p;
		}
	}
	int x,y,z,w;
	inline ll query(int &p,int l,int r){
		x=y=z=0;
		split(p,l-1,x,y);
		split(y,r-l+1,y,z);
		ll res=tree[y].sum;
		p=merge(x,merge(y,z));
		return res; 
	}
	inline void modify(int &p,int l,int r,int k){
		x=y=z=w=0;
		split(p,r,x,z);
		split(x,l-k-1,x,y);
		split(y,k,y,p);
		int tar=r-l+1+k;
		while(tree[y].siz<=tar)y=merge(y,y);
		int bin=0;
		split(y,r-l+1+k,y,bin);
		p=merge(x,merge(y,z));
	}
	inline void reset(int &p,int l,int r){
		x=y=z=0;
		split(rt[0],l-1,x,y);
		split(y,r-l+1,y,z);
		x=z=0;
		int bin=0;
		split(p,l-1,x,bin);
		split(bin,r-l+1,bin,z);
		p=merge(x,merge(y,z));
	}
	inline void build(int l,int r,int &p){
		if(l>r){
			p=0;
			return ;
		}
		int mid=l+r>>1;
		p=newnode(a[mid]);
		build(l,mid-1,ls(p));
		build(mid+1,r,rs(p));
		update(p);
	}
	inline void dfs(int p){
		if(!p)return ;
		if(ls(p))dfs(ls(p));
		a[++top]=tree[p].val;
		if(rs(p))dfs(rs(p));
	}
	inline void reconstruct(){
		top=0;
		dfs(rt[1]);
		tot=mem;
		build(1,n,rt[1]);
	}
}BT;
signed main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	BT.build(1,n,BT.rt[0]);
	mem=BT.tot;
	BT.rt[1]=BT.rt[0];
	for(int i=1,opt,l,r,k;i<=m;i++){
		scanf("%d%d%d",&opt,&l,&r);
		if(opt==1)printf("%lld\n",BT.query(BT.rt[1],l,r));
		else if(opt==2){
			scanf("%d",&k);
			BT.modify(BT.rt[1],l,r,k);
		}
		else BT.reset(BT.rt[1],l,r);
		if(BT.tot>LIM)BT.reconstruct();
	}
	return 0;
}

好像这类题不是特别多，遇见了再记录吧。

可持久化Trie

这个还挺简单的，而且相当好用，主要的应用是解决区间而非全局异或问题。

这是一份可持久化01trie的板子，会主席树基本就可以自研了。

struct Trie{
	#define ls(p) tree[p][0]
	#define rs(p) tree[p][1]
	int tree[MAXN*33][2],cnt[MAXN*33];
	int tot,rt[MAXN];
	inline void insert(int p,int pre,int val){//基于上个版本pre建立新版本p
		for(int i=30;i>=0;i--){
			cnt[p]=cnt[pre]+1;
			if((val>>i)&1){
				if(!rs(p))rs(p)=++tot;
				ls(p)=ls(pre);
				p=rs(p),pre=rs(pre);
			}
			else{
				if(!ls(p))ls(p)=++tot;
				rs(p)=rs(pre);
				p=ls(p),pre=ls(pre);
			}
		}
		cnt[p]=cnt[pre]+1;//记得跳到叶子也要加一下
	}
	inline int query(int x,int y,int val){//查区间lr内元素异或val的最大值
		int res=0;
		for(int i=30;i>=0;i--){
			int k=(val>>i)&1;
			if(cnt[tree[y][!k]]-cnt[tree[x][!k]]){
				res+=(1<<i);
				x=tree[x][!k];
				y=tree[y][!k];
			}
			else x=tree[x][k],y=tree[y][k];
		}
		return res;
	}
}Tr;

ALO

贪心地想：如果已经确定一个元素在这个区间是次大值，那对于这个元素肯定区间越大越好！可以单调栈跑出来每个元素左右侧第一个大于它的元素，并基于那个下标继续二分答案扩张（这样其实也就不用单调栈了），最后会生成两个它作为次大值的区间，于是对于每个 \(a_i\)：

\[Ans=\max_{i=1}^{n}max(a_i\oplus f(L_{i,0},R_{i,0}),a_i\oplus f(L_{i,1},R_{i,1})) \]

其中 \(f(l,r)\) 是区间 \(l,r\) 内异或 \(a_i\) 最大的值，单次可以拿01Trie在 \(O(logV)\) 复杂度求出，用可持久化Trie实现。

最大异或和

如果有动态添加的话，就可以直接考虑可持久化Trie了，然后观察一下询问是一个后缀和的性质，转化为求:

\[i\in[l,r],\max sum_n\oplus x\oplus sum_{i-1} \]

\(sum_i\) 表示前缀异或和。其中式子前两部分是定值，第三部分用可持久化Trie求解。

FOTILE模拟赛L

\(n,m\) 都很小啊！，考虑与处理一下答案，给数列分块，设 \(sav_{l,r}\) 表示从第 \(l\) 个块到第 \(r\) 个元素间的最优解，这个是可以 \(O(n\sqrt n)\) 与处理的。对于每次询问，剩下的散块相当于询问长 \(O(\sqrt n)\) 的区间 \([l,r']\) 中的左端点和 \([l,r]\) 的右端点的最大子段异或和，忽视左右的影响，改成前缀异或和的形式然后拿可持久化Trie处理。

字符串树

没啥说的，和树上主席树一个套路。

Xor

看起来很树剖啊！考虑用树剖的简化思想——dfs序解决问题，跑出dfs序然后对它建立可持久化Trie，则子树查询就是一个dfn区间，而路经查询就是若干个重链。

思路很简单但是写的时候不要犯迷糊了，转移到序列上就和树上父亲没关系了。

正在施工。

标签：持久,val,rs,int,tree,ls,数据结构
From： https://www.cnblogs.com/Claimo0611/p/18648824

相关文章

  • 数据结构与算法学习笔记----快速幂
    数据结构与算法学习笔记----快速幂@@author:明月清了个风@@firstpublishtime:2025.1.2ps⭐️快速幂的两道模版题，快速幂，乘法逆元，费马小定理Acwing875.快速幂[原题链接](875.快速幂-AcWing题库)给定n......
  • 数据结构：串
    文章目录串的基本概念串的相关操作串的代码与运行结果串的基本概念1.串长：串的长度（字符个数）称作串长。2.空串：长度为0的字符串。3.主串：包含所有子串的串为主串。4.子串：串中任意连续的字符组成的子序列称为该串的子串。串的相关操作串的操作有生成串，复制串，串连接，......
  • 【初阶数据结构与算法】排序算法总结篇(每个小节后面有源码)（直接插入、希尔、选择、堆
    文章目录一、直接插入排序二、希尔排序三、直接选择排序四、堆排序五、冒泡排序六、快速排序七、归并排序八、计数排序九、非递归快速排序十、非递归归并排序本篇内容将从稳定性与复杂度等角度分析排序算法，列出它们的特点、优点以及缺点，希望大家有所收获，如果想更加细......
  • [数据结构学习笔记2] 大O法表示程序的时间复杂度
    程序运行都是需要时间的，我们用大O法来表示，程序在最坏情况下，运行时间和输入规模的关系。一般有这么几种大O时间：快：闪电：O(1)-常量复杂度-和输入无关；比如通过数组下标访问元素；简单数学运算，如看末尾数字是否是基数；火箭：O(logn)-对数复杂度-时间增长随数字规模增长缓慢；这种......
  • [数据结构学习笔记1] 为什么需要有数据结构
    程序本质上就是用来读取数据，然后操作数据，最后生成数据的。如果数据能被有效，或者有结构的展现，那将极大方便程序操作。举例：我们家里有很多工具，剪刀，锤子，斧头，扳手，放大镜，六角扳手，螺丝刀，尺子，卷尺，螺丝，便利贴等等。我们可以怎样收纳这些工具，使得我们后续可以方便的使用呢？第一种，我们家有......
  • Java-数据结构-包装类与泛型
    一、包装类Java的包装类指的是将基本数据类型（如int、float、boolean等）封装成对象的类。Java中的8个基本数据类型（byte、short、int、long、float、double、char、boolean）都有对应的包装类。①基本数据类型对应的包装类基本数据类型包装类byteByteshortShortintIntegerlongLo......
  • 【数据结构】线性表
    目录线性表的定义及特点线性表的特点线性数据结构的特点线性表的定义顺序表定义和初始化操作存储方式初始化操作 其他操作查找插入删除 应用（合并操作）集合的合并操作两个顺序表的合并操作 链表单链表 定义及存储表示其他操作 创建前插法后插法 查......
  • 数据结构复习 (顺序查找,对半查找,斐波那契查找,插值查找,分块查找)
    查找（检索）：定义：从给定的数据中找到对应的K1，顺序查找：O(n)的从前向后的遍历2，对半查找，要求有序从中间开始查找，每次检查中间的是否正确，不正确就根据性质去左边or右边找2.1对半插入排序在找位置的时候是logn去找，但是最后需要换位置排序之后仍然是O()N^2)对同一序列分别......
  • 数据结构复习 (二叉查找树,高度平衡树AVL)
    1.二叉查找树:为了更好的实现动态的查找(可以插入/删除),并且不超过logn的时间下达成目的定义:二叉查找树（亦称二叉搜索树、二叉排序树）是一棵二叉树，其各结点关键词互异，且中根序列按其关键词递增排列。等价描述:二叉查找树中任一结点P，其左子树中结点的关键词都小于P的关键词......
  • 数据结构与算法Python版 拓扑排序与强连通分支
    文章目录一、图的应用-拓扑排序二、图的应用-强连通分支一、图的应用-拓扑排序拓扑排序TopologicalSort从工作流程图得到工作次序排列的算法，称为“拓扑排序”拓扑排序处理一个有向无环图DAG，输出顶点的线性序列。使得两个顶点v,w，如果图中有(v,w)边，在线性序列中v就......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99