可持久化线段树/主席树入门

在wmf大佬怂恿一天学习一个数据结构每天划水下,大概理清可持久化线段树,又名主席树的大致思路和代码实现。

今天JZ的雨,下得更加的猛烈了QAQ

  • 前言

  • 主席树为什么叫主席树呢? 

    因为发明它的fotile被我们叫做fotile主席,所以就叫主席树。 

  • 去年就尝试过学这东西,果然是IQ过低,完全看不懂,今年再看,发现并不是想象中的那么难QWQ

 

  • 引题: P3834 【模板】可持久化线段树 1(主席树)

  • 题意:给出一些数,对于多次询问,每次询问一个区间[l,r]中第k小的数是多少。

  • 来思考下怎么解决这道题

    • 首先是初学者都会的方法,对于每次询问把[l,r]区间排序一遍即可,但是这个时间复杂度我们难以接受QAQ
    • 我们考虑一个线段树的做法,假如一个区间[l, r]我们用这个区间内出现过的数的个数组成一颗线段树,这是什么意思呢,求一个区间的第k小数,当然与这个区间有多少数比他小有关,这颗线段树上的每个节点维护的是这个节点表示区间内的数的个数(假设每个数都不一样)
    • 我们首先只需要将这些数进行离散化即可,然后将这些离散化后的数插入线段树中,维护每个节点值表示这个节点表示区间内的数的个数,然后对于询问,我们判断左区间的数的个数是否大于k,如果大于,就证明第k小的数在左儿子区间内,如果小于,就证明在右儿子区间内,我们这样就得到了一个比较暴力的线段树的作法。
    • 但是我们发现,对于每次询问,我们都要建一棵线段树,这样子对于多次查询,时间复杂度和空间复杂度都会非常的高,甚至比最暴力的作法还慢。
    • 我们考虑通过前缀和的思想优化,我们设sum[i]表示1~i的区间内的情况,那么我们对于要求的区间[l,r],只需要通过sum[r]-sum[l-1]就可以快速得到我们所要的答案,这样我们只需要一次建树即可,但是,这样我们仍然要建n棵线段树,显然是不够优秀的,那么如何来改进呢?
    • 接下来就是主席树的精华所在:我们通过观察线段树的结构可知,假设我们已经建完了1~i的这棵线段树,我们来思考一下对于1~i+1这棵线段树与前一棵线段树有什么异同?因为实际上我们只是新增了第i+1个数,我们知道,对于线段树,新增一个数最多只会修改logn个节点,那么对应到主席树上,就证明当前这棵树和上一棵树最多只有logn个节点的状态不同,而如果我们每次重新建一棵线段树,其实就是重复建了许多以前已经建过的节点,所以,主席树的思想就是考虑如何将这些节点利用起来。
    • 我们可以通过该题的代码片段来分析

      • 首先是对于线段树的一些定义
      • 
        
        1
        2
        3
        4
        5
        6
        7
        8
        9
        struct node
        {
            int L,R;//分别指向左右子树
            int sum;//该节点所管辖区间范围内数的个数
            node()
            {
                sum=0;
            }
        }tree[N*20];//因为每插入一个数会增加log n个节点,所以要开大logn倍
      • 要注意的是,我们这里因为要重复利用节点,所以不采用传统线段树的堆式存储法
      • 对于一些其他的定义
      • 
        
        1
        2
        3
        4
        5
        6
        7
        8
        struct vv
        {
            int v;//值的大小
            int id;//离散之前在原数组中的位置
        }val[N];
        int n,m,cnt;
        int root[N];//多颗线段树的根节点
        int rank[N];//原数组离散之后的数组
      • 然后是一些初始化和排序的函数
      • 
        
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        bool cmp(vv aa,vv bb)
        {
            return aa.v<bb.v;
        }

        void init(void)
        {
            cnt=1;
            root[0]=0;
            tree[0].L=tree[0].R=tree[0].sum;
        }
      • 我们先来看修改/插入函数
      • 
        
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        void amend(int num,int &rt,int l,int r)
        //num-该数离散化后的值  rt-前一段前缀的根    l~r - 表示区间
        {
            tree[cnt]=tree[rt];
            cnt++;
            rt=cnt-1;
            tree[rt].sum++;
            if(l==r) return;
            int mid=(l+r)>>1;
            if (num<=mid)   amend(num,tree[rt].L,l,mid);
            else    amend(num,tree[rt].R,mid+1,r);
        }
      • 我们对于插入一个数num,rt是前一段前缀的根的编号,因为我们要重复利用那些相同的节点,我们把新的根先复制一遍上一个根,就巧妙地得到了上一棵线段树的所有信息,接下来我们只需要去修改新插入的这个数,因为最多修改logn个节点,所以新增的节点个数也是logn的。 
      • 接下来看看如何查询区间第k小
      • 
        
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        int query(int lr,int rr,int k,int l,int r)
        {
            int d=tree[tree[rr].L].sum-tree[tree[lr].L].sum;
            //在区间给定的范围内,左区间有d个数(从小到大)
            if (l==r)   return l;
            int mid=(l+r)>>1;
            if (k<=d)   return query(tree[lr].L,tree[rr].L,k,l,mid);
            //如果第k小在左区间,直接在左区间寻找第k个数即可
            else    return query(tree[lr].R,tree[rr].R,k-d,mid+1,r);
            //如果第k小在右区间,在右区间寻找第k-d个数即可
        }
      • 利用前缀和的思想,可以快速求出左区间有d个数,只需要将d和k比较大小关系再来询问左右区间即可OwO
      • 完全体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
        #include<cstdio>
        #include<cstring>
        #include<cmath>
        #include<algorithm>
        #include<iostream>
        using namespace std;

        const int N=2e5+10;

        struct node
        {
            int L,R;//分别指向左右子树
            int sum;//该节点所管辖区间范围内数的个数
            node()
            {
                sum=0;
            }
        }tree[N*20];//因为每插入一个数会增加log n个节点,所以要开大logn倍

        struct vv
        {
            int v;//值的大小
            int id;//离散之前在原数组中的位置
        }val[N];
        int n,m,cnt;
        int root[N];//多颗线段树的根节点
        int rank[N];//原数组离散之后的数组

        bool cmp(vv aa,vv bb)
        {
            return aa.v<bb.v;
        }

        void init(void)
        {
            cnt=1;
            root[0]=0;
            tree[0].L=tree[0].R=tree[0].sum;
        }

        void amend(int num,int &rt,int l,int r)
        //num-该数离散化后的值  rt-前一段前缀的根    l~r - 表示区间
        {
            tree[cnt]=tree[rt];
            cnt++;
            rt=cnt-1;
            tree[rt].sum++;
            if(l==r) return;
            int mid=(l+r)>>1;
            if (num<=mid)   amend(num,tree[rt].L,l,mid);
            else    amend(num,tree[rt].R,mid+1,r);
        }

        int query(int lr,int rr,int k,int l,int r)
        {
            int d=tree[tree[rr].L].sum-tree[tree[lr].L].sum;
            //在区间给定的范围内,左区间有d个数(从小到大)
            if (l==r)   return l;
            int mid=(l+r)>>1;
            if (k<=d)   return query(tree[lr].L,tree[rr].L,k,l,mid);
            //如果第k小在左区间,直接在左区间寻找第k个数即可
            else    return query(tree[lr].R,tree[rr].R,k-d,mid+1,r);
            //如果第k小在右区间,在右区间寻找第k-d个数即可
        }

        int main(void)
        {
            scanf("%d%d",&n,&m);
            for (int i=1;i<=n;i++)  scanf("%d",&val[i].v),val[i].id=i;
            sort(val+1,val+1+n,cmp);
            //进行离散化
            for (int i=1;i<=n;i++)
                rank[val[i].id]=i;//rank[i]表示原数组第i个数从小到大排的排名
            init();
            for (int i=1;i<=n;i++)
            {
                root[i]=root[i-1];//先把之前的树复制一遍,再进行logn次修改
                amend(rank[i],root[i],1,n);
            }
            int l,r,k;
            for (int i=1;i<=m;i++)
            {
                scanf("%d%d%d",&l,&r,&k);
                printf("%d\n",val[query(root[l-1],root[r],k,1,n)].v);
            }
           
            return 0;
        }
  • 当然,目前只能处理简单的静态区间的询问问题,动态区间需要主席树与其他数据结构的结合利用,将在以后再来探究。

 

 

人不能害怕失去就不去拥有,死只是一个结果,怎样活着才是最重要的。

2018.8.11记于JZ风雨飘摇的早晨

Y.W.

发表评论

电子邮件地址不会被公开。 必填项已用*标注