可持久化线段树学习笔记 (一)

扯淡

新赛季在即, 便在高二放弃了四晚回家博客 (希望作业少一点吧) , 可能是OI生涯的最后一年了.

简介

本期主要简单介绍普通的可持久化线段树 (如可持久化数组).

前置知识

1. 线段树
2. 权值线段树

普通可持久化线段树 (可持久化数组)

众所周知, 线段树是一种十分优秀的区间修改区间查询的数据结构. 但是线段树有一个弊端就是不可持久化, 即无法回到某一历史版本 (如本题), 于是可持久化线段树应运而生. 简单来说, 可持久化线段树在每次操作时都构建了一棵新的线段树. 但是很显然如果每次都建立一棵完整的线段树, 无论是空间复杂度还是时间复杂度都将难以接受. 于是我们发现每次的修改只会改变根节点到叶子节点的 logn 个节点. 于是可持久化线段树也依照如此每次只修改 logn 个节点来使空间复杂度和时间复杂度都达到较优的水平.

不同于普通线段树, 为了更加灵活地添加节点, 可持久化线段树使用结构体来保存每一个节点, 每个节点保存当前节点的信息以及左右儿子的节点编号. 除此以外还需要建立 root 数组来记录每棵树的根节点, 每次修改只需从上一个树的根节点向下添加需要更新的节点, 并将新的根节点加入 root 数组. 查询时只需要从某一历史版本的根节点开始按照普通线段树的方式进行查询.

code

const int MAXN = 1000010;
const int MAXM = 1000010;

int n, m, endd;
struct node {
	int l,r,w;
};
int root[MAXM];
int num[MAXN];
struct node tree[25000000];
int clone(int p){
	tree[++endd] = tree[p];
	return endd;
}
void buildtree(int p,int l,int r){
	if(l == r){
		tree[p].w = num[l];
		return;
	}
	int m = (l + r) >> 1;
	tree[p].l = ++endd;
	tree[p].r = ++endd;
	buildtree(tree[p].l, l, m);
	buildtree(tree[p].r, m + 1, r);
	return;
}
int add(int p, int l, int r, int pp, int w){
	p = clone(p);
	if(l == r) {
		tree[p].w = w;
		return p;
	}
	int m = (l + r) >> 1;
	if(pp >= l && pp <= m) tree[p].l = add(tree[p].l, l, m, pp, w);
	else tree[p].r = add(tree[p].r, m + 1, r, pp, w);
	return p;
}
int ask(int p, int l, int r, int pp){
	if(l == r) return tree[p].w;
	int m = (l + r) >> 1;
	if(pp >= l && pp <= m) return ask(tree[p].l, l, m, pp);
	else return ask(tree[p].r, m + 1, r, pp);
}
int main() {
	n = read(), m = read();
	rep(i,1,n){
		num[i] = read();
	}
	buildtree(0,1,n);
	rep(i,1,m){
		int vi = read(), op = read(), p = read();
		if(op == 1){
			int x = read();
			root[i] = add(root[vi],1,n,p,x);
		}
		else{
			root[i] = root[vi];
			printf("%d\n", ask(root[vi], 1, n, p));
		}
	}
	return 0;
}

一些细节

1. 数组大小理论为 nlogn + mlogn , 实际代码中对于大部分题目都可以开 n*20 来防止溢出.
2. 修改节点复制后 p 要更新为新的节点编号.
3. 修改下传后要更新儿子节点的编号.

应用

刚才的例题中, 我们发现我们对非叶子节点的利用并不彻底, 只是简单的记录了左右端点. 实际上我们完全可以像线段树一样充分地利用每一个节点. 可持久化线段树的应用也不仅仅是在可持久化数组上. 我们发现在普通的线段树上可以 logn 的时间完成的操作, 在可持久化线段树上同样可以, 只是可持久化线段树支持历史版本的查询. 我们继续深究就会发现二者本质的不同在于维护的数据的类型数目不同. 普通线段树只是同时维护了左右端点以及节点 value , 而可持久化线段树除此以外多了一个类型即 root 数组. 在例题中是数组下标, 在别的题目中它可以有别的身份, 需要灵活地运用.