可持久化数据结构-线段树(主席树）

可持久化数据结构-线段树(主席树）

(与可持久化字典树差不多）

1. 概念：可持久化线段树是基本线段树的一个简单拓展， 是使用函数式编程思想的线段树；

2. 作用： 可以存下来数据结构的所有历史版本

3. 特点: 拓扑结构不变

4. 核心思想：只记录每一个版本与前一个版本不同的节点， 并且利用历史版本之间的共用数据减少时间和空间消耗 (听起来很懵)

5. 打个比喻：$1s$ 动画由 $20$帧左右的静态画面连续播放而成， 每两幅相邻画面之间的差别很少， 如果用计算机制作动画 ， 若每一帧的画面都重新制作，会很浪费空间， 为了降低成本， 让每一帧画面只记录与前一帧的不同处；（又如红绿灯的秒数倒计时）

6. 类比线段树：基本思路如下：
   (1).有多棵线段树–如同每一帧的画面，(特点）
   (2).相邻的两棵线段树之间差别很小， 所以每棵线段树只需存储于前一棵的不同之处， 使用时再去修改填补并生成一棵完整存线段树(复制)。
   (3).任意两颗线段树能"相减"， 得到一棵新的线段树， 它往往包含了题目需要的解。

   实例：

   ​ 给定 $n$ 个整数构成的序列 $a$，将对于指定的闭区间 $[l,r]$ 查询其区间内的第 $k$ 小值。

   如何解决？

   一种可行的方案是：使用主席树。 主席树的主要思想就是：保存每次插入操作时的历史版本，以便查询区间第 $k$ 小。

   ​ 若每次开一棵线段树去存储， 很明显空间会爆掉。那应该如何去做呢？

   ​ 分析一下， 发现每次操作修改的的点的个数都是一样的。 如下图， 修改了 $[1，8]$ 中对应权值为 1 的结点，红色的点即为更改的点

   

   只更改了 $lo{g}_n$ 个结点，形成一条链，也就是说每次更改的结点数 = 树的高度

   怎么保存呢？简单暴力一点，每次开一棵线段树呗。
   那空间还不爆掉？

7. 需要建多少棵树呢？
   题目给定包含 n 个元素的序列， 每次用一个新元素建成一棵线段树， 共有 n 棵线段树

8. 每棵树有多少节点？
   线段树的叶子节点记录了元素， 如果元素没有重复， 叶子节点就设为 n 个， 如果元素有重复， 根据情况， 叶子节点可以设为 n 个， 也可以设为不重复元素的数量

9. 注意， 可持久化线段树只能解决单点修改问题， 不可解决区间修改问题

原因：不好处理懒标记

1.空间复杂度呈指数级增长

​ 当使用常规的可持久化线段树进行区间修改时，假设我们要对区间进行修改。如果使用懒标记来处理区 间修改，每次更新时，为了维护可持久化的特性，需要复制从根节点到包含该区间的所有节点路径。

例如，对于一个深度为 $ h$ 的线段树，在最坏的情况下，区间修改可能会导致 $2^h $ 个节点被复制。这 是因为线段树的节点数与区间划分的层次有关，一般有个节点（为数据规模）。如果频繁进行区间修改，空间消耗会急剧上升。

2. 时间复杂度的增加

• 时间复杂度方面，每次区间修改涉及的节点复制和更新操作是比较复杂的。首先，要找到包含区间的节点
• 然后，在复制和更新节点时，由于要维护可持久化，对于每个复制的节点，可能还需要更新其相关的指针和数据。例如，更新节点的左右子节点指针、更新区间范围信息等。
• 当懒标记下传时，还需要对每个子节点进行相应的更新操作，这个过程在最坏情况下可能会导致每次区间修改的时间复杂度达到。而且在进行查询操作时，由于节点结构因为区间修改变得更加复杂，查询的时间复杂度也可能会受到影响，不再是简单的，可能会因为需要处理更多的节点和懒标记而增加。

3. 实际逻辑复杂度

​ 太麻烦了没必要

10. 实际解决: 通常需要结合前缀和巧妙的去处理， 通过预处理达到 $O(1)$ 的复杂度。 So, 如果需要得到 $[l,r]$ 的统计信息，只需要用 $[1,r]$ 的信息减去 $[1,l-1]$ 的信息就行了。
11. 存点：

不能使用堆式存储法，就是说不能用 $x\times 2$，$x\times 2+1$ 来表示左右儿子，而是应该动态开点，并保存每个节点的左右儿子编号。 为什么这么做呢？------- 堆式存储法通常用于完全二叉树，如堆这种数据结构。在堆中，节点的存储顺序是按照数组下标来确定父子关系的。

主席树的结构特点决定了它不适合堆式存储。主席树在更新过程中，由于要保留历史版本，它的节点修改和新增是比较灵活的，不是像堆那样有固定的完全二叉树结构。

例如，在主席树中插入一个新元素可能只涉及到一条从根节点到叶子节点的路径上的节点修改和复制，而堆式存储的结构调整方式会干扰这种局部的、有针对性的更新，使得更新操作变得复杂，而且会破坏主席树原本高效的可持久化实现机制。同时，堆式存储法难以满足主席树在查询历史版本等操

作时的要求，因为它的存储方式不便于快速定位和访问历史版本对应的树结构。

------------所以， 应该用指针的方式去存

12.可持久化线段树的信息

struct{int l, r; // 表示左右子节点的下标int cnt; // 当前区间中一共有多少个数 }

一般不需要存储左右边界， 而是在递归的时候直接把左右边界直接传下去就好了。

可持久化线段树比Trie更简单，Trie在加入一个新单词可能会出现很多新的点的，但线段树中每一个版本的节点都是一样的， 所以线段树的判断要少一些。

13. 例题

洛谷P3834 【模板】可持久化线段树 2

ACWing 255 第 k 小数

分析： 此问题为静态问题 (在整个询问当中原序列没有发生变化)

​ 数据比较大， 所以需要离散化一下， 使数据变为 0 ~ n - 1 很小的范围

接着 在数值上面建立线段树 (注意不是下标)， 用线段树维护每一个数值区间中一共有多少个数

引子：如何求整体的第k小数。

已经将0 ~ n - 1离散化，排序了。

在线段树上面做二分。 判断0 - mid之间有多少个数。假设有cnt个数 如果 $cnt\ge k$, 说明左边整个区间里面数的个数比k要多，那就说明第k小数一定是在区间的左边 则递归左边， 否则递归右边。可以发现每次只会递归一边， 整个树有 $lo{g}_n$ 层，所以整个做法最多只会访问 $lo{g}_n$ 个节点.

复杂度为 $ O(log_n) $ . 这个问题是很简单的。

​ 现在考虑区间限制。

​ $[l,r]之间第k小数为多少$

​ 先考虑 $[1,r]$之间第k小数为多少。用可持久化线段树，从前往后加， 找刚好加完前 r 个数的时候线段树版本为多少， 直接搜此版本的线段树即可。

​ 由于可持久化线段树的特点，树本身结构不变，

所以可以想到

​ 求出第 r 个版本的区间 $[1,r]$ 之间数的个数 cnt1，

​ 以及第l - 1个版本的区间 $[l,r]$ 之间的个数 cnt2; (前缀和的思想)

​ 用 cnt1 - cnt2 就能得到在 l ~ r 中 出现多少个数 （对应6. (3)）

​ 用二分实现，就能找到最终的解。

代码:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>using namespace std;const int N = 100010;int n, m;
int a[N];
vector<int> nums; //用来离散化struct Node  //可持久化线段树的信息
{int l, r;int cnt;
}tr[N * 4 + N * 17];//首先需要开N << 2个点， 需要操作n次， 因此需要开nlogn个int root[N], idx;//每个版本的根节点 和 当前线段树中可用节点的下标//求每个数离散化后的值为多少
int find(int x)
{return lower_bound(nums.begin(), nums.end(), x) - nums.begin();
}
//建树
int build(int l, int r)
{int p = ++ idx;if (l == r) return p;int mid = l + r >> 1;tr[p].l = build(l, mid), tr[p].r = build(mid + 1, r);return p;
}
//插入
int insert(int p, int l, int r, int x)
{int q = ++ idx;tr[q] = tr[p];//复制之前的节点if (l == r){tr[q].cnt ++ ;return q;}int mid = l + r >> 1;if (x <= mid) tr[q].l = insert(tr[p].l, l, mid, x);// 在左边else tr[q].r = insert(tr[p].r, mid + 1, r, x);// 在右边tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt;// 更新 cnt = 左右儿子之和return q;
}int query(int q, int p, int l, int r, int k)//后面一个版本为q, 前面一个版本为p;
{if (l == r) return r;//到叶子节点int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt;//左半边的个数int mid = l + r >> 1;//查询 正如前面分析所说if (k <= cnt) return query(tr[q].l, tr[p].l, l, mid, k);else return query(tr[q].r, tr[p].r, mid + 1, r, k - cnt);
}int main()
{scanf("%d%d", &n, &m);for (int i = 1; i <= n; i ++ ){scanf("%d", &a[i]);nums.push_back(a[i]);}// 离散化 排序 + 删掉重复元素sort(nums.begin(), nums.end());nums.erase(unique(nums.begin(), nums.end()), nums.end());//第一个版本的线段树root[0] = build(0, nums.size() - 1);// n次操作for (int i = 1; i <= n; i ++ )root[i] = insert(root[i - 1], 0, nums.size() - 1, find(a[i]));// 第i 个版本的线段树, 和上一个版本的线段树比较。 0, num.size() - 1 为左右边界;//查询操作while (m -- ){int l, r, k;scanf("%d%d%d", &l, &r, &k);printf("%d\n", nums[query(root[r], root[l - 1], 0, nums.size() - 1, k)]);//返回为去掉离散化之后的值}return 0;
}

完结。