可持久化线段树

可持久化线段树

1.概念

可持久化线段树又被称为主席树。可持久化是指更新的同时保留了历史版本，可以获得所有的历史版本。

本质上是多颗线段树，不过这些线段树共同使用了一部分枝干。

2.实现

可持久化线段树和线段树的实现有很大差别。

线段树的left和right表示区间的左右边界，而可持久化线段树的left和right表示该节点的左右儿子

没更新一次，新建log(n)条边，如下

对于最简单的可持久化线段树：

P3919 【模板】可持久化线 1（可持久化数组） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

struct node
{
	int left, right, power;
};
int node a[4 * N + 22 * N];//表示整个树
int top=0,root[N];//root[i]表示第i个版本根节点在a数组中的下标

//建树，由于left和right不表示左右边界，函数中要有l，r表示边界
//返回的是这个节点的下标
//root[0]=build(1,n);//刚开始的是零号版本
int build(int l, int r)
{
	top++;
	int i = top;
	if (l == r)
	{
		cin >> a[top].power;
		return i;
	}
	int mid = (l + r) / 2;
	a[i].left = build(l, mid);
	a[i].right = build(mid + 1, r);
	return i;
}

更新某个点的大小

这个点的大小改变，上面相关的log(n)个节点也会改变。

所以增加log(n)个节点，对应于多个top++,其余节点的左右儿子不变，

//将第v个版本的第x个数更改成y，
//k表示v版本的根节点的下标，返回值是当前版本节点下标
root[i] = update(root[v], 1, n, x, y);
int update(int k, int l, int r, int x, int y)
{
	top++;
	int i = top;
    if(l==r)
		a[i].power = y;
	else
	{
		int mid = (l + r) / 2;
		if (x <= mid)
		{
			a[i].left = update(a[k].left, l, mid, x, y);
			a[i].right = a[k].right;
		}
		else
		{
			a[i].right = update(a[k].right, mid + 1, r, x, y);
			a[i].left = a[k].left;
		}
	}
	return i;
}

最终查询

//查询第v个版本的第x个数的值
query(root[v], 1, n, x);
void query(int k, int l, int r, int x)
{
	if (l == r)
		cout << a[k].power << endl;
	else
	{
		int mid = (l + r) / 2;
		if (x <= mid)
			query(a[k].left, l, mid, x);
		else
			query(a[k].right, mid + 1, r, x);
	}
	return;
}

非常经典的可持久化权值线段树入门题——静态区间第 k小。

1，离散化。将n个数变成1~n的数。

例如：25957 6405 15770 26287 26465 --> 3 1 2 4 5

//全放入map中，
int a[n],b[n];//a[i]表示原来的数组，b[i]表示第i大的数是a中的那个，mp[x]表示x是第几大的数
for (int i = 1; i <= n; i++)
{
	cin >> a[i];
	mp[a[i]] = 1;
}
map::iterator it;
int v = 1;
for (it = mp.begin(); it != mp.end(); it++)
{
	b[v] = it->first;		
    it->second = v;
	v++;
}

2，建立可持久化线段树

int root[200005], top = 0;
struct node
{
	int left, right, num;
};//num表示区间中有多少个数
node tree[4 * N + 20 * N];

root[0] = build(1, len);
int build(int l, int r)//建立一个空的树，为0号版本，
{
	top++;
	int i = top;
	if (l == r)
		return i;
	int mid = (l + r) / 2;
	tree[i].left = build(l, mid);
	tree[i].right = build(mid + 1, r);
	return i;
}

3，把n个数逐个插入,形成n个版本

//len=mp.size();len为区间长度
//有部分数字重复出现，所以区间总长度会变小
for (int i = 1; i <= n; i++)
{
	x = mp[a[i]];//插入的是离散化的结果
	root[i] = update(1, len, root[i - 1], x);//将x插入上一个版本
}

int update(int l, int r, int t, int x)//将第x个数++
{
	top++;
	int i = top;
	if (l == r)
	{
		tree[i].num = tree[t].num + 1;
		return i;
	}
	int mid = (l + r) / 2;
	if (x <= mid)
	{
		tree[i].right = tree[t].right;
		tree[i].left = update(l, mid, tree[t].left, x);
		tree[i].num = tree[tree[i].left].num + tree[tree[i].right].num;
	}
	else
	{
		tree[i].left = tree[t].left;
		tree[i].right = update(mid + 1, r, tree[t].right, x);
		tree[i].num = tree[tree[i].left].num + tree[tree[i].right].num;
	}
	return i;
}

4，询问区间[x,y]第z小的数

分析：

求第50个数~100个数中第30小的数。

应用了前缀和的思想，root[49]中存的是前49个树的信息，root[100]存的是前100个数的信息，

两者相减得到的是50-100的数的信息。

int lsum = tree[tree[y].left].num - tree[tree[x].left].num;

如果两个节点的左儿子节点中有超过k个数，则答案在左边。

若不超过k，答案在右边，询问第k-lsum大的数。

for (int i = 1; i <= m; i++)
{
	cin >> l >> r >> k;
	query(1, len, root[l-1], root[r], k);
}
void query(int l, int r, int x, int y, int z)
{
	if (l == r)
	{
		cout << n2[l] << endl;
		return;
	}
	int mid = (l + r) / 2;
	int lsum = tree[tree[y].left].num - tree[tree[x].left].num;
	//int rsum = tree[tree[y].right].num - tree[tree[x].right].num;
	if (lsum >= z)
	{
		query(l, mid, tree[x].left, tree[y].left, z);
	}
	else
	{
		query(mid + 1, r, tree[x].right, tree[y].right, z - lsum);
	}
}

例题3

给一个数列，每次询问一个区间内有没有一个数出现次数超过一半

POI2014]KUR-Couriers - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)