可持久化 Trie

前置知识：Trie。

设 $tr_{i, c}$ 为节点 $i$ 边权为 $c$ 的边指向的节点，插入一个字符串 $s$ 的具体方式如下：

1. 设当前可持久化 Trie 的最新根节点为 $u1$，新建一个节点 $u2$，设 $i = 1$。
2. 若 $u1$ 不为空节点，对于每一个 $c$ 令 $tr_{u2, c} = tr_{u1, c}$。
3. 新建一个节点 $t$，令 $tr_{u2, c} = t$。
4. 令 $u1 = tr_{u1, c}$，$u2 = tr_{u2, c}$，$i = i + 1$。
5. 重复操作 $2 \sim 4$ 直到 $i > |s|$。

下面演示了一棵可持久化 Trie 顺序插入 cat、rat、cab、fry 后的形态。

我们可以发现，从第 $i$ 次插入的根节点遍历，可以得到前 $i$ 次插入所得到的 Trie。

设字符集大小为 $l$，字符串为 $s$，单次插入时间复杂度为 $O(l \times |s|)$，单次插入会新建 $|s|$ 个节点。

例题

最大异或和

[十二省联考 2019] 异或粽子

[THUSC2015] 异或运算

可持久化线段树

前置知识：线段树。

根据可持久化 Trie 的思想，我们可以用类似的方法实现可持久化线段树。

下面是一颗可持久化线段树修改一次后的形态。

与可持久化 Trie 一样，从第 $i$ 次插入的根节点遍历，可以得到前 $i$ 次插入后的线段树。

模板题一代码：

#include <algorithm>
#include <cstdio>
int cnt = 0, rt[1000001];
struct node{
	int l, r, v;
}tr[30000001];
void update(int u1, int &u2, int l, int r, int p, int x){
	if (!u2) u2 = ++ cnt;
	if (l == r){
		tr[u2].v = x;
		return;
	}
	int mid = l + r >> 1;
	if (p <= mid) tr[u2].r = tr[u1].r, update(tr[u1].l, tr[u2].l, l, mid, p, x);
	else tr[u2].l = tr[u1].l, update(tr[u1].r, tr[u2].r, mid + 1, r, p, x);
} // 在 u1 为根的版本基础上修改
int query(int u, int l, int r, int p){
	if (!u) return 0;
	if (l == r) return tr[u].v;
	int mid = l + r >> 1;
	if (p <= mid) return query(tr[u].l, l, mid, p);
	return query(tr[u].r, mid + 1, r, p);
} // 查询

using namespace std;

int n, m, a[1000001], bb, op, p, x;
void build(int &u, int l, int r){
	if (!u) u = ++ cnt;
	if (l == r){
		tr[u].v = a[l];
		return;
	}
	int mid = l + r >> 1;
	build(tr[u].l, l, mid), build(tr[u].r, mid + 1, r);
} // 建树
int main(){
	scanf("%d%d", &n, &m);
	for (int i = 1;i <= n;i ++) scanf("%d", &a[i]);
	build(rt[0], 1, n);
	for (int i = 1;i <= m;i ++){
		scanf("%d%d%d", &bb, &op, &p);
		if (op == 1) scanf("%d", &x), update(rt[bb], rt[i], 1, n, p, x);
		else rt[i] = rt[bb], printf("%d\n", query(rt[i], 1, n, p));
	}
}

模板题二代码：

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

using namespace std;

int cnt, rt[500001];
struct node{
	int l, r, sum;
}tr[10000001];
int build(int l, int r){
	int o = ++ cnt;
	tr[o].sum = 0;
	if (l < r){
		int mid = l + r >> 1;
		tr[o].l = build(l, mid);
		tr[o].r = build(mid + 1, r);
	}
	return o;
} // 建树
int insert(int u, int l, int r, int x){
	int o = ++ cnt;
	tr[o] = tr[u], tr[o].sum ++;
	if (l >= r) return o;
	int mid = l + r >> 1;
	if (x <= mid) tr[o].l = insert(tr[u].l, l, mid, x);
	else tr[o].r = insert(tr[u].r, mid + 1, r, x);
	return o;
} // 修改
int query(int L, int R, int l, int r, int x){
	if (l >= r) return l;
	int mid = l + r >> 1, ch = tr[tr[R].l].sum - tr[tr[L].l].sum;
	if (x <= ch) return query(tr[L].l, tr[R].l, l, mid, x);
	return query(tr[L].r, tr[R].r, mid + 1, r, x - ch);
} // 查询
int n, m, len, a[500001], b[500001], ll, rr, x;
int main(){
	scanf("%d%d", &n, &m);
	for (int i = 1;i <= n;i ++) scanf("%d", &a[i]);
	memcpy(b, a, sizeof(a));
	sort(b + 1, b + n + 1);
	len = unique(b + 1, b + n + 1) - b - 1;
	rt[0] = build(1, len);
	for (int i = 1;i <= n;i ++) rt[i] = insert(rt[i - 1], 1, len, lower_bound(b + 1, b + len + 1, a[i]) - b);
	while (m --){
		scanf("%d%d%d", &ll, &rr, &x);
		printf("%d\n", b[query(rt[ll - 1], rt[rr], 1, len, x)]);
	}
}

可持久化并查集

只要实现了可持久化数组，将并查集的 $fa$ 数组可持久化就是可持久化并查集了。

模板题代码：

#include <algorithm>
#include <cstdio>
struct node{
	int l, r, v;
};
struct Array{
	int n, cnt, rt[200001];
	node tr[10000001];
	void build(int &u, int l, int r, int* a){
		if (!u) u = ++ cnt;
		if (l == r){
			tr[u].v = a[l];
			return;
		}
		int mid = l + r >> 1;
		build(tr[u].l, l, mid, a), build(tr[u].r, mid + 1, r, a);
	}
	void update(int u1, int &u2, int l, int r, int p, int x){
		u2 = ++ cnt;
		if (l == r){
			tr[u2].v = x;
			return;
		}
		int mid = l + r >> 1;
		if (p <= mid) tr[u2].r = tr[u1].r, update(tr[u1].l, tr[u2].l, l, mid, p, x);
		else tr[u2].l = tr[u1].l, update(tr[u1].r, tr[u2].r, mid + 1, r, p, x);
	}
	int query(int u, int l, int r, int p){
		if (!u) return 0;
		if (l == r) return tr[u].v;
		int mid = l + r >> 1;
		if (p <= mid) return query(tr[u].l, l, mid, p);
		return query(tr[u].r, mid + 1, r, p);
	}
	void init(int l, int* a){n = l, build(rt[0], 1, n, a);}
	void upd(int r1, int r2, int p, int x){update(rt[r1], rt[r2], 1, n, p, x);}
	int get(int r1, int p){return query(rt[r1], 1, n, p);}
}fa, siz;

using namespace std;

int n, m, _[100001], op, a, b, now;
int getfa(int x){
	int fax = fa.get(now - 1, x);
	if (x == fax) return x;
	return getfa(fax);
}
void merge(int a, int b){
	a = getfa(a), b = getfa(b);
	if (a == b) return;
	int siza = siz.get(now - 1, a), sizb = siz.get(now - 1, b);
	if (siza < sizb) swap(a, b), swap(siza, sizb);
	fa.upd(now - 1, now, b, a);
	siz.upd(now - 1, now, a, siza + sizb);
}
int main(){
	scanf("%d%d", &n, &m);
	for (int i = 1;i <= n;i ++) _[i] = i;
	fa.init(n, _);
	for (int i = 1;i <= n;i ++) _[i] = 1;
	siz.init(n, _);
	for (now = 1;now <= m;now ++){
		scanf("%d", &op);
		fa.rt[now] = fa.rt[now - 1], siz.rt[now] = siz.rt[now - 1];
		if (op == 1) scanf("%d%d", &a, &b), merge(a, b);
		else if (op == 2) scanf("%d", &a), fa.rt[now] = fa.rt[a], siz.rt[now] = siz.rt[a];
		else scanf("%d%d", &a, &b), printf("%d\n", getfa(a) == getfa(b));
	}
}

例题

[国家集训队] middle

[FJOI2016] 神秘数

[SCOI2016] 美味

Count on a tree

[SDOI2013] 森林