1. Toy模板网首页
  2. > Toy博客

「学习笔记」可持久化线段树?

10月前 作者：yi_fan0305 分类：Toy博客 阅读(35) 违法举报

这篇具有很好参考价值的文章主要介绍了「学习笔记」可持久化线段树?。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

可持久化数据结构 (Persistent data structure) 总是可以保留每一个历史版本，并且支持操作的不可变特性 (immutable)。
主席树全称是可持久化权值线段树，给定 \(n\) 个整数构成的序列 \(a\)，将对于指定的闭区间 \(\left[l, r\right]\) 查询其区间内的第 \(k\) 小值。

图片来自 \(\texttt{OI-wiki}\)

可持久化线段树

变量

#define mid ((l + r) >> 1)
int rot;
int rt[M];

struct node {
	int l, r, val;
} nod[M];

l, r: 左右孩子的指针；
val: 权值；
rot: 动态开点计数器；
rt: 不同版本的根节点的编号。

过程

「学习笔记」可持久化线段树?
每次修改操作修改的点的个数是一样的。
（例如上图，修改了 \(\left[1,8\right]\) 中对应权值为 \(1\) 的结点，红色的点即为更改的点）
只更改了 \(O_{\log{n}}\) 个结点，形成一条链，也就是说每次更改的结点数 \(=\) 树的高度。
主席树不能使用 \(x\times 2，x\times 2+1\) 来表示左右儿子，而是应该动态开点，并保存每个节点的左右儿子编号。
在记录左右儿子的基础上，保存插入每个数的时候的根节点就可以实现持久化。
现在还有个问题，如何求 \(\left[l,r\right]\) 区间 \(k\) 小值。
这里我们再联系另外一个知识：前缀和。
这个小东西巧妙运用了区间减法的性质，通过预处理从而达到 \(O_1\) 回答每个询问。
我们可以发现，主席树统计的信息也满足这个性质。
如果需要得到 \(\left[l,r\right]\) 的统计信息，只需要用 \(\left[1,r\right]\) 的信息减去 \(\left[1,l - 1\right]\) 的信息就行了。
关于空间问题，直接上个 \(2^5\times 10^5\)（即 n << 5，大多数题目中空间限制都较为宽松，因此一般不用担心空间超限的问题）。

操作

  • 建树

int build(int l, int r) {
	int u = ++ rot;
	if (l == r) {
		return u;
	}
	nod[u].l = build(l, mid);
	nod[u].r = build(mid + 1, r);
	return u;
}

  • 创建新节点

inline int newnod(int u) {
	++ rot;
	nod[rot] = nod[u];
	nod[rot].val = nod[u].val + 1;
	return rot;
}

修改时是在原来版本的基础上进行修改，先设置它们一样，由于插入了一个新的数，所以 nod[rot].val = nod[u].val + 1;。

  • 插入新节点

int add(int u, int l, int r, int pos) {
	u = newnod(u);
	if (l == r)	return u;
	if (pos <= mid) {
		nod[u].l = add(nod[u].l, l, mid, pos);
	}
	else {
		nod[u].r = add(nod[u].r, mid + 1, r, pos);
	}
	return u;
}

if (pos <= mid) {
	nod[u].l = add(nod[u].l, l, mid, pos);
}
else {
	nod[u].r = add(nod[u].r, mid + 1, r, pos);
}

修改时只会修改一条链，那也就意味着只会修改左孩子或右孩子中的一个，另一个保持不变。

  • 查询第 \(k\) 大

int query(int l, int r, int lr, int rr, int k) {
	int x = nod[nod[rr].l].val - nod[nod[lr].l].val;
	if (l == r)	return l;
	if (k <= x) {
		return query(l, mid, nod[lr].l, nod[rr].l, k);
	}
	else {
		return query(mid + 1, r, nod[lr].r, nod[rr].r, k - x);
	}
}

int x = nod[nod[rr].l].val - nod[nod[lr].l].val;

这里利用了前缀和，求的是在 \(lr\) 到 \(rr\) 这个版本之间，左孩子的数量增加了多少，即 \(\left[lr, rr\right]\) 的前 \(x\) 小的元素。

if (k <= x) {
	return query(l, mid, nod[lr].l, nod[rr].l, k);
}
else {
	return query(mid + 1, r, nod[lr].r, nod[rr].r, k - x);
}

如果 \(k < x\)，那么说明第 \(k\) 大的数在右孩子上，否则就在左子树上。

可持久化数组

这个来源于洛谷的【模板】可持久化线段树 1（可持久化数组），需要支持修改操作，但没有了查询第 \(k\) 大操作和插入操作。

变量

#define mid ((l + r) >> 1)
int rot;
int rt[M];

struct node {
	int ls, rs, val;
} nod[(N << 5) + 10];

操作

  • 创建新节点

inline int newnod(int u) { // 创建新节点
	++ rot;
	nod[rot] = nod[u];
	return rot;
}

  • 建树

int build(int l, int r) { // 建树
	int u = ++ rot;
	if (l == r) {
		scanf("%d", &nod[u].val);
		return u;
	}
	nod[u].ls = build(l, mid);
	nod[u].rs = build(mid + 1, r);
	return u;
}

  • 修改

int modify(int u, int l, int r, int pos, int c) { // 修改
	u = newnod(u);
	if (l == r) {
		nod[u].val = c;
	}
	else {
		if (pos <= mid) {
			nod[u].ls = modify(nod[u].ls, l, mid, pos, c);
		}
		else {
			nod[u].rs = modify(nod[u].rs, mid + 1, r, pos, c);
		}
	}
	return u;
}

  • 查询

int query(int u, int l, int r, int pos) { // 查询
	if (l == r) {
		return nod[u].val;
	}
	else {
		if (pos <= mid) {
			return query(nod[u].ls, l, mid, pos);
		}
		else {
			return query(nod[u].rs, mid + 1, r, pos);
		}
	}
}

模板

namespace Persistent { // 可持久化数据结构
#define mid ((l + r) >> 1)
	
	const int N = 1e6 + 5;
	const int M = (N << 5) + 10;
	
	struct persistent_arr { // 可持久化数组
		int rot;
		int rt[M];
		
		struct node {
			int ls, rs, val;
		} nod[(N << 5) + 10];
		
		inline int newnod(int u) { // 创建新节点
			++ rot;
			nod[rot] = nod[u];
			return rot;
		}
		
		int build(int l, int r) { // 建树
			int u = ++ rot;
			if (l == r) {
				scanf("%d", &nod[u].val);
				return u;
			}
			nod[u].ls = build(l, mid);
			nod[u].rs = build(mid + 1, r);
			return u;
		}
		
		int modify(int u, int l, int r, int pos, int c) { // 修改
			u = newnod(u);
			if (l == r) {
				nod[u].val = c;
			}
			else {
				if (pos <= mid) {
					nod[u].ls = modify(nod[u].ls, l, mid, pos, c);
				}
				else {
					nod[u].rs = modify(nod[u].rs, mid + 1, r, pos, c);
				}
			}
			return u;
		}
		
		int query(int u, int l, int r, int pos) { // 查询
			if (l == r) {
				return nod[u].val;
			}
			else {
				if (pos <= mid) {
					return query(nod[u].ls, l, mid, pos);
				}
				else {
					return query(nod[u].rs, mid + 1, r, pos);
				}
			}
		}
	};
	
	struct persistent_seg {
		int rot;
		int rt[M];
		
		struct node {
			int l, r, val;
		} nod[M];
		
		inline int newnod(int u) { // 创建新节点
			++ rot;
			nod[rot] = nod[u];
			nod[rot].val = nod[u].val + 1;
			return rot;
		}
		
		int build(int l, int r) { // 建树
			int u = ++ rot;
			if (l == r) {
				return u;
			}
			nod[u].l = build(l, mid);
			nod[u].r = build(mid + 1, r);
			return u;
		}
		
		int add(int u, int l, int r, int pos) { // 插入新节点
			u = newnod(u);
			if (l == r)	return u;
			if (pos <= mid) {
				nod[u].l = add(nod[u].l, l, mid, pos);
			}
			else {
				nod[u].r = add(nod[u].r, mid + 1, r, pos);
			}
			return u;
		}
		
		int query(int l, int r, int lr, int rr, int k) { // 查找第 k 大的值
			int x = nod[nod[rr].l].val - nod[nod[lr].l].val;
			if (l == r)	return l;
			if (k <= x) {
				return query(l, mid, nod[lr].l, nod[rr].l, k);
			}
			else {
				return query(mid + 1, r, nod[lr].r, nod[rr].r, k - x);
			}
		}
	};
}

例题

【模板】可持久化线段树 1（可持久化数组）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mid ((l + r) >> 1)

const int N = 1e6 + 5;

int n, m, rot;
int a[N], rt[N];

inline int read() {
	int x = 0;
	int fg = 0;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		fg |= (ch == '-');
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = (x << 3) + (x << 1) + (ch ^ 48);
		ch = getchar();
	}
	return fg ? ~x + 1 : x;
}

struct node {
	int ls, rs, val;
} nod[(N << 5) + 10];

inline int newnod(int u) {
	++ rot;
	nod[rot] = nod[u];
	return rot;
}

int build(int l, int r) {
	int u = ++ rot;
	if (l == r) {
		nod[u].val = a[l];
		return u;
	}
	nod[u].ls = build(l, mid);
	nod[u].rs = build(mid + 1, r);
	return u;
}

int modify(int u, int l, int r, int pos, int c) {
	u = newnod(u);
	if (l == r) {
		nod[u].val = c;
	}
	else {
		if (pos <= mid) {
			nod[u].ls = modify(nod[u].ls, l, mid, pos, c);
		}
		else {
			nod[u].rs = modify(nod[u].rs, mid + 1, r, pos, c);
		}
	}
	return u;
}

int query(int u, int l, int r, int pos) {
	if (l == r) {
		return nod[u].val;
	}
	else {
		if (pos <= mid) {
			return query(nod[u].ls, l, mid, pos);
		}
		else {
			return query(nod[u].rs, mid + 1, r, pos);
		}
	}
}

int main() {
	n = read(), m = read();
	for (int i = 1; i <= n; ++ i) {
		a[i] = read();
	}
	rt[0] = build(1, n);
	for (int i = 1, x, op, pos, val; i <= m; ++ i) {
		x = read(), op = read(), pos = read();
		if (op == 1) {
			val = read();
			rt[i] = modify(rt[x], 1, n, pos, val);
		}
		else {
			printf("%d\n", query(rt[x], 1, n, pos));
			rt[i] = rt[x];
		}
	}
}

【模板】可持久化线段树 2文章来源地址https://www.toymoban.com/news/detail-433948.html

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mid ((l + r) >> 1)

const int N = 1e6 + 5;
const int M = (N << 5) + 10;

int n, m;
int rot;
int a[N], tmp[N], rt[N];

struct node {
	int l, r, val;
} nod[M];

inline int getid(int c, int len) {
	return lower_bound(tmp + 1, tmp + len + 1, c) - tmp;
}

inline int newnod(int u) {
	++ rot;
	nod[rot] = nod[u];
	nod[rot].val = nod[u].val + 1;
	return rot;
}

int build(int l, int r) {
	int u = ++ rot;
	if (l == r) {
		return u;
	}
	nod[u].l = build(l, mid);
	nod[u].r = build(mid + 1, r);
	return u;
}

int add(int u, int l, int r, int pos) {
	u = newnod(u);
	if (l == r)	return u;
	if (pos <= mid) {
		nod[u].l = add(nod[u].l, l, mid, pos);
	}
	else {
		nod[u].r = add(nod[u].r, mid + 1, r, pos);
	}
	return u;
}

int query(int l, int r, int lr, int rr, int k) {
	int x = nod[nod[rr].l].val - nod[nod[lr].l].val;
	if (l == r)	return l;
	if (k <= x) {
		return query(l, mid, nod[lr].l, nod[rr].l, k);
	}
	else {
		return query(mid + 1, r, nod[lr].r, nod[rr].r, k - x);
	}
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++ i) {
		scanf("%d", a + i);
		tmp[i] = a[i];
	}
	sort(tmp + 1, tmp + n + 1);
	int len = unique(tmp + 1, tmp + n + 1) - tmp - 1;
	rt[0] = build(1, len);
	for (int i = 1; i <= n; ++ i) {
		rt[i] = add(rt[i - 1], 1, len, getid(a[i], len));
	}
	for (int i = 1, l, r, k; i <= m; ++ i) {
		scanf("%d%d%d", &l, &r, &k);
		printf("%d\n", tmp[query(1, len, rt[l - 1], rt[r], k)]);
	}
	return 0;
}

到了这里，关于「学习笔记」可持久化线段树?的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • Unity学习笔记--数据持久化之PlayerPrefs的使用

    PlayerPrefs是Unity游戏引擎中的一个类，用于在游戏中存储和访问玩家的偏好设置和数据。它可以用来保存玩家的游戏进度、设置选项、最高分数等信息。PlayerPrefs将数据存储在本地文件中，因此可以在游戏重新启动时保持数据的持久性。 PlayerPrefs中存储的数据存储在哪里？ PC端

    2024年02月05日
    浏览(44)

  • 可持久化线段树15（思维+乱搞）

    P4559 [JSOI2018]列队 首先思考： 对于 [ l , r ] [l,r] [ l , r ] 区间内的同学，他们集合之后与集合之前的相对大小是不会改变的，所有无论是否集合他们的相对的顺序是不变的，那么集合到 [ k , k + r − l ] [k,k+r-l] [ k , k + r − l ] 的时候，他们的位置一定是固定的，我们可以将其称之

    2024年02月09日
    浏览(31)
  • 微服务 - Redis缓存 · 数据结构 · 持久化 · 分布式 · 高并发

    微服务 - Redis缓存 · 数据结构 · 持久化 · 分布式 · 高并发

    系列目录 微服务 - 概念 · 应用 · 架构 · 通讯 · 授权 · 跨域 · 限流 微服务 - Consul集群化 · 服务注册 · 健康检测 · 服务发现 · 负载均衡 微服务 - Redis缓存 · 数据结构 · 持久化 · 分布式 · 高并发 微服务 - Nginx网关 · 进程机制 · 限流熔断 · 性能优化 · 动态负载 · 高可用

    2023年04月18日
    浏览(50)

  • Unity笔记：数据持久化的几种方式

    主要方法： ScriptableObject PlayerPrefs JSON XML 数据库（如Sqlite） PlayerPrefs 存储的数据是 全局共享 的，它们存储在用户设备的本地存储中，并且可以被应用程序的所有部分访问。这意味着，无论在哪个场景、哪个脚本中，只要是同一个应用程序中的代码，都可以读取和修改 Playe

    2024年02月19日
    浏览(44)
  • 【Unity学习日记03】数据持久化

    【Unity学习日记03】数据持久化

    这一篇只能说写了一部分，并没有把Unity里数据持久化的操作讲完整，之后可能是学到一点就记一点的模式。 数据持久化就是将内存中的数据模型转换为存储模型，以及将存储模型转换为内存中的数据模型的统称。 人话版：将游戏数据存储到硬盘，硬盘中数据读取到游戏中，

    2024年02月12日
    浏览(52)
  • Spark大数据处理讲课笔记--- RDD持久化机制

    Spark大数据处理讲课笔记--- RDD持久化机制

    理解RDD持久化的必要性 了解RDD的存储级别 学会如何查看RDD缓存 Spark中的RDD是懒加载的，只有当遇到行动算子时才会从头计算所有RDD，而且当同一个RDD被多次使用时，每次都需要重新计算一遍，这样会严重增加消耗。为了避免重复计算同一个RDD，可以将RDD进行持久化。 Spark中

    2024年02月06日
    浏览(44)

  • Spark大数据处理讲课笔记3.5 RDD持久化机制

    2023年05月06日
    浏览(45)

  • Docker学习路线5：在 Docker 中实现数据持久化

    Docker 可以运行隔离的容器，包括应用程序和其依赖项，与主机操作系统分离。默认情况下，容器是临时的，这意味着容器中存储的任何数据在终止后都将丢失。为了解决这个问题并在容器生命周期内保留数据，Docker 提供了各种数据持久化方法。 Docker 卷 绑定挂载 Docker tmpfs

    2024年02月16日
    浏览(45)
  • RabbitMQ学习笔记（消息发布确认，死信队列，集群，交换机，持久化，生产者、消费者）

    RabbitMQ学习笔记（消息发布确认，死信队列，集群，交换机，持久化，生产者、消费者）

    MQ（message queue）：本质上是个队列，遵循FIFO原则，队列中存放的是message，是一种跨进程的通信机制，用于上下游传递消息。MQ提供“逻辑解耦+物理解耦”的消息通信服务。使用了MQ之后消息发送上游只需要依赖MQ，不需要依赖其它服务。 功能1：流量消峰 功能2：应用解耦 功

    2024年02月07日
    浏览(54)
  • PySpark大数据教程：深入学习SparkCore的RDD持久化和Checkpoint

    PySpark大数据教程：深入学习SparkCore的RDD持久化和Checkpoint

    本教程详细介绍了PySpark中SparkCore的RDD持久化和Checkpoint功能，重点讲解了缓存和检查点的作用、如何进行缓存、如何设置检查点目录以及它们之间的区别。还提供了join操作的示例和Spark算子补充知识。

    2024年02月08日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包