【题目描述】

您的任务是维护一个数组列表，该列表最初只有一个数组。您必须处理以下类型的查询：

将数组k中的值a设置为x。

计算数组k中[a，b]范围内的值的总和。

创建数组k的副本，并将其添加到列表的末尾。

【输入】

第一个输入行有两个整数n和q：数组大小和查询数。

下一行有n个整数t1，t2，…，tn：数组的初始内容。

最后，还有描述查询的q行。每行的格式为以下格式之一：“1 k a x”、“2 k a b”或“3 k”。

【输出】

打印每个总和查询的答案。

【输入样例】

5 6

2 3 1 2 5

3 1

2 1 1 5

2 2 1 5

1 2 2 5

2 1 1 5

2 2 1 5

【输出样例】

13

13

13

15

#include<cstdio>
#include<vector>
#define int long long
using namespace std;
struct sd{
	int l;
	int r;
	int L;
	int R;
	int x;
};
const int N=200005;
int root[N],num=1;
vector<sd>d;
int tot;
int n,m,a[N];
void build(int p){
	int s=d[p].L,t=d[p].R;
	if(s==t){
		d[p].x=a[s];
		return ;
	}
	int mid=(s+t)>>1;
	if(!d[p].l){
		sd lin;
		lin.x=0;
		lin.l=lin.r=0;
		lin.L=s,lin.R=mid;
		tot++;
		d.push_back(lin);
		d[p].l=tot;
	}
	if(!d[p].r){
		sd lin;
		lin.x=0;
		lin.l=lin.r=0;
		lin.L=mid+1,lin.R=t;
		tot++;
		d.push_back(lin);
		d[p].r=tot;
	}
	build(d[p].l);
	build(d[p].r);
	d[p].x=d[d[p].l].x+d[d[p].r].x;
	return ;
}
void update(int x,int y,int p,int p0){
	int l0=d[p0].l,r0=d[p0].r;
	int s=d[p].L,t=d[p].R;
	if(s==t){
		d[p].x=y;
		return ;
	}
	int mid=(s+t)>>1;
	if(x<=mid){
		sd lin;
		lin.x=0;
		lin.l=lin.r=0;
		lin.L=s,lin.R=mid;
		tot++;
		d.push_back(lin);
		d[p].l=tot;
		d[p].r=r0;
		update(x,y,d[p].l,l0);
	}
	else{
		sd lin;
		lin.x=0;
		lin.l=lin.r=0;
		lin.L=mid+1,lin.R=t;
		tot++;
		d.push_back(lin);
		d[p].r=tot;
		d[p].l=l0;
		update(x,y,d[p].r,r0);
	}
	d[p].x=d[d[p].l].x+d[d[p].r].x;
	return ;
}
int findth(int x,int y,int p){
	int s=d[p].L,t=d[p].R;
	if(x<=s&&t<=y) return d[p].x;
	int mid=(s+t)>>1;
	int sum=0;
	if(x<=mid) sum+=findth(x,y,d[p].l);
	if(y>mid) sum+=findth(x,y,d[p].r);
	return sum;
}
signed main(){
	scanf("%lld%lld",&n,&m);
	sd lin;
	lin.L=lin.l=lin.R=lin.r=0;lin.x=0;
	d.push_back(lin);
	lin.L=1,lin.R=n;
	lin.l=lin.r=0;
	lin.x=0;
	d.push_back(lin);
	tot=1;
	root[1]=1;
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	build(root[1]);
	for(int i=1;i<=m;i++){
		int T,k,x,y;
		scanf("%lld",&T);
		if(T==3){
			scanf("%lld",&k);
			num++;
			lin.L=1,lin.R=n;
			lin.l=d[root[k]].l,lin.r=d[root[k]].r;
			lin.x=d[root[k]].x;
			d.push_back(lin);
			tot++;
			root[num]=tot;
		}
		else if(T==1){
			scanf("%lld%lld%lld",&k,&x,&y);
			update(x,y,root[k],root[k]);
		}
		else{
			scanf("%lld%lld%lld",&k,&x,&y);
			printf("%lld\n",findth(x,y,root[k]));
		}
	}
}