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\n", newa[query(t[l-1], t[r], 1 ,c, k)]);

    }

    return 0;

}//1800ms

还是划分树快些。。。

真的是理解花了好久，连写再调试又花了好久。。。。。。然而只学了点毛皮。

动态区间第k大貌似要用到树状数组，过几天再来研究一下！