可持久化线段树支持访问一个数组的历史版本。复杂度 \(O(\log n)\)。

基础

维护三个信息，左子树，右子树，权值。

int top;

struct zxs{
	int l,r,v;
} tree[(1e6)<<2];

建树

int build(int v,int l,int r){
	v=++top;
	if(l==r){
		tree[v].v=a[l];
		return top;
	}
	int mid=(l+r)>>1;
	tree[v].l=build(tree[v].l,l,mid);
	tree[v].r=build(tree[v].r,mid+1,r);
	return v;
}

新建节点

int newnode(int v){
	top++;
	tree[top]=tree[v];
	return top;
}

单点赋值

int update(int i,int l,int r,int x,int val){
	int node=newnode(i);
	if(l==r){
		tree[node].v=val;
	}
	else{
		int mid=(l+r)>>1;
		if(x<=mid)
			tree[node].l=update(tree[node].l,l,mid,x,val); 
		else
			tree[node].r=update(tree[node].r,mid+1,r,x,val);
	}
	return node;
}

单点查询

int query(int i,int l,int r,int x){
	if(l==r){
		return tree[i].v;
	}
	else{
		int mid=(l+r)>>1;
		if(x<=mid)
			return query(tree[i].l,l,mid,x);
		else
			return query(tree[i].r,mid+1,r,x); 
	}
}

P3919 【模板】可持久化线段树 1（可持久化数组）

传送门

要关闭同步流，否则88分。

#include <bits/stdc++.h>
using namespace std;

int top,n,m;

struct zxs{
	int l,r,v;
} tree[int(1e6)<<2+5];
int a[(int)(1e6)+5],root[(int)(1e6)+5];

int newnode(int v){
	top++;
	tree[top]=tree[v];
	return top;
}

int build(int v,int l,int r){
	v=++top;
	if(l==r){
		tree[v].v=a[l];
		return top;
	}
	int mid=(l+r)>>1;
	tree[v].l=build(tree[v].l,l,mid);
	tree[v].r=build(tree[v].r,mid+1,r);
	return v;
}

int update(int i,int l,int r,int x,int val){
	int node=newnode(i);
	if(l==r){
		tree[node].v=val;
	}
	else{
		int mid=(l+r)>>1;
		if(x<=mid)
			tree[node].l=update(tree[node].l,l,mid,x,val); 
		else
			tree[node].r=update(tree[node].r,mid+1,r,x,val);
	}
	return node;
}
int query(int i,int l,int r,int x){
	if(l==r){
		return tree[i].v;
	}
	else{
		int mid=(l+r)>>1;
		if(x<=mid)
			return query(tree[i].l,l,mid,x);
		else
			return query(tree[i].r,mid+1,r,x); 
	}
}

int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	root[0]=build(0,1,n);
	for(int i=1;i<=m;i++){
		int rt,mode,x;
		cin>>rt>>mode>>x;
		if(mode==1){
			int y;
			cin>>y;
			root[i]=update(root[rt],1,n,x,y); 
		}
		else{
			printf("%d\n",query(root[rt],1,n,x));
			root[i]=root[rt];
		}
	}
}