首页 > 其他 > 详细

可持久化数据结构(Trie、主席树)

时间:2021-01-20 23:27:32      阅读:32      评论:0      收藏:0      [点我收藏+]

可持久化数据结构

一、简介

1、作用是什么?

记录所有更改的历史状态

2、核心思想

只记录每一个版本与前一个版本不一样的地方

3、常用数据结构

1)可持久化Trie

技术分享图片

2)可持久化线段树——主席树

不能用一维数组存储,很难进行区间修改操作

技术分享图片

二、相关题目

256.最大异或和

256.最大异或和

255.第k小数

255.第k小数
三种做法:

  • 划分数,O(nlogn)
  • 树套树(线段树套平衡树),支持修改操作,O(mlog^2n)
  • 可持久化线段树(主席树),O(nlogn)

可持久化数据结构(Trie、主席树)

原文:https://www.cnblogs.com/grain-rain/p/14304857.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!