值得一提的是，静态主席树比单纯的线段树求区间和要短……
0 前置技能点
- 线段树
- 前缀和
- 离散化(权值线段树求第k大前置技能）
正常状况下的大脑一定的Debug能力
1 主席树
1.1 静态
1.1.1 权值线段树
我们现在看一下这个问题
区间第$k$大
我会排序！
$ N,M \leq 2e5$
我会排序！等下，时间复杂度不对
是的，显然这需要一个数据结构来维护它
我们来想想，如果只求第$k$大的话，有什么做法？
平衡树，权值线段树
加上区间查询？
我会Splay！
嗯，
Splay是一个比较优秀的解决方案,
但是权值线段树真的没有用武之地吗
1.1.2 可持久化
可持久化
这是一个非常有趣的名词
许多数据结构都可以可持久化
eg: 可持久化数组，可持久化平衡树，可持久化并查集等
什么是可持久化呢
可以访问历史版本的数据结构，我们通常就称其为可持久化数据结构
1.1.3 前缀和与权值线段树
我们先来回顾一下如果我们查询全局第$k$大时的步骤
- 离散化
- 按排名建立权值线段树
- 按照与二叉搜索树中查找第$k$大一样的方法查找并输出
有一种办法，建立 $ n^2 $ 棵线段树（枚举每个区间），但这种做法显然是不且实际的
但是如果我们仔细思考便会发现，我们对与区间$ [1,1] [1,2] [1,3] [1,4] \cdots [1,n] $ 中建立的权值线段树中的每一个节点都满足前缀和性质
也就是说我们只需要建立$n$棵权值线段树了
1.1.4 可持久化与权值线段树
到了这一步，我们的问题在空间与时间上都存在了
很明显，我们的空间有太多重复的叶子节点[区间相同，权值相同]
所以如果两个节点，它们的左节点（或者右节点）重复，我们可以将它们指向一个叶子
经过这么操作我们的时间也得到了大幅度优化，从原来的$O(n^2log(n))$变成了$O(nlog(n))$,空间也优化到$nlog(n)$
这么一来，这些线段树变成一个数据结构，我们可以访问历史版本
是的，这就是可持久化权值线段树，也称主席树
1.1.5 静态主席树
#include <cstdio>
#include <algorithm>
const int N=2e5+1e4;
int n,m,l,r,k,tcnt,idcnt;
int nid[N],rt[N],rk[N];
struct val{
int now,id;
}a[N];
bool cmp(val a,val b){
return a.now<b.now;
}
struct Persistable_Segment_Tree{
int left,rig;
int sum;
}tree[N*20];
void update(int &root,int left,int rig,int val){
tree[tcnt++]=tree[root];
tree[tcnt-1].sum++;
root=tcnt-1;
if(left==rig) return ;
int mid=(left+rig)>>1;
if(val<=mid) update(tree[root].left,left,mid,val);
else update(tree[root].rig,mid+1,rig,val);
}
int query(int left_root,int rig_root,int k,int left,int rig){
int dep=tree[tree[rig_root].left].sum-tree[tree[left_root].left].sum;
if(left==rig) return left;
int mid=(left+rig)>>1;
if(k<=dep) return query(tree[left_root].left,tree[rig_root].left,k,left,mid);
else return query(tree[left_root].rig,tree[rig_root].rig,k-dep,mid+1,rig);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i].now);
a[i].id=i;
}
std::sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++)
rk[a[i].id]=i;
tcnt=1;
for(int i=1;i<=n;i++){
rt[i]=rt[i-1];
update(rt[i],1,n,rk[i]);
}
for(int i=1;i<=m;i++){
scanf("%d%d%d",&l,&r,&k);
printf("%d\n",a[query(rt[l-1],rt[r],k,1,n)].now);
}
}