主席树模板 / 区间第k小 / p3834

前言

主席树的全称是可持久化权值线段树，关键词有两个，一个是可持久化，一个是权值线段树

主席树与普通线段树有不少区别，学主席树之前最好学一下权值线段树，

理解其蕴含的前缀存储思想

可以把权值线段树理解为一个桶，每个叶子节点leaf[k]存的是a[1, …, n]中，k出现的次数

因此在构建主席树之前应当将数据离散化处理一下，这里由dispersed()和find()完成

主席树与普通权值线段树的区别主要在于增加了可持久化功能，

具体表现为update()函数的动态开点功能（开出历史存档），

以及query对不同版本的树根查询（借鉴了权值线段树的前缀存储思想）

一、 例题 p3834

二、 思路及代码 1. 思路

很经典的主席树入门，直接套模板即可

2. 代码

代码如下 ：

#include 
#include 
using namespace std;
const int maxn = 2e5 + 7;
int root[maxn], id, len = 1;
int a[maxn], b[maxn];
int n, m;
struct ptree {
  int l, r;
  int cnt;  // 权重线段树
} t[maxn  1;
  t[cur].l = build(l, mid);
  t[cur].r = build(mid + 1, r);
  return cur;
}
int update(int pre, int x, int l, int r) {
  int cur = ++id;
  int mid = l + r >> 1;
  t[cur] = t[pre], t[cur].cnt++;  // 权值++
  if (l  1;  // 即1 - tmp排名的节点均在左子树
  if (k