| 😊 | Powered By HeartFireY | Persistent Segment Tree |
| 📕 | 需要的前导知识：线段树(Segment Tree)、权值线段树、可持久化数据结构理论(Persistent Data Structure Theory) |
一、可持久化线段树 简介
可持久化线段树，顾名思义，即对线段树进行可持久化处理之后的线段树。
在可持久化数据结构的理论中，我们对可持久化的概念有所了解：“可以返回之前的某个状态，并在该基础上进行修改”。可持久化线段树就是这样一种结构。
我们从一般思路出发进行分析：想要让线段树可持久化，最朴素的方法就是每进行一次操作都新建一颗线段树。但显然这是不明智的做法：时间和空间上而言都是非常差的的算法。我们不妨继续分析一下更新之后与更新之前的结构：每次更新都只有少量的点被修改。因此大量的点可以继续使用，无需重新建树。
本文分两个部分对可持久化线段树进行探讨。
值得注意的是：我们一般认为主席树就是可持久化线段树，实际上两者之间有区分：
可持久化线段树单纯指经过可持久化处理之后，能够查询、修改历史节点数据的结构，建立在基础线段树的基础之上；而主席树建立在权值线段树的基础之上，能够查询修改历史节点。二者本质区别在于纪念性可持久化的对象所维护的对象不同(一个维护权值、一个维护值域)。
因此，可持久化线段树主席树，准确的说，主席树可持久化线段树。
二、可持久化线段树 基本结构与操作
1.基本结构、建树操作
首先应该明确一点：由于可持久化结构重叠的特殊性，可持久化线段树不能采用堆式储存，因此只能采取动态开点的方式进行储存。
不同于后续节点的更新，对于最初的状态下的线段树我们采用一次建树完成：
- 采用递归建树，递归函数参数保存左右边界(初始化为)、当前元素的指针。同时保存总计数；
- 递归边界控制为，由于此时左边界即为指向数组的指针，因此叶子节点赋值
- 非叶子节点首先记录左右子节点的下标，然后递归建左右子树：
- 建立左右节点后非叶子节点 = 左右子节点的和：
根据以上建树过程，我们以数组为例建立线段树：
可以看到：不同于基础线段树，可持久化线段树的下标不再遵循堆的规律，这种建树方式我们称为动态开点。
结构体封装版：
#define
#define
#define
#define
struct node{
int val, mark = INT_MIN;
int ls, rs;
}tree[MAXN];
void build(int l = 1, int r = n, int p = 1){
if(l == r) val(p) = a[l];
else{
ls(p) = ++cnt, rs(p) = ++cnt;
int mid = (l + r) >> 1;
build(l, mid, ls(p));
build(mid + 1, r, rs(p));
val(p) = val(ls(p)) + val(rs(p));
}
} 建树完毕后，上述线段树已经静态化，后续的修改操作通过增加新节点来实现。
2.单点修改
假设现在要对加，则操作步骤如下：
首先建立新根结点，更新根节点记录数组：
创建新节点后对其进行处理。由于我们要修改的元素位于右子树，因此左子树部分保持不变，可以继续使用。因此将原左子树与新节点相连，同时新建右子节点。
继续处理，位于当前结点左子树，右子树保持不变继续使用，因此新建左子节点，将原右子节点与新节点相连。
继续访问左子节点发现到达叶子结点，对原数据进行处理后再逐层回溯，更新路径上的结点值。
单点修改的操作到此结束。可以看到，对于最初版本的线段树，其任何数据未被改变。
void update(int x, int d, int p, int q, int cl = 1, int cr = n){
if (cl == cr) val(q) = val(p) + d; // 给叶子节点赋值
else{
ls(q) = ls(p), rs(q) = rs(p); // 复制节点
int mid = (cl + cr) / 2;
if (x <= mid) ls(q) = ++cnt, update(x, d, ls(p), ls(q), cl, mid);
// 创建新节点作为左儿子，然后往左递归
else rs(q) = ++cnt, update(x, d, rs(p), rs(q), mid + 1, cr);
// 创建新节点作为右儿子，然后往右递归
val(q) = val(ls(q)) + val(rs(q)); // 根据子节点给当前节点赋值
}
} 3.区间查询
区间查询与基础线段树几乎一致，只需要额外关注查询的版本对应的根节点即可。
int query(int l, int r, int p, int cl = 1, int cr = n){
if (cl > r || cr < l) return 0;
else if (cl >= l && cr <= r) return val(p);
else{
int mid = (cl + cr) / 2;
return query(l, r, ls(p), cl, mid) + query(l, r, rs(p), mid + 1, cr);
}
} 4.区间修改
我们需要再次回到标记上进行讨论：
对于标记，我们其实有两种实现方案：
- 标记上下传，也就是我们最常用的操作；
- 标记永久化：标记时不用，而是在查询的时候干预数据。
二者的一大区别在于，标记上下传会引发修改结点路径上的点的更新，而标记永久化不会影响树上的点。
这点区别是非常有意义的：考虑一棵可持久化线段树，如果从某节点上传，则到根节点路径上的点都会被修改，而可持久化结构导致了某些结点的复用，这会引发多个版本的线段树更新，无法指定是哪一版本；同理，下传标记也会引发不必要的点的更新。因此，我们只能通过标记永久化对可持久化线段树进行修改。
于是，我们在查询时需要额外带上一个标记：
我们不妨再回顾一下查询的过程：
我们曾在线段树的查询过程中了解到：查询的过程就是不断地查询区间的交集，以此不断地缩小查找范围。
如上图所示，假设查询到①所示的区间则返回该节点的值，因为他是待查询区间的子集；②所示的区间则需要向右递归搜索、③向左递归搜索。
不同于基础线段树，可持久化线段树需要进行额外加永久化标记的操作，即：查询到待查区间的子集时，返回(该节点值子集元素个数永久化标记)
同时，递归查询时也要额外对标记进行累加。这点也十分容易理解：
我们思考永久标记的意义：对于当前节点所管辖的区间元素全部加某个值(或者做出某种改变)，因此向下查询子集时应该带上当前节点的标记，相当于将标记进行了下放。
ll query(int l, int r, int p, int cl = 1, int cr = n, ll mk = 0){
if (cl > r || cr < l) return 0;
else if (cl >= l && cr <= r) return val(p) + mk * (cr - cl + 1); // 加上带的标记
else{
int mid = (cl + cr) >> 1;
return query(l, r, ls(p), cl, mid, mk + mark(p)) + query(l, r, rs(p), mid + 1, cr, mk + mark(p)); // 带着标记传递
}
} 对于操作，其基本过程如下：
- 首先对当前节点进行复制；
- 判断：如果当前节点管辖区间合法，且是待修改区间的子集，那么对当前新的节点(复制后的节点)的标记执行加操作；
- 如果不满足条件，则判断待修改区间是否由左子树管辖、是否由右子树管辖，如果是则复制节点，递归向左\右建点更新。
值得注意的是，由于缺少传递标记，因此由子节点给当前节点赋值可能会发生错误。
为了得到全包含的区间并计算真实长度，我们只需要定义区间为即可(保证其为带查询区间的子集)。
void update(int l, int r, int d, int p, int q, int cl = 1, int cr = n){
ls(q) = ls(p), rs(q) = rs(p), mark(q) = mark(p); // 复制节点
if (cl >= l && cr <= r && cr > cl) mark(q) += d;
else{
int mid = (cl + cr) >> 1;
if (cl <= r && mid >= l) ls(q) = ++cnt, update(l, r, d, ls(p), ls(q), cl, mid);// 提前进行判断，以免新建不必要的节点
if (mid + 1 <= r && cr >= l) rs(q) = ++cnt, update(l, r, d, rs(p), rs(q), mid + 1, cr);
}
val(q) = val(p) + (min(cr, r) - max(cl, l) + 1) * d; // 根据需要更新的区间长度计算当前节点的值
} 三、主席树
区别于一般的可持久化线段树，主席树是可持久化权值线段树。
下面简单介绍一下主席树的构造过程：
1.建立空树
void build(int l = 1, int r = n, int p = 1){
val(p) = 0;
if (l != r){
ls(p) = ++cnt, rs(p) = ++cnt;
int mid = (l + r) / 2;
build(l, mid, ls(p));
build(mid + 1, r, rs(p));
}
} 2.区间离散化
int C[MAXN], L[MAXN], ori[MAXN];
void discretize(int A[], int n){
memcpy(C, A, sizeof(int) * n); // 复制
sort(C, C + n); // 排序
int l = unique(C, C + n) - C; // 去重
for (int i = 0; i < n; ++i){
L[i] = lower_bound(C, C + l, A[i]) - C + 1; // 查找
ori[L[i]] = A[i]; // 保存离散化后的数对应的原数
} 3.插入离散化数据
for (int i = 0; i < n; i++){
roots[i + 1] = ++cnt;
update(L[i], 1, roots[i], roots[i + 1]);
} 4.查询区间第大/小
我们已经有了求
[1, r]
内第k大数的方法（查询相应历史版本即可），而求
[l, r]
内第k小数，只需对
kth
函数稍作修改。注意，我们在求
kth
时会用到当前左儿子对应的区间和，现在要排除
[1, l-1]
，那么把这部分和减去即可。
这一部分的思想与权值树状数组很相似。
int kth(int k, int p, int q, int cl = 1, int cr = n){
if (cl == cr) return ori[cl];
int mid = (cl + cr) / 2;
if (val(ls(q)) - val(ls(p)) >= k) return kth(k, ls(p), ls(q), cl, mid); // 往左搜
else return kth(k - (val(ls(q)) - val(ls(p))), rs(p), rs(q), mid + 1, cr); // 往右搜
}