学习可持久化线段树前提须知
可持久化 是一种数据结构的统称，他们同样有的功能就是能够 保存历史版本 ，今天我们要说的可持久化线段树就是这样一种数据结构，能够保存历史版本
算法内容
竞赛需要用到的点
1、可持久化线段树的空间消耗较大，使用时注意一下数据范围
2、可持久化线段树对于区间问题都能够解决，基本形态类似但是代码不同，需要熟练掌握主席树的原理与代码含义
可持久化线段树求第k大问题略讲
可持久化线段树可以维护很多东西，我们这里挑个比较常见的来讲，（该算法对于我这种人来说还是比较难，请观看人自己权衡）。考虑这样一个问题，每次修改都会保留一个时间戳，然后每次询问我们都会访问某个时间戳上的某个区间问题，很显然，正常的线段树并不能满足我们的需求，我们来考虑可持久化写法，若为单点修改，那么每次修改只会改变(logn)个节点，换个思路，修改就相当于我们可以多开(logn)个节点来保存修改之后的这些值，因为其他节点不变，所以我们可以共用这些节点。
共用节点？什么意思，可以参考下图(洛谷题解摘，实在是不想自己画了)
定义：橙色是改变前，蓝色是改变后 但仅有[1,4] [3,4] [4,4]为新建的点
我们发现，橙色的[1,4]和蓝色的[1,4]共用[1,2]这样的点，[1,2]的子树当然也不用多说，这样就能完成我们的可持久化操作了，但这样还有一个问题就是，怎么知道它们每个版本的情况怎么样？我们需要用一个数组保存节点个数，这样我们就能轻松反馈一个版本的情况了
解决完这些情况后，我们来考虑这道题，在分析第(k)大前我们需要在考虑一个东西就是，在([l, r])区间中找第(k)大，这个([l, r])区间怎么办，当你分析到这里的时候，其实答案也就呼之欲出了，以前缀和维护区间内容，什么意思？我们以每个叶子节点为一个数，每个区间为含有的数的个数作一棵权值线段树，那么就有，每一个含第一个数的前缀和就是一个版本，这样([1, l])就是一棵可持久化线段树，继而([1, r])也是一棵可持久化线段树，哎 因为我们用的前缀和进行建树，是不是每次版本也满足前缀和的性质呢？当然满足，也就是说我们想求([l, r])区间的第(k)大，我们可以用([1.r] - [1, l - 1]),这样便是我们的([l, r])了
满足了区间要求，我们再来满足我们的第(k)大要求，现在我们假设已经求出了([l,r])这个版本的权值线段树了，求第(k)大，我们考虑左子树，发现数量多于等于(k)，很明显我们的答案在左边。若少于(k)，很显然我们的答案在右侧，就往右边走，但要注意，往右边走时我们的第(k)大就变成了 (k) - 左子树（([1, mid])）所包含的数，这个可以自己画图理解
到此，我们就可以写出代码了
求第k大可持久化线段树部分代码展现
和线段树一样，有个建树
//#define fre yes
#include <cstdio>
const int N = 1000005;
int T[N];
struct Node {
int l, r, interval;
} tree[N << 5];
int cnt; //点的个数
void build(int l, int r) {
int rt = ++cnt;
tree[rt].l = l;
tree[rt].r = r;
tree[rt].interval = 0;
if(l == r) return ;
int mid = (l + r) >> 1;
build(l, mid);
build(mid + 1, r);
}
int main() {
build(1, m);
}
然后单点修改
int update(int pre, int l, int r, int x) { //update(T[g], 1, m, x) //g代表哪次版本
int rt = ++cnt;
tree[rt].l = tree[pre].l;
tree[rt].r = tree[prt].r;
tree[rt].interval = tree[pre].interval;
if(l == r) return rt;
int mid = (l + r) >> 1;
if(mid >= x) tree[rt].l = (tree[pre].l, l, mid, x);
else tree[rt].r = (tree[pre].r, mid + 1, r, x);
return rt;
}
然后单点查询
int query(int u, int v, int l, int r, int x) {
if(l == r) return l;
int t = tree[tree[v].l].sum - tree[tree[u].l].sum;
int mid = (l + r) >> 1;
if(t >= x) return query(tree[u].l, tree[v].l, l, mid, x);
else return query(tree[u].r, tree[v].r, mid + 1, r, x - t);
}
最后放一道例题 洛谷P3834
完整代码
//#define fre yes
#include <cstdio>
#include <algorithm>
const int N = 200005;
int a[N], b[N], T[N];
struct Node {
int l, r, sum;
} tree[N << 5];
int cnt;
void build(int l, int r) {
int rt = ++cnt;
tree[rt].l = l;
tree[rt].r = r;
tree[rt].sum = 0;
if(l == r) return ;
int mid = (l + r) >> 1;
build(l, mid);
build(mid + 1, r);
}
int update(int pre, int l, int r, int x) {
int rt = ++cnt;
tree[rt].l = tree[pre].l;
tree[rt].r = tree[pre].r;
tree[rt].sum = tree[pre].sum + 1;
if(l == r) return rt;
int mid = (l + r) >> 1;
if(mid >= x) tree[rt].l = update(tree[pre].l, l, mid, x);
else tree[rt].r = update(tree[pre].r, mid + 1, r, x);
return rt;
}
int query(int u, int v, int l, int r, int x) {
if(l == r) return l;
int sum = tree[tree[v].l].sum - tree[tree[u].l].sum;
int mid = (l + r) >> 1;
if(sum >= x) return query(tree[u].l, tree[v].l, l, mid, x);
else return query(tree[u].r, tree[v].r, mid + 1, r, x - sum);
}
int main() {
static int n, q;
scanf("%d %d", &n, &q);
for (int i = 1; i <= n; i++) {
int x;
scanf("%d", &a[i]);
b[i] = a[i];
}
std::sort(b + 1, b + 1 + n);
int m = std::unique(b + 1, b + 1 + n) - b - 1;
T[0] = 0;
build(1, m);
for (int i = 1; i <= n; i++) {
int t = std::lower_bound(b + 1, b + 1 + m, a[i]) - b;
T[i] = update(T[i - 1], 1, m, t);
}
for (int i = 1; i <= q; i++) {
int x, y, z;
scanf("%d %d %d", &x, &y, &z);
int t = query(T[x - 1], T[y], 1, m, z);
printf("%d
", b[t]);
} return 0;
}