【模板】可持久化数组（可持久化线段树/平衡树）

传送门

原来写过一篇不能看的，现在重新写一遍，也当是复习巩固可持久化线段树的思想。

---

题意

给定一个数列以及两种操作：

• 操作1：修改某一个历史版本某个位置上的值

• 操作2：查询某一个历史版本某个位置上的值

对于每一个操作，都会生成一个新的历史版本。其中操作2生成的历史版本与查询的版本相同。

---

思路

考虑最朴素的解法，对于每一个版本，我们直接开空间保存下来，这样的话时间复杂度和空间复杂度都是(O(nm))，显然无法接受。

不难发现，时间复杂度之所以会有(O(nm))，是因为每一次储存树都要耗费巨量的时间，因此只要简化储存方式就可以同时降低时间与空间复杂度。

容易想到，两个版本之间存在相同的元素，因此只要在储存时不储存这一个部分就可以实现简化了。

易知修改前后两个版本之间的区别在于所有包含被修改元素的区间，这样的区间长度是(logn)。所以简化后的空间复杂度应该是(O(mlogn))，时间复杂度同。

实现上我们对于每次更新只需要新建被修改的节点即可，原有节点直接利用。

---

代码

#include <bits/stdc++.h>

using namespace std;

namespace StandardIO {

	template<typename T>inline void read (T &x) {
		x=0;T f=1;char c=getchar();
		for (; c<'0'||c>'9'; c=getchar()) if (c=='-') f=-1;
		for (; c>='0'&&c<='9'; c=getchar()) x=x*10+c-'0';
		x*=f;
	}

	template<typename T>inline void write (T x) {
		if (x<0) putchar('-'),x=-x;
		if (x>=10) write(x/10);
		putchar((x%10)+'0');
	}

}

using namespace StandardIO;

namespace Project {
	#define int long long
	
	const int N=1000001;
	
	int n,m;
	int tot,rcnt;
	int a[N],root[N];
	struct node {
		int l,r;
		int val;
	} tree[N*15];
	
	inline void pushup (int pos) {
		tree[pos].val=tree[tree[pos].l].val+tree[tree[pos].r].val;
	}
	int build (int l,int r) {
		int now=++tot,mid=(l+r)>>1;
		if (l==r) {
			tree[now].val=a[l];
			return now;
		}
		tree[now].l=build(l,mid),tree[now].r=build(mid+1,r);
		pushup(now);
		return now;
	}
	int update (int las,int x,int val,int l,int r) {
		int now=++tot,mid=(l+r)>>1;
		if (l==r) tree[now].val=val;
		else if (x<=mid) {
			tree[now].l=update(tree[las].l,x,val,l,mid);
			tree[now].r=tree[las].r;
			pushup(now);
		} else {
			tree[now].l=tree[las].l;
			tree[now].r=update(tree[las].r,x,val,mid+1,r);
			pushup(now);
		}
		return now;
	}
	int query (int las,int x,int l,int r) {
		if (l==r) return tree[las].val;
		int mid=(l+r)>>1;
		if (x<=mid) return query(tree[las].l,x,l,mid);
		return query(tree[las].r,x,mid+1,r);
	}

	inline void MAIN () {
		read(n),read(m);
		for (register int i=1; i<=n; ++i) {
			read(a[i]);
		}
		root[0]=build(1,n);
//		5 10 59 46 14 87 41
		while (m--) {
			int op,x,y,z;
			read(x),read(op),read(y);
			if (op==1) read(z),root[++rcnt]=update(root[x],y,z,1,n);
			else root[++rcnt]=root[x],write(query(root[x],y,1,n)),putchar('
');
		}
	}
	
	#undef int
}

int main () {
//	freopen("testdata.in","r",stdin);
//	freopen("testdata.out","w",stdout);
	Project::MAIN();
}