POJ 2104为例（主席树入门题）
思想：
可持久化线段树，也叫作函数式线段树，也叫主席树（高大上）。
可持久化数据结构(Persistent data structure)：利用函数式编程的思想使其支持询问历史版本、同时充分利用它们之间的共同数据来减少时间和空间消耗。
主席树：对原序列的每一个前缀[1..i] 建立出一棵线段树维护值域上每个数的出现次数（所以要先离散化）。线段树每个节点保存的是区间中前缀对应的值出现的次数。
注意：
- 这里没有使用指针，而是给每个节点编号，通过编号来将节点与左右子节点连接起来。
- 对于前缀
[1,i] 和前缀[1,i+1] 的线段树，如果离散化后newa[i+1]<=mid ，那么这两棵线段树的右边是完全相同的，不需要重复建立。 - 查询过程，先查看左子树中元素的出现次数是否大于k，如果是，继续查左子树，反之查询右子树。
- 同一区间出现次数可以直接相减得到。
代码：
#include<cstdio>
#include<algorithm>
using namespace std;//[]
const int maxn = 100010, maxm = 20 * maxn;
int tot, c;
int a[maxn], newa[maxn];
int lson[maxm], rson[maxm], t[maxm], tree[maxm];
//lson,rson记录左右节点标号，t记录每一个前缀构成的线段树的根节点标号，tree记录标号对应区间中数字出现次数
int compress(int x)//离散化
{
return lower_bound(newa+1, newa+1+c, x) - newa;
}
int build(int l, int r)
{
int root = tot++; tree[root] = 0;
int mid = (l+r)/2;
if(l == r ) return root;
lson[root] = build(l, mid);
rson[root] = build(mid + 1, r);
return root;
}
void update(int root, int newroot, int l, int r, int num)
{
tree[newroot] = tree[root] + 1;
if(l == r) return;
int mid = (l + r)/2;
if(num <= mid){
lson[newroot] = tot++;//有变动，重新建立
rson[newroot] = rson[root];//右边不变
update( lson[root], lson[newroot], l, mid, num);
}else{
rson[newroot] = tot++;//有变动，重新建立
lson[newroot] = lson[root];//左边不变
update(rson[root], rson[newroot], mid + 1, r, num);
}
}
int query(int leftroot, int rightroot, int l, int r, int k)
{
if(l == r ) return l;
int mid = (l + r)/2;
if(tree[lson[rightroot]] - tree[lson[leftroot]] >= k){
query(lson[leftroot], lson[rightroot], l, mid, k);
}else{
int temp = tree[lson[rightroot]] - tree[lson[leftroot]];
query(rson[leftroot], rson[rightroot], mid + 1, r, k - temp);
}
}
int main (void)
{
int n,m;scanf("%d%d",&n,&m);
tot = 0;
for(int i = 1; i <= n; i++) {
scanf("%d",&a[i]);
newa[i] = a[i];
}
sort(newa+1, newa+1+n);
c = unique(newa+1, newa+1+n) - newa-1;//去重
t[0] = build(1, c);//初始化
for(int i = 1; i <= n; i++){
t[i] = tot++;
update(t[i-1], t[i], 1 , c, compress(a[i]));//不断更新，建树
}
int l, r, k;
while(m--){
scanf("%d%d%d",&l,&r,&k);
printf("%d
", newa[query(t[l-1], t[r], 1 ,c, k)]);
}
return 0;
}//1800ms
还是划分树快些。。。
真的是理解花了好久，连写再调试又花了好久。。。。。。然而只学了点毛皮。
动态区间第k大貌似要用到树状数组，过几天再来研究一下！