> 首页 / 技术文章 / 高级数据结构知识 / 文章详情

高级数据结构知识 「学习笔记」可持久化线段树

• 高级数据结构知识

可持久化线段树

变量

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

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

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

过程

image 每次修改操作修改的点的个数是一样的。 （例如上图，修改了 \(\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

复制代码
#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;
}
高级数据结构知识
作者：|yi_fan0305|，原文链接: https://www.cnblogs.com/yifan0305/p/17372381.html

文章推荐

Python异步编程之web框架 异步vs同步 Redis并发对比

无限分解流 - -Fork/Join框架

drf——全局处理异常、接口文档、jwt介绍、based64编码与解码

深度剖析Redis九种数据结构实现原理，建议收藏

一文彻底搞懂Raft算法，看这篇就够了！！！

计网学习笔记六 Network Layer Overview

最新版本 Stable Diffusion 开源 AI 绘画工具之汉化篇

设计模式(二十六)----行为型模式之备忘录模式

StyleGAN 生成 AI 虚拟人脸，再也不怕侵犯肖像权

使用go切片应注意的一个小问题：copy函数的重要性

Linux常用的20个命令(下)

一文带你看懂Java中的Lock锁底层AQS到底是如何实现的

所有标签
开发技能 数据库 云计算 AI & 大数据 Linux python 大前端 大数据 MySQL JavaScript 软件架构 Go Html5 程序人生 iOS Android AspNetCore 前端工具 职场生活 Vue.js DevOps Redis 运维 Docker SpringBoot Kubernetes 自动化测试 机器学习 数据分析 设计模式 算法 架构
实用课程推荐
相关教程推荐
休闲君评测 |  TOOLFK工具网 |  古诗文网 |  良许Linux教程网 |  Python之禅 |  红色石头 |  入党申请书 | 

© 2020 Hi LearnFk 意见反馈 免责声明 关于我们 桂ICP备11002319号-3 友链&广告位+QQ: 1963612630