声明：本文中出现的“主席”二字仅为计算机领域一种数据结构的别名，请勿过度解读。
题目传送门：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;
}
文章评论