【洛谷P3919】【模板】可持久化数组【主席树】
题目大意：
题目连接：https://www.luogu.org/problemnew/show/P3919
如题，你需要维护这样的一个长度为的数组，支持如下几种操作
- 在某个历史版本上修改某一个位置上的值
- 访问某个历史版本上的某一位置的值
此外，每进行一次操作（对于操作2，即为生成一个完全一样的版本，不作任何改动），就会生成一个新的版本。版本编号即为当前操作的编号（从1开始编号，版本0表示初始状态数组）
思路：
主席树模板题。
主席树的题目大多是单点修改的。当我们需要支持访问历史版本时，最简单的方法是新建一棵线段树。
但是这样的内存会爆炸的。
我们发现，由于只要单点修改，所以我们需要修改的就只有这个节点以及他的祖宗，其他点就是根本不用修改的，所以如果我们可以只修改需要修改的点，其他点直接连向原本线段树的点，就可以大大压缩空间。虽然这样空间复杂度还是会很高
假设我们有一棵这样的线段树
其中分别表示左儿子和右儿子。
此时如果我们需要修改点10，就可以得到下面这样一棵主席树
注意节点13,14的左儿子和右儿子的位置还是不变的。
此时如果我们需要访问历史版本0，就从根节点1为的主席树找，如果要访问历史版本1，就从根及诶单为12的主席树找。
这样的时间复杂度是，空间复杂度是。
为了节省空间，主席树的区间表示不再在结构体中记录，而是使用递归参数来传递。
代码：
#include <cstdio>
using namespace std;
const int N=1e6+10;
const int M=N+20*N;
int n,m,a[N],root[N],tot,s,k,val,x;
struct Tree
{
int ls,rs,a;
}tree[M*2];
int build(int l,int r)
{
int p=++tot; //记录节点编号
if (l==r) tree[p].a=a[l]; //记录这个点的值
else
{
int mid=(l+r)/2;
tree[p].ls=build(l,mid); //左子树
tree[p].rs=build(mid+1,r); //右子树
}
return p;
}
int change(int now,int l,int r,int k,int val) //修改
{
int p=++tot;
tree[p]=tree[now]; //复制一份过来
if (l==r) tree[p].a=val;
else
{
int mid=(l+r)/2;
if (k<=mid) tree[p].ls=change(tree[now].ls,l,mid,k,val); //修改左子树
else tree[p].rs=change(tree[now].rs,mid+1,r,k,val); //修改右子树
}
return p;
}
int ask(int now,int l,int r,int k) //查询
{
int p=++tot;
tree[p]=tree[now];
if (l==r) printf("%d\n",tree[p].a); //找到就输出
else
{
int mid=(l+r)/2;
if (k<=mid) tree[p].ls=ask(tree[now].ls,l,mid,k); //查询左子树
else tree[p].rs=ask(tree[now].rs,mid+1,r,k); //查询右子树
}
return p;
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
root[0]=build(1,n); //root[i]表示历史版本i的根
for (int i=1;i<=m;i++)
{
scanf("%d%d",&s,&x);
if (x==1)
{
scanf("%d%d",&k,&val);
root[i]=change(root[s],1,n,k,val);
}
else
{
scanf("%d",&k);
root[i]=ask(root[s],1,n,k);
}
}
return 0;
}
1、ORACLE SQL效率 理论部分
2、docker 查看容器信息---格式化
3、pl/sql插入报错
4、用Python做一个翻译软件
5、Java并发编程：synchronized（转载）