可持久化线段树(主席树)
1.主席树是可以留存历史版本的线段树并且节省空间
操作：一般如果该节点的其中一个子树内容不变，可以直接指引到历史版本的内容，节省重新建立导致新开辟的空间，用模板题来讲解代码
题目来源
给定 n 个整数构成的序列 a，将对于指定的闭区间 [l,r] 查询其区间内的第 k 小值
解决这个问题可以留存 [1..i] 的权值线段树 (先讲解权值线段树)
权值线段树
“权值线段树就是对一个值域上值的个数进行维护的线段树”原视频09:51
---不分解的AgOH
回归正题，已经知道了权值线段树，本题可以利用权值线段树先建树，后递归查询，如果$ [l,(l+r)/2] 的个数 <=k ，左子树递归，反之右子树递归
本题数据范围较大， -10^9 <= a <= 10^9 但是 n <= 2 x 10^5 说明可以进行离散化让权值线段树的空间节省
而且本题不需要提前建树，因为初始值为 0 ，初始化已经完成了
接下来写代码
const int N = 2e5+2;
int n,m,a[N],cnt,root[N];
vector<int> v;
struct node{int l,r,sum;
}hjt[N*40];
cnt 当作线段树储存版本， root 即每一个版本的根节点， v 数组进行离散化处理
cin>>n>>m;
for(int i=1;i<=n;i++){cin>>a[i];v.push_back(a[i]);
}
sort(v.begin(),v.end());
v.erase(unique(v.begin(),v.end()),v.end());
将 v 数组排序后去重
(注: unique 函数会去重并且指向最后一位的迭代器，可以使用 erase 进行删除剩余部分)
int getid(int x){return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}
void insert(int l,int r,int pre,int &now,int p){hjt[++cnt]=hjt[pre];now=cnt;hjt[now].sum++;if(l==r)return;int mid=(l+r)>>1;if(p<=mid)insert(l,mid,hjt[pre].l,hjt[now].l,p);else insert(mid+1,r,hjt[pre].r,hjt[now].r,p);
}
//main函数内部
for(int i=1;i<=n;i++){insert(1,n,root[i-1],root[i],getid(a[i]));
}
getid() 函数进行离散化
main 内部遍历 i 进行存储 [1..i] 的权值线段树
insert() 函数先复制上一个版本的线段树由于只是单点修改所以修改范围不大，后续进行修改即可，并且 now 指向 cnt ，如果 l=r 说明处于叶子节点 return ，否则进行 mid 如果插入的 p <= 中间值放到左子树，反之插入到右子树
int query(int ln,int rn,int l,int r,int k){//r表示r版本.sum - l表示l-1版本.sum=answer if(ln==rn)return ln;int mid=(ln+rn)>>1;int tmp=hjt[hjt[r].l].sum-hjt[hjt[l].l].sum;if(k<=tmp)return query(ln,mid,hjt[l].l,hjt[r].l,k);else return query(mid+1,rn,hjt[l].r,hjt[r].r,k-tmp);
}
//main函数内部
while(m--){int l,r,k;cin>>l>>r>>k;cout<<v[query(1,n,root[l-1],root[r],k)-1]<<"\n";
}query() 里面当 ln=rn 说明到达叶子节点，返回 ln 也就是离散化后的值，没有到达叶子节点需要求解 [l-1,r] 的左子树个数，如果 k <= tmp 说明第k小就在左子树，反之在右子树，进行递归并返回(注:参数里 l 表示的 l-1 的版本)
由于 query() 返回的离散化后的值，需要反接，也就是套个 v
query() 的 tmp 求解解剖：
tmp=hjt[hjt[r].l].sum-hjt[hjt[l].l].sum
hjt[r].l是[1,r]数列中[1,中间值]的个数
hjt[l].l是[1,l]数列中[1,中间值]的个数
综合起来就是[l+1,r]数列中[1,中间值]的个数