网站开发是做什么?,网站建设百度百科,深圳十大穷人区,个人网站的域名注册参考博客 可持久化数据结构#xff1a;可以保留每一个历史版本#xff0c;若所有版本都既可以访问又可以修改#xff0c;成为完全可持久化#xff08;可以回滚到某个历史版本#xff09; 时间线#xff1a;
可持久化线段树
可持久化下标线段树
题目#xff1a;
模板…参考博客 可持久化数据结构可以保留每一个历史版本若所有版本都既可以访问又可以修改成为完全可持久化可以回滚到某个历史版本 时间线
可持久化线段树
可持久化下标线段树
题目
模板 可持久化数组 你需要维护一个长度为N的数组支持如下几种操作 1.在某个历史版本上修改某一个位置上的值 2.访问某个历史版本的某一位置的值
做法
用下标线段树维护一个数组对于每个版本建一棵线段树-空间O(QN) 用可持久化的思想进行优化 当a[id]的值发生改变时会影响从根[1,N]–叶子[id,id]这条链上的所有点其他点不会被影响受影响的点只有logN个所有我们没必要单独再建一个线段树可以只建新版本的logN个点其他点与老版本共用 如图当a[1]发生修改时的情况 这样我们既保存了旧版本又存下新版本根节点1白色对应旧版本根节点1红色对应新版本这样保存下所有历史版本而且空间得到优化 空间O(logN) 时间O(logN) 增加边复杂度为常数
赋值节点的操作
赋值节点时直接用赋值运算符
int clone(int rt){top;tr[top]tr[rt];return top;
}int update(int rt,int l,int r,int pos,int val){rtclone(rt);if(lr){tr[rt].valval;return rt;}int mid(lr)1;if(posmid)tr[rt].lupdate(tr[rt].l,l,mid,pos,val);else tr[rt].rupdate(tr[rt].r,mid1,r,pos,val);return rt;
}完整代码 改成我自己风格的可持久化
#includebits/stdc.h
#define debug(a,b) printf(%s %d\n,a,b);
using namespace std;
typedef long long ll;
typedef pairint, int PII;
//Fe~Jozky
const ll INF_ll1e18;
const int INF_int0x3f3f3f3f;
inline ll read(){ll s0,w1ll;char chgetchar();while(ch0||ch9){if(ch-)w-1ll;chgetchar();}while(ch0ch9) ss*10ll((ch-0)*1ll),chgetchar();//s(s3)(s1)(ch^48);return s*w;
}
void rd_txt(){#ifdef ONLINE_JUDGE#elsefreopen(in.txt,r,stdin);#endif
}
const int maxn1e69;
int a[maxn];
int top0;
struct tree{int l,r,val;
}tr[maxn*30];
int clone(int rt){top;tr[top]tr[rt];return top;
}
int build(int rt,int l,int r){rttop;if(lr){tr[rt].vala[l];return rt;}int mid(lr)1;tr[rt].lbuild(tr[rt].l,l,mid);tr[rt].rbuild(tr[rt].r,mid1,r);return rt;
}
int update(int rt,int l,int r,int pos,int val){rtclone(rt);if(lr){tr[rt].valval;return rt;}int mid(lr)1;if(posmid)tr[rt].lupdate(tr[rt].l,l,mid,pos,val);else tr[rt].rupdate(tr[rt].r,mid1,r,pos,val);return rt;
}
int query(int rt,int l,int r,int x){if(lr)return tr[rt].val;int midlr1;if(xmid)return query(tr[rt].l,l,mid,x);else return query(tr[rt].r,mid1,r,x);
}
int Root[maxn];
int main()
{rd_txt();int n,m;scanf(%d%d,n,m);for(int i1;in;i){scanf(%d,a[i]);}Root[0]build(0,1,n);for(int i1;im;i){int rt,mode,x;scanf(%d%d%d,rt,mode,x);if(mode1){int y;scanf(%d,y);Root[i]update(Root[rt],1,n,x,y);}else {printf(%d\n,query(Root[rt],1,n,x));Root[i]Root[rt];}}
}
