【主席树】【模板】【Luogu P3919】可持久化线段树1

小目录

链接

Luogu P3919

题目描述

如题，你需要维护这样的一个长度为 N 的数组，支持如下几种操作
1.在某个历史版本上修改某一个位置上的值
2.访问某个历史版本上的某一位置的值
此外，每进行一次操作（对于操作2，即为生成一个完全一样的版本，不作任何改动），就会生成一个新的版本。版本编号即为当前操作的编号（从1开始编号，版本0表示初始状态数组）

思路

主席树模板之一（因为后面还有好多篇模板
存下区间[l,r]，直接每次版本复制（log(n)），然后直接修改点就好了
Ti表示第i个版本的树的根节点

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

struct trr
{
	int k, ls, rs;
}tr[32000005];

int n, m, cnt, v, pl, val, tp;
int a[1000006], T[1000006];

void build(int &x, int l, int r)
{
	x = ++cnt;
	if(l == r) {
		tr[x].k = a[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(tr[x].ls, l, mid);
	build(tr[x].rs, mid + 1, r);
	tr[x].k = tr[tr[x].ls].k + tr[tr[x].rs].k;
}

void change(int &x, int last, int l, int r, int pl, int val)
{
	x = ++cnt;
	tr[x] = tr[last];
	if(l == r)
	{
		tr[x].k = val;
		return;
	}
	int mid = (l + r) >> 1;
	if(pl <= mid) change(tr[x].ls, tr[last].ls, l, mid, pl, val);
	if(pl > mid) change(tr[x].rs, tr[last].rs, mid + 1, r, pl, val);
	tr[x].k = tr[tr[x].ls].k + tr[tr[x].rs].k;
}

int ask(int x, int l, int r, int pl)
{
	if(l == r) return tr[x].k;
	int mid = (l + r) >> 1;
	if(pl <= mid) return ask(tr[x].ls, l, mid, pl);
	if(mid < pl) return ask(tr[x].rs, mid + 1, r, pl); 
}

int main()
{
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i)
		scanf("%d", &a[i]);
	build(T[0], 1, n);
	for(int i = 1; i <= m; ++i)
	{
		scanf("%d%d", &v, &tp);
		if(tp == 1) {
			scanf("%d%d", &pl, &val);
			change(T[i], T[v], 1, n, pl, val);
		}
		else {
			scanf("%d", &pl);
			printf("%d\n", ask(T[v], 1, n, pl));
			T[i] = T[v];
		}
	}
	return 0;
}