Part 1 简介
可持久化线段树(在中国国内信息学竞赛社区中又称总书记树、主席树或函数式线段树)是一种可持久化数据结构（Persistent data structure）. 由于引入者黄嘉泰姓名的缩写与前中共中央总书记、国家主席胡锦涛相同，因此这种数据结构也可被称为总书记树或主席树。这种数据结构在普通线段树的基础之上支持查询某个历史版本，同时时间复杂度与线段树是同级，空间复杂度相较而言更高。
Part 2 应用
静态区间第k大数值
这类问题需要求解在一个长度为$ {\displaystyle n}$ 的数列中，第$ {\displaystyle i} $个数为$ {\displaystyle a_{i}}$. 现在给定一些形如 ${\displaystyle (l,r,k)} $的三元组作为询问，设计程序计算数列第$ {\displaystyle l~r} $这些元素中出现次数排在第$ {\displaystyle k} $位的是多少。
利用可持久化线段树，维护区间$ {\displaystyle (l,r)} $代表区间$ {\displaystyle [l,r]} $中的元素出现了多少次，以此作为原始版本$ {\displaystyle S_{0}}$，此后每次建立一个新版本 ${\displaystyle S_{i}}$，代表去掉原数列中 ${\displaystyle a_{0}~a_{i-1}} $的元素之后建立的线段树，维护目标与上述相同。具体过程可以每次将$ {\displaystyle a_{i}}$的出现次数减一，并保存此时生成的新版本。
Part 3 代码实现
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#define MAX_N 200005
using namespace std;
int tot, n, m;
int sum[(MAX_N << 5) + 10], rt[MAX_N + 10], leftson[(MAX_N << 5) + 10], rightson[(MAX_N << 5) + 10];
int a[MAX_N + 10], ind[MAX_N + 10], len;
int l, r, k;
//查找最小下标的匹配值
int getid(const int &val) { return lower_bound(ind + 1, ind + len + 1, val) - ind; }
int build(int l, int r) {
int root = ++tot;
if (l == r) return root;
int mid = (l + r) >> 1;
leftson[root] = build(l, mid);
rightson[root] = build(mid + 1, r);
return root;
} //建树
//节点k代表区间[l,r]
//插入操作
int update(int k, int l, int r, int root) {
int dir = ++tot;
leftson[dir] = leftson[root], rightson[dir] = rightson[root], sum[dir] = sum[root] + 1; //新节点
if (l == r) {
//sum[dir] = t; 如果题目要求sum加t，去掉注释然后去掉上面的+1
return dir;
} //递归底层返回新节点编号，修改父节点的儿子指向
int mid = (l + r) >> 1;
if (k <= mid)
leftson[dir] = update(k, l, mid, leftson[dir]);
else
rightson[dir] = update(k, mid + 1, r, rightson[dir]);
//sum[dir] = sum[lc[dir]] + sum[rightson[dir]];在该题中，不需要这样做，但是很多情况下是要这样更新的
return dir;
}
//初始的u和v分别代表的是点l-1和点r，l和r分别表示线段树点代表的区间，初始的k表示查询第k小
//查询（历史区间和）
int section_ask(int u, int v, int l, int r, int k) {
int mid = (l + r) >> 1;
int x = sum[leftson[v]] - sum[leftson[u]]; //左儿子的信息
//因为主席树是区间统计好了的，只要减一下即可，无需递归到叶子再处理
if (l == r) return l; //找到目标位置
if (k <= x) //说明在左儿子中
return section_ask(leftson[u], leftson[v], l, mid, k);
else //说明在右儿子中
return section_ask(rightson[u], rightson[v], mid + 1, r, k - x);
}
void init() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", a + i);
memcpy(ind, a, sizeof ind);
sort(ind + 1, ind + n + 1);
len = unique(ind + 1, ind + n + 1) - ind - 1;
rt[0] = build(1, len);
for (int i = 1; i <= n; i++) rt[i] = update(getid(a[i]), 1, len, rt[i - 1]);
}
void work() {
while (m--) {
scanf("%d%d%d", &l, &r, &k);
printf("%d\n", ind[section_ask(rt[l - 1], rt[r], 1, len, k)]);
}
}
int main() {
init();
work();
return 0;
}
参考：
