不修改的主席（HJT）树-HDU2665，POJ-2104；

参考：优秀的B站视频；

　　和 https://blog.csdn.net/creatorx/article/details/75446472

感觉主席树这个思路是真的优秀，每次在前一次的线段树的基础上建立一颗新的小线段树；所以更新和查询都是要前后两个根节点进行操作；

利用引用，只用修改此次的节点，而不动前一次的线段树；

主席树可用在求区间的第K大的数上：思路是：

我们也可以利用前缀和这个思想来解决建树这个问题，我们只需要建立n颗“前缀”线段树就行，第i树维护[1,i]序列，这样我们处理任意区间l, r时就可以通过处理区间[1,l - 1], [1,r]，就行，然后两者的处理结果进行相加相减就行。为什么满足相加减的性质，我们简单分析一下就很容易得出。如果在区间[1,l - 1]中有x个数小于一个数，在[1,r]中有y个数小于那个数，那么在区间[l,r]中就有y - x 个数小于那个数了，这样就很好理解为什么可以相加减了，另外，每颗树的结构都一样，都是一颗叶节点为n个的线段树。

这里还有一个利用vector离散化的操作；

hdu ac的：

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <string>

#include <vector>

using namespace std;

#define pb push_back

const int maxn = ;

struct node {

    int l,r;

    int sum;

}T[maxn*];

int a[maxn],root[maxn];

vector<int>v;

int getid(int x){

    return lower_bound(v.begin(),v.end(),x) - v.begin() + ;

}

int n,m,cnt,x,y,k;

void init(){

    v.clear();

    memset(T,,sizeof(T));

    cnt = ;

}

void update(int l,int r,int &x,int y,int pos)

{

    T[++cnt] = T[y]; T[cnt].sum++; x = cnt;

    if(l==r)return;

    int mid = (l+r)>>;

    if(mid>=pos)

        update(l,mid,T[x].l,T[y].l,pos);

    else update(mid+,r,T[x].r,T[y].r,pos);

}

int query(int l,int r,int x,int y,int pos)

{

    if(l==r)return l;

    int sum = T[T[y].l].sum - T[T[x].l].sum;

    int mid = (l+r)>>;

    if(sum >= pos)

        return query(l,mid,T[x].l,T[y].l,pos);

    else return query(mid+,r,T[x].r,T[y].r,pos - sum);

}

int main(){

    int t;

    scanf("%d",&t);

    while(t--)

    {

        init();

        scanf("%d%d",&n,&m);

        for(int i=; i<=n; i++)

        {

            scanf("%d", &a[i]);

            v.pb(a[i]);

        }

        sort(v.begin(), v.end());

        v.erase(unique(v.begin(),v.end()),v.end());

        for(int i=; i<=n; i++)

            update(,n,root[i],root[i-],getid(a[i]));

        for(int i=; i<=m; i++)

        {

            int le,ri,k;

            scanf("%d%d%d", &le,&ri,&k);

            printf("%d\n",v[query(,n,root[le-],root[ri],k)-]);

        }

    }

    return ;

}

POJ的

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <string>

#include <vector>

using namespace std;

#define pb push_back

const int maxn = ;

struct node {

    int l,r;

    int sum;

}T[maxn*];

int a[maxn],root[maxn];

vector<int>v;

int getid(int x){

    return lower_bound(v.begin(),v.end(),x) - v.begin() + ;

}

int n,m,cnt,x,y,k;

void update(int l,int r,int &x,int y,int pos)

{

    T[++cnt] = T[y]; T[cnt].sum++; x = cnt;

    if(l==r)return;

    int mid = (l+r)>>;

    if(mid>=pos)

        update(l,mid,T[x].l,T[y].l,pos);

    else update(mid+,r,T[x].r,T[y].r,pos);

}

int query(int l,int r,int x,int y,int pos)

{

    if(l==r)return l;

    int sum = T[T[y].l].sum - T[T[x].l].sum;

    int mid = (l+r)>>;

    if(sum >= pos)

        return query(l,mid,T[x].l,T[y].l,pos);

    else return query(mid+,r,T[x].r,T[y].r,pos - sum);

}

int main(){

    scanf("%d%d",&n,&m);

    for(int i=; i<=n; i++)

    {

        scanf("%d", &a[i]);

        v.pb(a[i]);

    }

    sort(v.begin(), v.end());

    v.erase(unique(v.begin(),v.end()),v.end());

    for(int i=; i<=n; i++)

        update(,n,root[i],root[i-],getid(a[i]));

    for(int i=; i<=m; i++)

    {

        int le,ri,k;

        scanf("%d%d%d", &le,&ri,&k);

        printf("%d\n",v[query(,n,root[le-],root[ri],k)-]);

    }

    return ;

}

巴特西

不修改的主席（HJT）树-HDU2665，POJ-2104；

最新文章

热门文章