主席树

主席树（可持久化线段树）

问题描述：

给定N个数（int范围内），一共M次询问，每次都要询问区间[[l,r]的第k大的数。 其中N, M, l, r均不超过$2\times10^5$，保证询问有答案

​ 主席树本名可持久化线段树，也就是说，主席树是基于线段树发展而来的一种数据结构。其前缀”可持久化”意在给线段树增加一些历史点来维护历史数据，使得我们能在较短时间内查询历史数据，图示如下。

当每插入一个数据时，会修改$logn$个节点，因为主席树的左右子树节点编号不能够计算得到，而是需要记录下来。

static constexpr int N = 200010
int rt[N]                  // 记录插入第i个数后的根节点
int ls[N << 5], rs[N << 5] // 记录左儿子，右儿子
int sum[N << 5]            // 记录当前节点区间的元素个数

• 将数组复制一份，进行排序，去掉重复的数字离散化。

• 以离散化后的数组为基础建立一个全零的线段树，称为基础主席树

• 对原数据中每一个[1,i]区间统计，有序地插入新节点，i每增加1，就会多一个数，仅需对主席树对应的节点增加1即可

• 对于查询[l, r]中第k小值的操作，找到[l, r]对应的根节点，按照线段树操作的方法即可

建立基础主席树

void build(int &u, int l, int r) {
	u = ++tot;
	if (l == r) return;
	int mid = l + (r - l) / 2;
	build(ls[u], l, mid);
	build(rs[u], mid + 1, r);
}

向主席树中加入元素

int modify(int pre, int l, int r, int x) {
	int cur = ++tot;
	ls[cur] = ls[pre]; rs[cur] = rs[pre]; sum[cur] = sum[pre] + 1;
	if (l == r) return cur;
	int mid = l + (r - l) / 2;
    if (x <= mid) ls[cur] = modify(ls[cur], l, mid);
    else rs[cur] = modify(rs[cur], mid + 1, r);
	return cur;
	
}

查询区间第k大，注意区间下标是从1开始

int query(int u, int v, int l, int r, int k) {
    int ans = 0, x = sum[ls[v]] - sum[ls[u]];
    int mid = l + (r - l) / 2;
    if (l == r) return l;
    if (k <= x) ans = query(ls[u], ls[v], l, mid, k);
    else ans = query(rs[u], rs[v], mid + 1, r, k - x);
    return ans;
}