首页 > 其他分享 >可持久化数据结构

可持久化数据结构

时间:2024-07-26 18:10:05浏览次数:19  
标签:持久 log 线段 修改 权值 数据结构 节点

可持久化数据结构简介

分类

部分可持久化

所有版本都可以访问,但是只有最新版本可以修改。

完全可持久化

所有版本都既可以访问又可以修改。

实际应用

几何计算(扫描线),字串处理(合并操作 rope),版本回溯,函数式编程。

可持久化线段树

引入[P3834 【模板】可持久化线段树 2]

首先考虑静态全局第 \(k\) 小,可以用权值线段树,在线段树上二分,同时也支持动态全局第 \(k\) 小(单点修改)。

考虑静态区间第 \(k\) 小,对于每个前缀 \(a_{1,2,\dots,n}\) 都建一个权值线段树 \(T_i\),\(T_i\) 中代表区间 \([l,r]\) 的节点存前缀 \(a_{i,2,\dots,n}\) 中有多少个数在 \([l,r]\) 内。

对于 \([l,r]\) 的询问,我们只需将 \(T_r\) 与 \(T_{l-1}\) 两棵树中的对应节点相减,就得到了该区间的权值线段树。

但一共需要 \(O(n^2)\) 个节点,考虑优化。

发现 \(T_i\) 较 \(T_{i-1}\) 只修改了从 \(a_i\) 对应的叶子节点到根节点的路径上的权值,共 \(O(\log n)\) 个节点。

因此,从 \(T_{i-1}\) 到 \(T_i\) 的过程中,我们只需要新建发生变化的 \(O(\log n)\) 个节点,剩下的节点与 \(T_{i-1}\) 共用(即新建根节点,被修改的儿子新建节点,未被修改的儿子仍用 \(T_{i-1}\) 的)。

区间修改同理,同样只有 \(O(\log n)\) 个节点被修改。

标签:持久,log,线段,修改,权值,数据结构,节点
From: https://www.cnblogs.com/CheZiHe929/p/18325966

相关文章

  • 数据结构 二叉树 前 中 后 序列
    简单二叉树的遍历如果看完还是不太懂就观看速成视频https://www.bilibili.com/video/BV1Ub4y147Zv/?spm_id_from=333.337.search-card.all.click&vd_source=e5f8765d50fb89ef04eb150bd76075b5引用资料文献链接放到篇尾简单术语解释节点(Node):二叉树中的一个元素,包含值和......
  • 【数据结构与算法】快速排序万字全攻略:hoare版本、挖坑法、前后指针法、优化版、非递
          ......
  • 软考-软件设计师(3)-数据结构与算法:树、图、队列、查找算法、排序算法、霍夫曼编码/
    场景软考-软件设计师-数据结构与算法模块高频考点整理。以下为高频考点、知识点汇总,不代表该模块所有知识点覆盖,请以官方教程提纲为准。注:博客:霸道流氓气质-CSDN博客实现知识点树:节点的度、树的度、深度、高度、满二叉树、完全二叉树、平衡二叉树、B树、二叉排序树节点......
  • 算法与数据结构 -随笔
    1.LinkedList1)Buildthelist2)Sortthelist3)Lookupsomeiteminthelist4)Insertionanddeletioninthelist5) Reversethelist6)JousephproblemWeshouldn'tlimitourselvestoonlymoveonesinglestepbyusing......
  • 【数据结构】单链表的增删改查
    介绍链表是有序的列表,但是它在内存中是如下存储的:①链表以节点的方式进行存储,是链式存储的②每个节点包含data域、next域:指向下一节点③链表的各个节点不一定是连续存放的④链表分为有头节点的链表和没有头节点的链表 head节点1.不存放具体数据2.作用就是表示......
  • 山东大学数据结构与算法实验10堆及其应用(堆的操作/霍夫曼编码)
    A : 堆的操作题目描述创建 最小堆类。最小堆的存储结构使用 数组。提供操作:插入、删除、初始化。题目第一个操作是建堆操作,接下来是对堆的插入和删除操作,插入和删除都在建好的堆上操作。输入输出格式输入第一行一个数n(n<=5000),代表堆的大小。第二行n个数,代表堆的......
  • 数据结构之队列详解
    1.队列的概念以及结构队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFo(FristinFristout)的特性入队列:进行插入才操作的一端称为队尾出队列:进行删除操作的一端称为队头2.队列的实现队列也可以使用数组和链表的结构实现,使用......
  • 多校数据结构
    多校数据结构省选选手不再需要学习新数据结构,主要需要学习数据结构题目的常见套路,训练代码能力,提升思维能力。因此,此次授课主要提供各种类型的数据结构题目,点拨解题思路,为选手在比赛中处理各类数据结构问题提供参考。[CF1039D]YouAreGivenaTree题目描述有一棵\(n\)个......
  • 数据结构--第一天
    --顺序表    -顺序表的概念     顺序表实际上就是数组,数组在进行封装后,可以进行增删改查操作,就成了顺序表    -顺序表相关函数      malloc函数        框架:int* p=(int*)malloc(sizeof(int));      ......
  • 数据结构-2. 动态数组1
    动态数组设计structdynamicArray{ void**pAddr;//维护真实在堆区创建的数组的指针 intm_capacity;//数组容量 intm_size;//数组大小};数组初始化structdynamicArray*init_DynamicArry(intcapacity){ if(capacity<=0) { returnNULL; } //给数......