A Huster

0%

主席树初步

Posted on Valine:

前置知识

　　1.线段树。。。

　　（好像没了

　　2.（可知可不知，可能会有帮助）动态开点线段树

主席树(可持久化线段树)

　　一看可持久化,我们总会想到一些恐怖的算法.但是其实理解并不难,而这里我只是将主席树的思想讲清楚(尽量),题还是自己刷(虽然我就没刷几道

　　先看一道 模板题

题目描述

如题，给定N个整数构成的序列，将对于指定的闭区间查询其区间内的第K小值。

输入格式

第一行包含两个正整数N、M，分别表示序列的长度和查询的个数。

第二行包含N个整数，表示这个序列各项的数字。

接下来M行每行包含三个整数l,r,k l, r, kl,r,k , 表示查询区间[l,r][l, r][l,r]内的第k小值。

输出格式

输出包含k行，每行1个整数，依次表示每一次查询的结果

　　我们发现这道题很难处理,因为我们没有学过什么数据结构可以维护区间第k大;

　　那么如何处理这个数组是一个关键;

　　回顾一下,我们在求前缀和时,如何求一个区间的和?用一个前缀和去减另一个前缀和.

　　类比一下,我们是否可以用一个区间减去另一个区间得到第k大?

　　是可以的.这里引入平衡树中一个操作,平衡树左子树维护比这个节点值小的子树,右子树维护比这个节点值大的子树;

　　平衡树是如何操作的呢?

　　保存每个节点的子树大小,比较排名k与左子树的大小,排名k小于左子树大小,那么我们要找的点一定在左子树上,那么走左子树;

　　如果排名比左子树大,那么将排名减去左子树大小和自身,走右子树

　　alt

　　注意,这个一定要看懂!

　　这个概念如果理解了话,那么就简单了.考虑线段树也是一颗二叉树,与平衡树一个性质,并且线段树本质维护的就是区间,那么我们考虑维护一个值域线段树.

　　那么就可以初略的定义,主席树是维护一颗值域线段树,将每一个位置作为一个时间点,继承前一个点,并添加自己的值.

　　如果要求区间 l 到 r 第k大,那么就可以用 r 时间点的线段树减去 l - 1 时间点的线段树,然后得到这个区间中某个值域中有多少个数,然后用上面所说类似于平衡树的做法,

　　(图我是真的画不出来了QAQ)

　　为了补偿,在代码中会有详细解释

　　Code

　　

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<bits/stdc++.h>
#define maxn 400007
using namespace std;
int n,m,tot,a[maxn],b[maxn];

template<typename type_of_scan>
inline void scan(type_of_scan &x){
    type_of_scan f=1;x=0;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    x*=f;
}
template<typename Tops,typename... tops>
inline void scan(Tops &x,tops&... X){
    scan(x),scan(X...);
}
template<typename type_of_print>
inline void print(type_of_print x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) print(x/10);
    putchar(x%10+'0');
}

struct node{
    int l,r,sum;
};

struct tree{
    node tr[maxn*20];int t[maxn>>1]; 
    void add(int &rt,int pre,int l,int r,int x){
        rt=++tot;//建一个点保存新的信息 
        tr[rt]=tr[pre],tr[rt].sum++;
        //继承前面节点,并且添加自身 
        if(l==r) return ;
        int mid=l+r>>1;//这里需要注意,l和r是表示值域 
        if(mid>=x) add(tr[rt].l,tr[pre].l,l,mid,x);
        else add(tr[rt].r,tr[pre].r,mid+1,r,x);
        //这里就可以看出主席树的优越性,每一次建logn个点 
    }
    //从此可以看出来,每次加的只有一条从根到叶子的新边(其他边是继承前面的 
    //因此空间复杂度nlogn,注意一下数组 
    int query(int u,int v,int l,int r,int k){
        if(l==r) return l;//返回位置 
        int mid=l+r>>1;
        int x=tr[tr[v].l].sum-tr[tr[u].l].sum;
        //用时间靠后的减去时间靠前的,
        //得到区间信息 
        if(k<=x) return query(tr[u].l,tr[v].l,l,mid,k);
        else return query(tr[u].r,tr[v].r,mid+1,r,k-x);
        //类似于平衡树操作 
    }
}t;

int main(){
    scan(n,m);
    for(int i=1;i<=n;i++)
        scan(a[i]),b[i]=a[i];
    sort(b+1,b+1+n);
    int ol=unique(b+1,b+1+n)-b-1;
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(b+1,b+1+ol,a[i])-b;
        //离散化
        t.add(t.t[i],t.t[i-1],1,ol,a[i]);
        //注意建立新的节点时,要继承前一个时间段的 
    }//不用建树,直接上 
    for(int i=1,l,r,k;i<=m;i++){
        scan(l,r,k);
        int pos=t.query(t.t[l-1],t.t[r],1,ol,k);
        printf("%d\n",b[pos]);
    }
    return 0;
}

总结　　

　　这样大概就讲完了思想,这里介绍一道 水题 ,不过对于加深主席树的思想有重大帮助(将主席树看成一颗前缀线段树)

　　我会附上我的代码(因为码风大家都不太相同,如果与我的码风相似了话,看起来就会很享受)

　　Code

　　

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include<bits/stdc++.h>
#define maxn 100007
using namespace std;
int n,m,fa[maxn],head[maxn],son[maxn],sz[maxn],ol;
int T[maxn],tot,a[maxn],top[maxn],dep[maxn],b[maxn];
int lastans,cent;
struct node{
    int next,to;
}edge[maxn<<1];
struct ML{
    int l,r,sum;
};

template<typename type_of_scan>
inline void scan(type_of_scan &x){
    type_of_scan f=1;x=0;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    x*=f;
}
template<typename Tops,typename... tops>
inline void scan(Tops &x,tops&... X){
    scan(x),scan(X...);
}
template<typename type_of_print>
inline void print(type_of_print x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) print(x/10);
    putchar(x%10+'0');
}

inline void add(int u,int v){
    edge[++cent]=(node){head[u],v};head[u]=cent;
    edge[++cent]=(node){head[v],u};head[v]=cent;
}

struct tree{
    ML tr[maxn*20];
    void add(int &rt,int pre,int l,int r,int x){
        rt=++tot;
        tr[rt]=tr[pre],tr[rt].sum++;
        if(l==r) return ;
        int mid=l+r>>1;
        if(x<=mid) add(tr[rt].l,tr[pre].l,l,mid,x);
        else add(tr[rt].r,tr[pre].r,mid+1,r,x);
    }
    int query(int u,int v,int lca,int flca,int l,int r,int k){
        if(l==r) return l;
        int mid=l+r>>1;
        int x=tr[tr[u].l].sum+tr[tr[v].l].sum-tr[tr[lca].l].sum-tr[tr[flca].l].sum;
        if(k<=x) return query(tr[u].l,tr[v].l,tr[lca].l,tr[flca].l,l,mid,k);
        else return query(tr[u].r,tr[v].r,tr[lca].r,tr[flca].r,mid+1,r,k-x);
    }
}t;

void dfs1(int x){
    sz[x]=1;t.add(T[x],T[fa[x]],1,ol,a[x]);
    for(int i=head[x];i;i=edge[i].next){
        int y=edge[i].to;
        if(y==fa[x]) continue;
        fa[y]=x;dep[y]=dep[x]+1;
        dfs1(y);sz[x]+=sz[y];
        if(sz[son[x]]<sz[y]) son[x]=y;
    }
}

void dfs2(int x,int tp){
    top[x]=tp;
    if(!son[x]) return ;
    dfs2(son[x],tp);
    for(int i=head[x];i;i=edge[i].next){
        int y=edge[i].to;
        if(y==fa[x]||y==son[x]) continue;
        dfs2(y,y);
    }
}

int get_lca(int x,int y){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        x=fa[top[x]];
    }
    return dep[x]<dep[y]?x:y;
}

int main(){
    scan(n,m);
    for(int i=1;i<=n;i++) scan(a[i]),b[i]=a[i];
    sort(b+1,b+1+n);
    ol=unique(b+1,b+1+n)-b-1;
    for(int i=1;i<=n;i++)
        a[i]=lower_bound(b+1,b+1+ol,a[i])-b;
    for(int i=1,u,v;i<=n-1;i++)
        scan(u,v),add(u,v);
    dfs1(1),dfs2(1,1);
    for(int i=1,u,v,k;i<=m;i++){
        scan(u,v,k);u^=lastans;
        int lca=get_lca(u,v);
        int pos=t.query(T[u],T[v],T[lca],T[fa[lca]],1,ol,k);
        printf("%d\n",b[pos]);lastans=b[pos];
    }
}

如果你看完了这篇博客并想骂博主讲的太简单,说明你已经超越博主了QAQ

end

本站访问次数：