Nginx环境搭建 JS acm haskell build autocomplete jestjs vue安装教程 jquery触发点击事件 jquery获取元素宽度 mysql组合索引 python输出函数 python搭建环境 pythoninput random函数用法 java在线教程 java迭代器 java框架 java读取文件数据 java中的泛型 磁盘分区软件 php连接mssql typemonkey din字体 1660ti java电子书 fdisk下载 无限视距 存储过程写法 电脑听歌识曲 碧桂园园宝 ABViewer cad视口旋转 微信公众号点餐系统 qq黑客软件 欧洲卡车模拟2存档 炫舞爱的惊喜 ps光照效果 启用宏在哪里设置 淘宝退货怎么上门取件
当前位置: 首页 > 学习教程  > 编程语言

主席树

2020/8/11 19:50:22 文章标签:

主席树

首先必须会线段树并且会动态开点才能看该博客。

众所周知,线段树长这样

在这里插入图片描述

主席树,又称可持久化线段树,因为它支持历史查询,就像这样:
现在有一个序列,原始版本:[1,2,3,4]
1:将原始版本2号点增加3,成为1号版本:[1,5,3,4]
2:查询1号版本区间1~3的和:9
3:将1号版本3号点增加3,成为2号版本:[1,5,6,4]
4:查询原始版本区间1~5的和:10
5:将1号版本4号点减少1,成为3号版本:[1,5,3,3]

而这些,我们都可以用主席树维护。
由于每一次只会改变一个点,所以我们可以这么做。
假如现在要在原始版本重修改4号点,我们就可以新建一个根节点,作为一号版本的根节点,然后将左儿子连向原始版本的左儿子,新建右儿子,再将右儿子的左儿子连向原始版本的右儿子的左儿子,然后再在右儿子中新建一个右儿子,值为现在修改成的值,就可以啦。
就像这样:
在这里插入图片描述
我们发现:从每一个根开始遍历当前树其实就是当前版本的线段树。
记录一下每一个版本的根,然后动态开点就可以啦。


本文链接: http://www.dtmao.cc/news_show_100225.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?