type
status
date
slug
summary
tags
category
icon
password
主席树
主席树全称是可持久化权值线段树
引入
保存每次插入操作时的历史版本，以便查询区间第 k小。
要开一堆线段树？
分析一下，发现每次修改操作修改的点的个数是一样的。
通过修改一条链来进行了修改，修改数为树的高度。
而树的储存就需要从线段树那样的堆维护，使用动态开点来维护，在需要时才进行开点。
所以只要在记录左右儿子的基础上，保存插入每个数的时候的根节点就可以实现持久化。
每次求 区间的小值，只需要找到插入时的根节点版本，使用权值线段树。
加上前缀和，如果需要得到的统计信息，只需要用的信息减去的
就可以。
代码
大法——
#include<ext/rope> using namespace __gnu_cxx; 本来是一个用于快速操作string的工具，却一般被定义成int，然后用作可持久化线段树。
定义方法
如何申请更新一个新的可持久化版本：
如何继承版本
访问第num个版本
在末尾添加元素str
在pos插入元素x
从pos开始删除x个元素
将从pos开始len个元素替换为x
从pos开始换成b
从pos开始提取s个
复杂度
代码
- Author:Grimner
- URL:https://tangly1024.com/article/example-29
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!