通过与 Jira 对比,让您更全面了解 PingCode

  • 首页
  • 需求与产品管理
  • 项目管理
  • 测试与缺陷管理
  • 知识管理
  • 效能度量
        • 更多产品

          客户为中心的产品管理工具

          专业的软件研发项目管理工具

          简单易用的团队知识库管理

          可量化的研发效能度量工具

          测试用例维护与计划执行

          以团队为中心的协作沟通

          研发工作流自动化工具

          账号认证与安全管理工具

          Why PingCode
          为什么选择 PingCode ?

          6000+企业信赖之选,为研发团队降本增效

        • 行业解决方案
          先进制造(即将上线)
        • 解决方案1
        • 解决方案2
  • Jira替代方案

25人以下免费

目录

写时拷贝与可持久化数据结构的区别是什么

写时拷贝与可持久化数据结构的区别是可持久化:将数据结构的所有历史版本记录下来,称为可持久化。不是所有的数据结构都是可以持久化的,可持久化的数据结构要求其结构稳定,比如堆(是一颗满二叉树,结构稳定)、树状数组等。

一、写时拷贝与可持久化数据结构的区别

写时拷贝与可持久化数据结构的区别是可持久化:将数据结构的所有历史版本记录下来,称为可持久化。不是所有的数据结构都是可以持久化的,可持久化的数据结构要求其结构稳定,比如堆(是一颗满二叉树,结构稳定)、树状数组、trie(字典树)、线段树等。平衡树就不可以进行持久化操作,因为其存在左旋、右旋的操作。

存下来所有的历史版本有两种方式,一种是每改动一次则全部备份下来;另一种是增量备份。名列前茅种方式时空复杂度都比较高,不使用这种方式,我们这里只讲解增量备份的方式(类似于git)。

增量备份的核心思想是:只记录每个版本与前一个版本不同的部分。

可持久化Trie的用途:

正常的Trie树可以解决字符串的一些问题,特殊的Trie树(比如0/1Trie)可以解决最大异或和的相关问题,但是如果每次的询问是针对区间的,Trie树就不好解决,因为你不能对每个区间都建一棵Trie树,那样空间就会爆炸,于是,我们的可持久化Trie就登场了。

延伸阅读:

二、可持久化Trie的构造

设trie[x][ch],表示从x号节点连向的字符为ch的点的编号(与普通Trie的含义相同),root[i]表示第i次插入的字符串的根节点,tot代表总节点数

可持久化Trie插入第i个字符串的构造流程如下:

1:首先新建第i个字符串的根节点,并定义两个变量p,q代表当前串的节点和上一个版本与之对应的节点,初始化p=root[i-1],q=root[i]

2:若当前字符串的下一个字符是ch,那么就让trie[q][ch]=++tot;

然后对于不是ch的字符CH,trie[q][CH]=trie[p][CH];

3:让p=trie[p][ch],q=trie[q][ch],并重复2,3,步直到建树完成。

相关文章