声明：本文中出现的“主席”二字仅为计算机领域一种数据结构的别名，请勿过度解读。

题目传送门：P3834 【模板】可持久化线段树 2 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题意请看原题链接。

最近在学习主席树，用这篇文章做一个总结。

什么是主席树？/ What is?

主席树是由黄嘉泰dalao改进得到的，因为名字的首字母为HJT，故名主席树（猜测）。

从概念上讲，主席树是线段树的一种延伸。

但是通俗的说，主席树就是“对线段树的前缀和”。经常和权值线段树，又名可持久化权值线段树。

新增节点 / Insert

数组中每新增一个点，主席树就要多出logN个点来形成一条新的链并连接到之前的树中，共用相同的部分，新增的部分与后面的新增的树共用。

上图中橙色的为“历史节点”，右边新增的蓝色的为“新增节点”。

主席树的一个节点需要将儿子的下标记录下来。用一个结构体表示为：

struct Node{int ls, rs, v;}

类似前缀和地，每次新增一条链，都会先将之前的链的信息复制到当前的链（包括左右儿子和权值），如果需要修改就修改，不用修改就让他去吧。

每次insert操作，需要用到当前树的根（利用&o变量自动新建一个），上一棵树的根（已经算出了），新增的数字x，区间1~N。

这里insert的x是下标(index)，并不是值(value)，表达的含义是数字x的数量+1。

insert函数完整版如下：

void insert(int &o, int pre, int x, int s = 1,int e = N)
{
	if(x < s || e < x)return;//递归出口，如果当前区间[s, e]和x无关就跳出 
	o = ++ idx;//分配一个节点给o，这个o引用类型会传给上一个点的ls或者rs 
	t[o] = t[pre];//将信息完全复制 
	t[o].v ++;//表示在这个节点下的区间中，多了1个数字 x 
	if(s == e)return;//到叶子节点就跳出 
	int mid = (s + e) / 2;//递归处理左右子树 
	insert(t[o].ls, t[pre].ls, x, s, mid);
	insert(t[o].rs, t[pre].rs, x,mid+1,e);
}

值得注意的是，主席树只能单点修改，区间查询。

查询 / Query

查询结果为元素权值大小位于区间[l, r]中个数。

这里要求第k小的数字。

每次算出左子树有多少个元素(left_sum)，如果>=k，那么答案肯定在左子树，如果<k，答案肯定在右子树，注意递归右子树时，不能再找第k小的，应该找右子树中第k - left_sum小的。

int query(int lnode,int rnode,int k,int s = 1,int e = N)
{
	if(s == e)return s;//如果到了叶子节点，说明找到了我们要的值（在离散化数组中的下标） 
	int mid = (s + e) / 2;
	//计算左子树中元素个数 
	int left_sum = t[t[rnode].ls].v - t[t[lnode].ls].v; 
	if(left_sum >= k)//如果左子树的元素个数大于等于k说明答案肯定在左子树中 
		return query(t[lnode].ls, t[rnode].ls, k, s,  mid);
	return query(t[lnode].rs, t[rnode].rs, k - left_sum,mid+1,e);
}

完整带注释代码 / Complete Code with Explain

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 2e5 + 9;
int root[maxn], idx = 0, N, M, a[maxn];
struct Node{int ls, rs, v;}t[maxn << 6];
vector<int> v;

void insert(int &o, int pre, int x, int s = 1,int e = N)
{
	if(x < s || e < x)return;//递归出口，如果当前区间[s, e]和x无关就跳出 
	o = ++ idx;//分配一个节点给o，这个o引用类型会传给上一个点的ls或者rs 
	t[o] = t[pre];//将信息完全复制 
	t[o].v ++;//表示在这个节点下的区间中，多了1个数字 x 
	if(s == e)return;//到叶子节点就跳出 
	int mid = (s + e) / 2;//递归处理左右子树 
	insert(t[o].ls, t[pre].ls, x, s, mid);
	insert(t[o].rs, t[pre].rs, x,mid+1,e);
}

int query(int lnode,int rnode,int k,int s = 1,int e = N)
{
	if(s == e)return s;//如果到了叶子节点，说明找到了我们要的值（在离散化数组中的下标） 
	int mid = (s + e) / 2;
	//计算左子树中元素个数 
	int left_sum = t[t[rnode].ls].v - t[t[lnode].ls].v; 
	if(left_sum >= k)//如果左子树的元素个数大于等于k说明答案肯定在左子树中 
		return query(t[lnode].ls, t[rnode].ls, k, s,  mid);
	return query(t[lnode].rs, t[rnode].rs, k - left_sum,mid+1,e);
}

signed main()
{
	scanf("%lld %lld", &N, &M);	
	for(int i = 1;i <= N; ++ i)
	{
		scanf("%lld", a + i);
		v.push_back(a[i]);
	}
	sort(begin(v), end(v));//离散化，用排序后的位置表示某个数字 
	for(int i = 1;i <= N; ++ i)
		insert(root[i], root[i - 1], lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1);
	//注意这里要+1，与a数组保持一致化 
	while(M --)
	{
		int l, r, k;scanf("%lld %lld %lld", &l, &r, &k);
		printf("%lld\n",v[query(root[l - 1], root[r], k, 1, N) - 1]);
		//因为前面的数字+1，所以这里需要-1来访问v中的对应下标的元素 
	}
	return 0;
}