欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

可持久化数组

程序员文章站 2024-03-04 12:13:29
...
/*
可持久化数组
操作1:修改某历史版本的某一位置的元素
操作2:查询某历史版本的某一位置的元素
每次操作后都会有新的版本
实现上还是采用主席树
用线段树维护一个数组 
主席树则维护了每个版本的线段树 
动态开点,每个版本复制修改前的版本,只修改要修改的部分,空间为log 
*/ 


#include <iostream>
using namespace std;

const int maxn = 1e6 + 5;

int a[maxn],root[maxn],cnt;
struct node{
	int l,r,val;   //左右儿子节点编号和节点的值 
}hjt[maxn*40];

void build(int l,int r,int &now)
{
	now = ++cnt;   //记录当前编号 
	if( l == r )   //由于维护的是一个数组,所以只需要根节点存值即可 
	{
		hjt[now].val = a[l];
		return;
	}
	int m = ( l + r ) >> 1;
	build(l,m,hjt[now].l);
	build(m+1,r,hjt[now].r);   //传引用自然就确定了左右儿子编号 
}

void modify(int l,int r,int ver,int &now,int loc,int p)  //当前区间为[l,r],版本为ver,当前版本为now,修改位置loc为p 
{
	now = ++cnt;
	hjt[now] = hjt[ver];   //先复制,然后修改要改的 
	if( l == r )   //到叶子节点,进行修改 
	{
		hjt[now].val = p;
		return;
	}
	int m = ( l + r ) >> 1;
	if( loc <= m ) modify(l,m,hjt[ver].l,hjt[now].l,loc,p);  //选择去左还是右 
	else modify(m+1,r,hjt[ver].r,hjt[now].r,loc,p);
}

int query(int l,int r,int now,int loc)  //当前区间为[l,r],查询now版本第loc的位置的元素 
{
	if( l == r ) return hjt[now].val;   //正常的线段树查询 
	int m = ( l + r ) >> 1;
	if( loc <= m ) return query(l,m,hjt[now].l,loc);
	else return query(m+1,r,hjt[now].r,loc); 
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n,m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	build(1,n,root[0]);
	for (int i = 1; i <= m; i++)
	{
		int ver,kind,loc;
		cin >> ver >> kind >> loc;
		if( kind == 1 )
		{
			int x;
			cin >> x;
			modify(1,n,root[ver],root[i],loc,x);
		}else
		{
			cout << query(1,n,root[ver],loc) << '\n';
			root[i] = root[ver];   //每次操作都会产生新版本,所以直接复制即可 
		}
	} 
	return 0;
}
相关标签: 高级数据结构