可持久化数组:路径复制与共享节点实现历史版本查询
可持久化数组解决的是这样一类问题同一个数组经过多次单点修改后还能随时查询任意历史版本中任意下标的值。普通数组保存的是“当前状态”一次赋值就会覆盖旧值改掉就回不去如果每修改一次就把整个数组复制一份内存和时间又完全不能接受。可持久化数组的关键在于共享节点、只复制修改路径把单次修改的代价从 O(n) 降到 O(log n)同时让旧版本根节点继续保留旧值。算法动画里最能体现这一点的是那棵“会分身”的线段树一次修改不是推倒重来而是沿着根到叶子的路径长出一串新节点旧节点原封不动。理解这条主线就能回答标题里的问题——改过的数为什么还能查回去因为旧数据从来没有被删掉只是不再被新版本引用而已。1. 可持久化数组到底在解决什么问题1.1 普通数组做不到的事普通数组的赋值操作非常直接把某个下标对应的内存单元改成新值。下面这段代码看起来没有任何问题。int a[5] {1, 2, 3, 4, 5}; a[1] 99; // a 现在是 {1, 99, 3, 4, 5}问题在于原来的数组在哪里内存中同一个地址已经被覆盖旧值 2 已经不存在了。如果程序只是处理当前状态这当然没问题但一旦业务逻辑需要撤销、重放、回到某次修改之前的版本普通数组就无能为力。这类场景在工程里很常见编辑器撤销栈、版本化配置、进程快照、在线数据表的历史回溯都会遇到“修改之后还要能读取修改前的值”的需求。数据结构领域把这种能力称为可持久化常见说法是 Persistence。所以可持久化数组要解决的并不是“怎么把数组改得更好”而是“怎么让每一次修改都被完整保存下来并且可以在任意时刻查询任意历史版本”。1.2 朴素快照方案为什么不可行最容易想到的方案是做快照每次修改前或修改后把整个数组复制一份存到版本列表里。查询历史版本时直接按下标读取对应版本数组。写成代码大概是这样vectorvectorint versions; versions.push_back(original); // 修改时复制最后一份再修改 vectorint cur versions.back(); cur[pos] value; versions.push_back(cur); // 查询时直接读取 int val versions[ver][pos];这个方案逻辑清晰、查询很快坏在修改成本太高。数组长度为 n每修改一次就要复制 n 个元素修改 m 次总时间 O(n*m)空间也是 O(n*m)。当 n 和 m 都达到 10 万级别时内存会接近灾难。假设每个整数占 4 字节10 万次修改、每次复制 10 万个整数总占用约 40GB任何常规竞赛或业务环境都扛不住。快照方案并不是完全不能用它适合数据量小、修改次数少、查询压力大的场景。但在大数组高频修改的场景里必须换一种更聪明的结构。1.3 可持久化思想的核心不覆盖旧数据共享旧结构可持久化数据结构的设计思路可以概括成两句话旧节点永远不修改。新版本复制需要变化的路径其余部分直接共享旧节点。可持久化数组的典型实现是把数组看成线段树叶子节点上保存的值。线段树的每个节点代表一个区间根节点代表整个数组。初始版本由一棵完整线段树构成执行单点修改时从根节点出发到目标叶子的整条路径上每个节点都新建一份副本路径之外的所有子树继续指向旧版本节点。从外部看修改一次只是多了一条“新根到新叶子”的路径数组的其余部分仍然和旧版本共用。因为旧根没有被改动旧版本依旧可以完整查询因为新根指向的是复制出来的路径新版本也不会干扰旧版本。这样就把单次修改的时间从 O(n) 压缩到了 O(log n)。为了实现这一点需要一棵动态开点的线段树而不是用数组下标 2*i、2*i1 的静态完全二叉树。每个节点必须显式记录左右孩子下标否则无法在多个版本之间共享子树。2. 路径复制原理一次修改为什么要新建 log n 个节点2.1 线段树是天然的版本容器可持久化数组为什么选择线段树而不是直接改造普通数组原因在于线段树天然具备“用区间索引定位单点”的能力。一颗长度为 n 的线段树深度约 log2(n)1。从根走到任意一个叶子需要经过的节点数也就是这个深度。可持久化单点修改时只有这条路径上的节点值或孩子指针会发生变化因此只需要复制这些节点。路径外的兄弟子树保持不变可以被新版本直接共享。以数组 [1,2,3,4,5] 为例初始版本 root0 的线段树一共 9 个节点5 个叶子4 个内部节点。如果修改下标 2 为 99从根节点到叶子 [2,2] 的路径一共 4 个节点根 [1,5]、内部节点 [1,3]、内部节点 [1,2]、叶子 [2,2]。新版本只需要新建这 4 个节点。这种结构可以抽象成下面的样子root0 root1 [1,5] [1,5] / \ / \ [1,3] [4,5] [1,3]new [4,5]继承 / \ / \ [1,2] [3,3] [1,2]继承 [3,3]继承 / \ [1,1] [2,2]newroot0 仍然指向左侧原来的 [1,5]所以版本 0 的数组还是 [1,2,3,4,5]。root1 指向新的 [1,5]这个新根向左走到新 [1,3]继续向左走到从版本 0 继承下来的 [1,2]再向左走到 [1,1]向右走到新叶子 [2,2]新根的右孩子直接继承版本 0 的 [4,5]。因此版本 1 读到的数组是 [1,99,3,4,5]同时没有破坏版本 0。2.2 一次单点修改的节点变化过程把一次修改拆成更细的步骤可以写成一个标准流程给新根节点分配一个新编号。把旧根节点的 left、right、value 全部复制到新根节点。判断目标下标 pos 属于左子树还是右子树。如果是左子树递归修改左子树并把返回的新左孩子下标赋给新根节点的 left。如果是右子树递归修改右子树并把返回的新右孩子下标赋给新根节点的 right。到达叶子时把新节点的 value 改成目标值。整个过程只复制从根到目标叶子路径上的节点未经过的子树直接保留旧下标。下面用表格说明一次修改会新建哪些节点新节点代表区间创建原因孩子指向根节点[1,5]新版本必须有新根左孩子指向新的 [1,3]右孩子继承旧 [4,5]内部节点[1,3]路径经过左孩子继承旧 [1,2]右孩子继承旧 [3,3]内部节点[1,2]路径经过左孩子继承旧 [1,1]右孩子指向新叶子 [2,2]叶子节点[2,2]目标位置value99这里的关键点是新根虽然代表版本 1但它的很多子孙节点仍然是版本 0 的节点。这就是“共享”的实际含义。2.3 版本根与查询路径保存历史版本并不需要复制整棵树只需要保存一个数组 root下标是版本号值是每个版本根节点在节点池中的下标。root[0] 建树返回的根下标; root[1] 第一次修改返回的新根下标; root[2] 第二次修改返回的新根下标;查询版本 ver 中位置 pos 的值时从 root[ver] 出发按 pos 所在的区间不断向下走直到叶子。为什么这样查询不会读到后续版本的修改因为版本 ver 的根节点保存的是“当时”的树关系。即使后面新建了版本 2、版本 3版本 1 的根节点下标没有变它指向的左孩子、右孩子也没有变。后续版本的修改只会在新路径上创建新节点不可能回头去修改版本 1 路径上已经存在的节点。可以从另一个角度理解可持久化数组不是“数组在变”而是“一棵不断生长的树在记录所有状态”。每次修改只是在树上新增一条路径旧路径永远保持原样。3. C 实现一个最小可运行的可持久化数组3.1 节点设计与内存预分配因为每个节点都要被多个版本共享节点不能在递归函数里以局部变量形式存在必须使用一个全局的节点池。节点结构包含三个字段左孩子下标、右孩子下标、当前节点保存的值。struct Node { int left; int right; int value; };这里 value 只在叶子节点上有实际作用。内部节点的 value 在单点查询实现里不会被用到。如果后续要支持区间和、区间最大值就需要把 value 替换成 sum、max 等聚合字段。节点池大小需要提前估算。初始建树会创建约 2*n 个节点每次修改会创建约 log2(n)1 个节点。如果修改次数为 m总节点数大约是2 * n m * (ceil(log2(n)) 1)为了更稳妥可以在公式后面加一个常数余量。下面代码里按 n 和 m 都取 100000log 约 17 来估算const int MAXN 100005; const int LOGN 18; const int MAXQ 100005; const int MAXNODE MAXN * 2 MAXQ * (LOGN 2); struct Node { int left; int right; int value; }; Node tree[MAXNODE]; int root[MAXQ]; int nodeCnt 0;数组开得比理论值大一些能避免极端数据下段错误。实际生产环境还要根据自己的数据规模重新计算不能照搬。3.2 建树、修改、查询三块核心代码建树负责从数组 a 构造出版本 0。叶子节点记录 a[l]内部节点不需要计算聚合值只需要把左右孩子连起来。int a[MAXN]; int build(int l, int r) { int id nodeCnt; if (l r) { tree[id].value a[l]; return id; } int mid (l r) 1; tree[id].left build(l, mid); tree[id].right build(mid 1, r); return id; }这里要注意 build 访问的 a 是全局数组下标从 1 开始。如果题目要求下标从 0 开始需要统一调整 l、r 和数组下标不要在函数内部混用两套体系。修改操作是路径复制的核心int update(int prev, int l, int r, int pos, int val) { int id nodeCnt; tree[id].left tree[prev].left; tree[id].right tree[prev].right; tree[id].value tree[prev].value; if (l r) { tree[id].value val; return id; } int mid (l r) 1; if (pos mid) { tree[id].left update(tree[prev].left, l, mid, pos, val); } else { tree[id].right update(tree[prev].right, mid 1, r, pos, val); } return id; }update 第一件事是复制旧节点字段而不是直接修改旧节点。复制完成后再修改需要变化的一侧孩子指针另一侧保持继承关系。这样返回的新节点 id 可以安全作为新版本的根。查询操作只读取不创建任何节点int query(int u, int l, int r, int pos) { if (l r) { return tree[u].value; } int mid (l r) 1; if (pos mid) { return query(tree[u].left, l, mid, pos); } return query(tree[u].right, mid 1, r, pos); }整个递归过程始终沿着 pos 所在区间前进最终在叶子返回 value。3.3 完整示例与输入输出验证把上面三块代码组装成完整程序。操作规则如下1 pos val在当前最新版本基础上把 pos 位置改成 val生成一个新版本。2 ver pos查询第 ver 个版本中 pos 位置的值。#include bits/stdc.h using namespace std; const int MAXN 100005; const int LOGN 18; const int MAXQ 100005; const int MAXNODE

相关新闻

LangChain Agent集成MCP全流程:从工具调用到记忆持久化

LangChain Agent集成MCP全流程:从工具调用到记忆持久化

最近 LangChain、Agent、MCP 这几个关键词在开发圈讨论度很高。这次我们直接拆一套完整的 LangChain Agent 集成 MCP 全流程,重点解决当下 Agent 应用里最容易被忽略的问题:Agent 怎么接外部工具,以及记忆系统在企业级场景里怎么做才不是玩具…

2026/11/19 22:37:13 阅读更多 →
多模型数据库统一引擎:融合关系、图、列式与键值存储

多模型数据库统一引擎:融合关系、图、列式与键值存储

如果你所在团队的业务线同时要求“快、准、深、宽”,那么你很可能会在同一个系统中被迫同时维护 MySQL、Neo4j、ClickHouse 和 Redis。每一套都是成熟产品,但每一套都有自己的安装、备份、监控、权限和版本升级流程。数据要在多个系统之间同步&#xff0…

2026/11/19 22:37:13 阅读更多 →
Grok Bot智能体协作实战:接入Dify/Coze与工程化落地

Grok Bot智能体协作实战:接入Dify/Coze与工程化落地

Grok Bot 的名字在智能体圈子里最近出现得越来越频繁。如果你正在搭建多智能体协作流程,或者准备把大模型能力接进 Dify、Coze 这类智能体平台,那这篇内容可以直接收藏。今天不聊概念,重点说清楚 Grok Bot 在智能体协作里到底解决什么问题、怎…

2026/11/3 11:14:08 阅读更多 →

最新新闻

Electron桌面应用开发实战:从环境搭建到打包发布全流程

Electron桌面应用开发实战:从环境搭建到打包发布全流程

做前端这些年,我大部分时间都在跟浏览器标签页打交道,直到第一次把桌面应用跑起来,才发现原来自己一直被限制在地址栏和刷新按钮围起来的框框里。Electron这个词,最开始是在某段时间频繁出现在同事的讨论里,一个用HTML…

2026/11/19 21:38:27 阅读更多 →
滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

滑盖智能锁T109深度解析:结构原理、安装调试与故障排查

简介:亚太天能T109滑盖智能锁产品说明书是一份PDF格式的官方技术文档,主要面向智能锁安装人员、终端用户及售后维护者,帮助快速掌握产品安装、配置与常见故障处理。全包仅1个PDF文件,大小4.37MB,内容结构清晰&#xff…

2026/11/19 21:38:49 阅读更多 →
PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

PMSM弱磁控制原理与Simulink建模:高速AGV驱动系统设计指南

上个月我在调试一台高速AGV的驱动系统,整车要求空载跑到8m/s,电机转速已经拉到额定点,驱动器的输出电压也顶到了母线电压极限附近。再往上踩速度指令,转速纹丝不动,三相电流反而开始震荡。那会儿我的第一反应就是&…

2026/11/19 21:39:09 阅读更多 →
C++核心知识点:从内存管理到STL的实战指南

C++核心知识点:从内存管理到STL的实战指南

C 这门语言我前前后后折腾了十几年,用它写过嵌入式驱动、做过游戏服务端,也搭过基础组件库。每次看到新人一头扎进"C 核心知识点"这个搜索词,我其实挺感慨的——这门语言的难点从来不是语法多,而是知识点之间的耦合太深…

2026/11/19 21:36:50 阅读更多 →
T109滑盖智能锁怎么装?安装调试与故障排查全攻略

T109滑盖智能锁怎么装?安装调试与故障排查全攻略

简介:亚太天能T109滑盖智能锁产品说明书以PDF格式发布,适合智能锁用户、安装人员与售后维修人员阅读。内容围绕T109系列指纹密码刷卡锁展开,先介绍前面板、后面板、锁体、机械钥匙、电池盒盖等部件名称与功能,再给出完整安装步骤&…

2026/11/19 21:37:45 阅读更多 →
LLM知识降熵:从信息垄断到理解权下放

LLM知识降熵:从信息垄断到理解权下放

你有没有过这种经历:翻开源码注释、论文摘要或者一份专业报告,每个字都认识,连在一起却像天书。想找人聊聊,身边要么没人懂,要么懂的懒得跟你解释。后来我试着把同一段内容丢给一个大语言模型,几秒钟之后&a…

2026/11/19 21:36:20 阅读更多 →

日新闻

周新闻

月新闻