精华内容
下载资源
问答
  • 可持久化线段树

    2020-10-08 15:45:44
    可持久化线段树 可持久化线段树就是对[1,n]的每一个i,都建一颗线段树,然后为了省空间就复制了一部分的树 #include<bits/stdc++.h> using namespace std; const int N=2e5+5; struct zxs{ int l,r,sum,ed; }...

    可持久化线段树

    可持久化线段树就是对[1,n]的每一个i,都建一颗线段树,然后为了省空间就复制了一部分的树

    #include<bits/stdc++.h>
    using namespace std;
    
    const int N=2e5+5;
    struct zxs{
    	int l,r,sum,ed;
    }q[N*18*4];
    int n,m,a[N],b[N],c[N],cnt=0;
    int rt[N];
    int newnode(int id){
    	q[++cnt]=q[id];
    	return cnt;
    }
    int uppdate(int l,int r,int id,int x,int val){
    	int idd=newnode(id);
    	if(l==r){
    		q[idd].ed=x;
    		q[idd].sum++;
    		return idd;
    	}
    	int mid=(l+r)>>1;
    	if(val<=mid) q[idd].l=uppdate(l,mid,q[id].l,x,val);//
    	else q[idd].r=uppdate(mid+1,r,q[id].r,x,val);//
    	int ls=q[q[idd].l].sum,rs=q[q[idd].r].sum;
    	q[idd].sum=ls+rs;
    	return idd;
    }
    int query(int l,int r,int u,int v,int k){
    	if(l==r){
    		return q[v].ed;
    	}
    	int mid=(l+r)>>1;
    	int vv=q[v].l,uu=q[u].l;
    	int stmp=q[vv].sum-q[uu].sum;
    	if(k<=stmp) return query(l,mid,q[u].l,q[v].l,k);
    	else return query(mid+1,r,q[u].r,q[v].r,k-stmp);
    }
    int main(){
    	scanf("%d%d",&n,&m);
    	for(int i=1;i<=n;i++){
    		scanf("%d",&a[i]);
    	    b[i]=a[i];
    	}
    	sort(b+1,b+n+1);
    	int nn=unique(b+1,b+n+1)-b-1;
    	for(int i=1;i<=n;i++){
    		c[i]=upper_bound(b+1,b+nn+1,a[i])-b-1;
    	};
        for(int i=1;i<=n;i++)
        {
        	rt[i]=uppdate(1,nn,rt[i-1],i,c[i]);
        }
        for(int i=1;i<=m;i++){
        	int l,r,k;
        	scanf("%d%d%d",&l,&r,&k);
        	int tp=query(1,nn,rt[l-1],rt[r],k);
        	printf("%d\n",a[tp]);
        }
     }
    
    展开全文
  • 主席树,又称可持久化线段树,属于持久化数据结构。“主席”这一名词是由于发明者缩写为HJT,和某位主席拼音缩写相同(有些牵强),故将该数据结构称为主席树。 主席树既保留了线段树的灵活,也拥有了持久化数据...

    摘要

    主席树,又称可持久化线段树,属于可持久化数据结构。“主席”这一名词是由于发明者缩写为HJT,和某位主席拼音缩写相同(有些牵强),故将该数据结构称为主席树。
    主席树既保留了线段树的灵活,也拥有了可持久化数据结构的特点,在处理某些特定问题时有着其它数据结构不具有的优势。
    本文将首先介绍什么是“可持久化数据结构”,随后介绍主席树的思想,关于代码实现将结合例题讲解。

    可持久化数据结构

    可持久数据结构主要指的是我们可以查询历史版本的情况并支持插入,利用使用之前历史版本的数据结构来减少对空间的消耗(能够对历史进行修改的是函数式编程 [1])。

    我们经常会遇到这样的问题:我们需要维护一个数据结构,我们可以修改单一结点的值,查询单一结点的值,但是最关键的是我们可能还需要回退之前做过的某些操作。这里回退是指回到未做这些操作之前的状态。

    在无回退操作的情况下,我们有大把的数据结构可供选择来解决这些问题。但是一旦涉及到回退操作,选择就少的多了。我们将支持回退操作的数据结构称为可持久化数据结构。

    稍微思考一下如何可以在原来数据结构的基础上使其变得可持久化,有一个很简单的方案。我们每次操作都将重新建立一个新的数据结构,并将之前的操作都先在其上执行一次,之后执行该次操作。我们按操作执行顺序将这些数据结构维护成一个序列S,此时S[0]表示未经任何操作的初始数据结构。对于i>0,S[i]表示在S[0]的基础上执行过序号1到i的所有操作后得到的新的数据结构。在这样的做法下,我们称S[i]为版本i,回退操作等价于切换到某个特定版本。若操作i表示切换为版本j,那么我们可以直接将S[i]设置为S[j]的克隆。

    上面提到的做法下很容易发现可以使得任意数据结构都可以支持回退操作,但是缺点也是非常明显,空间和时间的复杂度都奇高。每一次操作都需要累加之前操作的时间复杂度,空间也是,我们为了保存各个版本需要耗费大量的内存。

    先说明时间复杂度的优化,对于i号操作,我们完全可以直接克隆版本S[i-1]并在其上执行i号操作,这样时间复杂度基本上就向空间复杂度看齐了。下面我们就可以专注于空间复杂度的优化(对应的也就是时间复杂度的优化)。

    数据结构是用于保存数据的,我们将其保存数据的单元称为结点,我们可以利用结点来刻画整个数据结构的骨架。数据结构基本分为两类,一类是稳定的,一类是不稳定的。稳定的数据结构,其特定是在修改的结点的值之后不会改变结点之间的关系,而不稳定的数据结构在结点值变更后需要重新维护结点之间的关联。稳定的数据结构有线段树,后缀数组,前缀树等等,不稳定的数据结构主要就是各种二叉平衡树。对于稳定的树状结构,若孩子没有保存指向父结点的指针,即由父亲负责记录所有的孩子,我们很容易发现,当我们对某个结点更改时(修改值,新增,删除等操作),我们只需要同时修改该结点的所有祖先结点即可,那我们是不是也可以只克隆这些结点而非整个数据结构呢?答案是肯定的。由于父亲维护孩子,因此一个孩子允许有多个父亲,故所有没有被直接影响的结点都可以继续复用。我们将部分树状数据结构(特定是稳定和父亲维护父子关系)的一次操作的空间复杂度优化到了O(h),其中h是树状数据结构的高度。

    当我们将上面的想法作用到线段树时,就得到了常说的主席树。其高度为 O ( l o g 2 ( n ) ) O(log_2(n)) O(log2(n)),其中n为线段树维护的区间大小,同时其时间和空间复杂度均为 O ( l o g 2 ( n ) 2 ) O(log_2(n)^2) O(log2(n)2)

    引用自:陶无语的博客

    静态主席树

    我们按照“是否支持修改”来将主席树划分为静态和动态。静态主席树一旦建树成功,就不再支持修改,只能够用于查询。静态主席树维护元素出现次数的前缀和。

    例题:洛谷P3834,查询区间第k大值
    给定n个元素,共m个询问,每次询问给出[l ,r]和k,回答区间[l , r]内第k大元素值是多少。

    建树

    考虑用主席树解决上述问题,给出如下建树步骤:

    1. 新建一棵完整的空树,其根节点编号存放在root[0]内。
    2. 依次将n个元素插入到“版本0”的空树中,他们的“版本号”(根节点)存放在root[i]中。

    对于每一个“新版本”,我们都在原来基础上新增“需要修改的节点”,并将其根节点记录在root数组中。
    如此我们的时空花费都与修改的路径成正比,即每次 O ( l o g 2 N ) O(log_2N) O(log2N)

    当然这些都是从理论思想上来讲的,比较抽象;具体到这一题,我们令线段树维护区间内元素数量,每个节点有三个变量,分别是 ls , rs , sum,即左儿子编号,右儿子编号,区间内元素个数。
    初始时sum都为0,随后将n个元素依次插入形成n棵新的线段树,而这n+1棵(包括编号为0的空树)构成了一棵静态主席树。
    所以建树操作其实分为两步:BuildTree()建立一棵空树并返回根节点编号;updata()在原树基础上“增加一棵新树”,并返回该版本的根节点编号。

    虽然不同历史版本的线段树节点之间有交叉以重复利用,但每个历史版本都有唯一且独立的根节点

    查询

    由于线段树维护的是区间内元素的数量,所以不同版本的线段树的对应节点是可以加减的,那么root[i] - root[j]意义就是“第 i 个版本的线段树比第 j 个版本的线段树多几个元素”。如果我们再加上区间范围限制[l , r],那么我们也可以查询“第 i 个版本比第 j 个版本,在[l , r]上多几个元素”。

    具体到本题,我们需要查询区间[l , r]内第k大的元素,已知线段树可以加减,那么对于询问(l , r , k),我们就需要在root[l-1] 与 root[r]两棵线段树上找寻答案,不要忘记了这颗线段树是根据权值建立的,也就是所谓的权值线段树。那么在res个数中找第k个,显然二分(树上),参见代码。

    代码模板

    见附录部分code-1:洛谷P3834静态主席树模板-求区间第k大值

    动态主席树

    静态主席树虽然支持历史查询,但其功能还是不太强大,因为其不支持更改。我们将支持修改的主席树称为动态主席树,但是这个功能添加起来并不容易。静态主席树还可以看作是线段树通过小修改得到,而动态主席树则是树套树。

    思想依旧是维护元素出现次数的前缀和,可以类比差分数组,我们都知道前缀和数组是不支持修改的,如果要修改,就需要用 树状数组/线段树 来维护,这里也是类似。

    我们考虑“外层用树状数组,内层用记录区间内数值出现次数的线段树”来实现支持修改的可持久化线段树,也即动态主席树。

    在静态主席树上,可以通过两个权值线段树相减来求得区间第k大值,在这里我们仍旧是通过这种方法求区间第k大,不同的是我们需要保证所有线段树的数据是正确的(维护修改)。
    如果我们用树状数组来维护不同版本的权值线段树的编号,那么对于“将位置 p 的 x 修改为 y”这一操作,我们需要修改共logN个版本的权值线段树,如此修改操作的时间复杂度是 O ( ( l o g 2 N ) 2 ) O((log_2N)^2) O((log2N)2)
    值得注意的是,此时空间复杂度 = 树状数组空间 * 权值线段树空间 = N 2 N^2 N2,但是树状数组实际上只保存权值线段树的“版本号”而已,因此实际上用到的空间也就只有权值线段树上的 O ( N ( l o g 2 N ) 2 ) O(N(log_2N)^2) O(N(log2N)2)个节点的空间,因此动态开点即可。

    例题2:洛谷P2617

    代码模板: 见附录部分code-2

    注释

    [1] 函数式编程:“函数式编程”是一种“编程范式”(programming paradigm),也就是如何编写程序的方法论。它属于“结构化编程”的一种,主要思想是把运算过程尽量写成一系列嵌套的函数调用。

    引用自:aezero的博客

    附录

    code-1:洛谷P3834静态主席树模板-求区间第k大值

    #include<cstdio>
    #include<algorithm>
    using namespace std;
    const int N = 2e5+10;
    int n,m,a[N];
    struct zxTree{
        int ls,rs,sum;//左右儿子,区间内元素个数
        #define ls(x) tr[x].ls
        #define rs(x) tr[x].rs
        #define sum(x) tr[x].sum
    } tr[N*40];//注意数组大小
    int sz = 0;//不同版本的树的总数 
    int root[N];//root[i]存放第i棵树的树根的编号
    int BuildTree(int l,int r){
        /*建树,和普通线段树相同*/
        int rt = ++sz;sum(rt) = 0;
        if(l == r) return rt;
        int mid = l+r>>1;
        ls(rt) = BuildTree(l,mid);
        rs(rt) = BuildTree(mid+1,r);
        return rt;
    }
    int updata(int pre,int l,int r,int x){
        /*新建一棵树,其比pre树多一个元素x*/
        int rt = ++sz;
        tr[rt] = tr[pre]; sum(rt)++;
        if(l == r) return rt;
        int mid = l+r>>1;
        if(x <= mid) ls(rt) = updata(ls(pre),l,mid,x);
        else rs(rt) = updata(rs(pre),mid+1,r,x);
        return rt;
    }
    int ask(int pre,int rt,int l,int r,int k){
        /*  依次是:上一个树根,当前树根,区间左右端点,所求区间第k大
            返回该区间第k大数的下标 */
        if(l >= r) return l;
        int res = sum(ls(rt)) - sum(ls(pre));
        int mid = l+r>>1;
        if(res >= k) return ask(ls(pre),ls(rt),l,mid,k);
        else return ask(rs(pre),rs(rt),mid+1,r,k-res);
    }
    int tmp[N];
    int main(){
        scanf("%d%d",&n,&m);
        for(int i = 1;i <= n;i++) scanf("%d",a+i),tmp[i] = a[i];
        //离散化
        sort(tmp+1,tmp+1+n);
        int tot = unique(tmp+1,tmp+1+n)-tmp-1;
        root[0] = BuildTree(1,tot);
        for(int i = 1;i <= n;i++){
            int x = lower_bound(tmp+1,tmp+1+tot,a[i])-tmp;
            root[i] = updata(root[i-1],1,tot,x);
        }
        //利用主席树可以加减原理计算
        for(int i = 1,l,r,k;i <= m;i++){
            scanf("%d%d%d",&l,&r,&k);
            int x = ask(root[l-1],root[r],1,tot,k);
            printf("%d\n",tmp[x]);
        }
        return 0;
    }
    

    code2-洛谷P2617动态主席树

    #include<cstdio>
    #include<algorithm>
    using namespace std;
    const int N = 1e5+10;
    /*线段树节点,要存放左右儿子编号,区间内元素个数*/
    struct SegmentTree{
        int ls,rs,sum;
        #define ls(x) tr[x].ls
        #define rs(x) tr[x].rs
        #define sum(x) tr[x].sum
    }tr[N*400];//空间要N(logN)^2大小
    /*因为要离散化,所以要提前读取所有操作*/
    struct Query{
        int l,r,k;//查询操作,询问区间[l,r]内第k大数的值
        int p,x;    //修改操作,修改位置p位置上的元素为x
    }qy[N];
    int sz = N;/*不同版本的线段树总数,
    即动态申请节点编号,初始值要为N,因为前n个节点被使用*/
    int a[N],n,m,tot = 0;//tot离散化用
    char op[10];
    void Insert(int rt,int l,int r,int p,int d){
        /*对以rt为根的线段树,区间[l,r]内新增一个元素x*/
        sum(rt) += d;
        if(l == r) return; int mid = l+r>>1;
        if(!ls(rt)) ls(rt) = ++sz;//如果该子树没有子节点则新建
        if(!rs(rt)) rs(rt) = ++sz;//动态申请节点
        if(p <= mid) Insert(ls(rt),l,mid,p,d);
        else Insert(rs(rt),mid+1,r,p,d);
    }
    void add(int l,int p,int y){
        /*向树状数组中的 线段树中 位置p值+d,要从l开始哦*/
        for(int x = l;x <= n;x += x&-x) Insert(x,1,tot,p,y); 
    }
    int t1[N],t2[N],c1,c2;//临时记录遍历路径
    int ask(int l,int r,int k){
        /*返回区间[l,r]内第k大元素的值(离散化后的)*/
        if(l == r) return l;
        int res = 0, mid = l+r>>1;
        for(int i = 1;i <= c1;i++) res -= sum(ls(t1[i]));
        for(int i = 1;i <= c2;i++) res += sum(ls(t2[i]));
        if(res >= k){
        	for(int i = 1;i <= c1;i++) t1[i] = ls(t1[i]);
        	for(int i = 1;i <= c2;i++) t2[i] = ls(t2[i]);
        	return ask(l,mid,k);
    	}else{
    		for(int i = 1;i <= c1;i++) t1[i] = rs(t1[i]);
        	for(int i = 1;i <= c2;i++) t2[i] = rs(t2[i]);
    		return ask(mid+1,r,k-res);
    	} 
    }
    int tmp[N*2];//离散化用
    int query(int l,int r,int k){
    	c1 = c2 = 0;
    	/*我们将树状数组上待查询的线段树的左儿子编号先存储*/
    	for(int i = l;i;i -= i&-i) t1[++c1] = i;
    	for(int i = r;i;i -= i&-i) t2[++c2] = i;
    	int x = ask(1,tot,k);	//注意查询区间是[1,tot] 
    	return tmp[x];
    }
    int main(){
        scanf("%d%d",&n,&m);
        for(int i = 1;i <= n;i++) scanf("%d",a+i),tmp[++tot] = a[i];
        for(int i = 1;i <= m;i++){
            scanf("%s",op);
            if(op[0] == 'C'){
                scanf("%d%d",&qy[i].p,&qy[i].x);
                tmp[++tot] = qy[i].x;//先存储,方便离散化
            }else scanf("%d%d%d",&qy[i].l,&qy[i].r,&qy[i].k);
        }
        //离散化
        sort(tmp+1,tmp+1+tot);
        tot = unique(tmp+1,tmp+1+tot)-tmp-1;
        for(int i = 1;i <= n;i++){
            int p = lower_bound(tmp+1,tmp+1+tot,a[i])-tmp;
            add(i,p,1);
        }
        for(int i = 1;i <= m;i++){
            if(qy[i].l){
                int l = qy[i].l, r = qy[i].r;
                printf("%d\n",query(l-1,r,qy[i].k));
            }else{
                int p = lower_bound(tmp+1,tmp+1+tot,qy[i].x)-tmp;
                int pre = lower_bound(tmp+1,tmp+1+tot,a[qy[i].p])-tmp;
                add(qy[i].p,pre,-1); add(qy[i].p,p,1); a[qy[i].p] = qy[i].x;
            }
        }
        return 0;
    }
    
    展开全文
  • 当我们遇到要求快速查询区间的问题时,通常用线段树、平衡树等数据结构维护这类问题.但是使用这些数据结构的前提是要求区间信息可以快速合并(例如O(1)O(1)O(1)或O(log⁡n)O(\log n)O(logn)合并),还有很多问题是不...

    一.问题引入.

    当我们遇到要求快速查询区间的问题时,通常用线段树、平衡树等数据结构维护这类问题.但是使用这些数据结构的前提是要求区间信息可以快速合并(例如 O ( 1 ) O(1) O(1) O ( log ⁡ n ) O(\log n) O(logn)合并),还有很多问题是不可以这样做的,例如区间第k小的问题.

    区间第k小问题可以使用很多数据结构来解决,例如划分树、归并树、分块、树套树等数据结构来解决,然而这些数据结构一次查询的时间复杂度大多劣于 O ( log ⁡ n ) O(\log n) O(logn).

    就当这些数据结构都对这类问题显得十分无力的时候,可持久化这种数据结构上的技巧横空出世,而主席树(可持久化线段树)就是其中的一种经典应用.


    二.权值线段树.

    在认识主席树之前,我们先来看一种特殊的线段树——权值线段树,这种线段树的维护的是序列的数值范围内每一个值的出现情况.

    我们不考虑时空复杂度,尝试利用权值线段树来维护区间第 k k k小问题.

    首先建立 n n n棵结构相同线段树,每棵线段树维护区间 [ 1 , n ] [1,n] [1,n]中出现的权值信息.那么当我们要查询区间 [ l , r ] [l,r] [l,r]的第 k k k小数时,就可以同时从维护 [ 1 , l − 1 ] [1,l-1] [1,l1] [ 1 , r ] [1,r] [1,r]的线段树的根节点出发往下走.设 t r [ m ] [ i ] tr[m][i] tr[m][i]表示维护 [ 1 , m ] [1,m] [1,m]的线段树的第 i i i个节点,那么若 t r [ r ] [ i ] tr[r][i] tr[r][i]的左儿子所包含的权值数量减去 t r [ l − 1 ] [ i ] tr[l-1][i] tr[l1][i]左儿子所包含的权值数量小于 k k k则往右儿子走(注意让 k k k减掉权值数量),否则往左儿子走.

    这个时候我们会发现查询一次的时间复杂度为 O ( log ⁡ n ) O(\log n) O(logn),但是空间复杂度和建树的时间复杂度均为 O ( n 2 ) O(n^2) O(n2)(离散化后),于是我们的算法就要考虑如何优化这一复杂度.


    三.可持久化的引入.

    我们设原来的权值序列为 2 , 1 , 3 , 4 2,1,3,4 2,1,3,4,那么原来的 4 4 4棵线段树大概是这样的:
    在这里插入图片描述
    其中橙色的节点表示与上一棵线段树之间的差异.

    我们考虑相邻的两棵线段树之间的关系,发现两棵线段树之间的差异只有树上的一条长度为 O ( log ⁡ n ) O(\log n) O(logn)的链!

    这是否可以启发我们可以每次只存储发生改变的节点,其它节点直接调用上一棵的?

    考虑这样子存储原来的 n n n棵线段树:
    在这里插入图片描述
    图有点丑不要介意QAQ.

    我们发现这正好对应了我们上面的只存修改节点的思想,看起来这个想法非常可行,显然时空复杂度均为 O ( n log ⁡ n ) O(n\log n) O(nlogn).

    事实上,这是一种被称作“可持久化”的技巧,这种技巧被广泛应用于数据结构的维护上,我们上面维护的线段树就是可持久化线段树,也被称为主席树.

    类比可持久化线段树,我们还可以维护可持久化Trie、可持久化并查集、可持久化平衡树等数据结构,除了可持久化树状数据结构外,也有可持久化栈、可持久化块状链表等数据结构.


    四.可持久化线段树的实现.

    说了那么多,我们该如何实现一棵可持久化线段树呢?

    首先我们可以仿照动态开点线段树,初始第一棵树直接利用 0 0 0节点的自我迭代来实现,也就是说我们不需要建树.

    之后考虑如何往后增加一棵树 k k k.其实很简单,只需要顺着第 k − 1 k-1 k1棵树往下,新建一条链即可,代码如下:

    void Add_tree(int x,int l,int r,int hk,int &k){
      tr[k=++cn]=tr[hk];
      if (l==r) {++tr[k].sum;return;}
      int mid=l+r>>1;
      if (x<=mid) Add_tree(x,l,mid,tr[hk].s[0],tr[k].s[0]);
      else Add_tree(x,mid+1,r,tr[hk].s[1],tr[k].s[1]);
      Pushup(k);
    }
    //主程序中
    Add_tree(a[i],1,n,rot[i-1],rot[i]);
    

    查询 [ l , r ] [l,r] [l,r]就从第 l − 1 l-1 l1和第 r r r往下走就好了,代码如下:

    int Query(int k,int l,int r,int L,int R){
      if (l==r) return l;
      int sum=tr[tr[R].s[0]].sum-tr[tr[L].s[0]].sum,mid=l+r>>1;
      if (sum>=k) return Query(k,l,mid,tr[L].s[0],tr[R].s[0]);
      else return Query(k-sum,mid+1,r,tr[L].s[1],tr[R].s[1]);
    }
    



    五.例题与代码.

    题目:luogu3834.

    注意,这题由于数的范围太大权值线段树开不下,需要离散化.

    代码如下:

    #include<bits/stdc++.h>
      using namespace std;
     
    #define Abigail inline void
    typedef long long LL;
    
    const int N=200000,C=30; 
    
    int n,m,a[N+9],ord[N+9];
    
    int Lower(int *a,int n,int x){
      int l=1,r=n,mid=l+r>>1;
      for (;l<r;mid=l+r>>1)
        x>a[mid]?l=mid+1:r=mid;
      return l;
    }
    
    struct tree{
      int s[2],sum;
    }tr[N*C+9];
    int cn,rot[N+9];
    
    void Pushup(int k){tr[k].sum=tr[tr[k].s[0]].sum+tr[tr[k].s[1]].sum;}
    
    void Add_tree(int x,int l,int r,int hk,int &k){
      tr[k=++cn]=tr[hk];
      if (l==r) {++tr[k].sum;return;}
      int mid=l+r>>1;
      if (x<=mid) Add_tree(x,l,mid,tr[hk].s[0],tr[k].s[0]);
      else Add_tree(x,mid+1,r,tr[hk].s[1],tr[k].s[1]);
      Pushup(k);
    }
    
    int Query(int k,int l,int r,int L,int R){
      if (l==r) return l;
      int sum=tr[tr[R].s[0]].sum-tr[tr[L].s[0]].sum,mid=l+r>>1;
      if (sum>=k) return Query(k,l,mid,tr[L].s[0],tr[R].s[0]);
      else return Query(k-sum,mid+1,r,tr[L].s[1],tr[R].s[1]);
    }
    
    Abigail into(){
      scanf("%d%d",&n,&m);
      for (int i=1;i<=n;++i){ 
        scanf("%d",&a[i]);
        ord[i]=a[i];
      }
    }
    
    Abigail work(){
      sort(ord+1,ord+1+n);
      for (int i=1;i<=n;++i)
        a[i]=Lower(ord,n,a[i]);
      for (int i=1;i<=n;++i)
        Add_tree(a[i],1,n,rot[i-1],rot[i]);
    }
    
    Abigail getans(){
      int l,r,k;
      while (m--){
      	scanf("%d%d%d",&l,&r,&k);
      	printf("%d\n",ord[Query(k,1,n,rot[l-1],rot[r])]);
      }
    }
    
    int main(){
      into();
      work();
      getans();
      return 0;
    }
    
    展开全文
  • 可持久化线段树 主席树 详解 一、可持久化线段树 简介 可持久化线段树,顾名思义,即对线段树进行持久化处理之后的线段树。 在持久化数据结构的理论中,我们对持久化的概念有所了解:“可以返回之前的某个状态...
    😊 | Powered By HeartFireY | Persistent Segment Tree
    📕 | 需要的前导知识:线段树(Segment Tree)、权值线段树、可持久化数据结构理论(Persistent Data Structure Theory)

    一、可持久化线段树 简介

    可持久化线段树,顾名思义,即对线段树进行可持久化处理之后的线段树。

    在可持久化数据结构的理论中,我们对可持久化的概念有所了解:“可以返回之前的某个状态,并在该基础上进行修改”。可持久化线段树就是这样一种结构。

    我们从一般思路出发进行分析:想要让线段树可持久化,最朴素的方法就是每进行一次操作都新建一颗线段树。但显然这是不明智的做法:时间和空间上而言都是非常差的的算法。我们不妨继续分析一下更新之后与更新之前的结构:每次更新都只有少量的点被修改。因此大量的点可以继续使用,无需重新建树。

    本文分两个部分对可持久化线段树进行探讨。

    值得注意的是:我们一般认为主席树就是可持久化线段树,实际上两者之间有区分:

    可持久化线段树单纯指经过可持久化处理之后,能够查询、修改历史节点数据的结构,建立在基础线段树的基础之上;而主席树建立在权值线段树的基础之上,能够查询修改历史节点。二者本质区别在于纪念性可持久化的对象所维护的对象不同(一个维护权值、一个维护值域)。

    因此,可持久化线段树 ≠ \neq =主席树,准确的说,主席树 ⊂ \subset 可持久化线段树。

    二、可持久化线段树 基本结构与操作

    1.基本结构、建树操作

    首先应该明确一点:由于可持久化结构重叠的特殊性,可持久化线段树不能采用堆式储存,因此只能采取动态开点的方式进行储存。

    不同于后续节点的更新,对于最初的状态下的线段树我们采用一次建树完成:

    1. 采用递归建树,递归函数参数保存左右边界(初始化为 ( 1 , n ) (1, n) (1,n))、当前元素的指针。同时保存总计数 c n t cnt cnt

    2. 递归边界控制为 l = = r l == r l==r,由于此时左边界 l l l即为指向 a a a数组的指针,因此叶子节点赋值 v a l ( p ) = a [ l ] val(p) = a[l] val(p)=a[l]

    3. 非叶子节点首先记录左右子节点的下标 l s ( p ) = c n t + + , r s ( p ) = c n t + + ls(p) = cnt++, rs(p) = cnt++ ls(p)=cnt++,rs(p)=cnt++,然后递归建左右子树:

      b u i l d ( l ,   m i d ,   l s ( p ) ) 、 b u i l d ( m i d + 1 ,   r ,   r s ( p ) ) build(l,\ mid,\ ls(p))、build(mid + 1, \ r,\ rs(p)) build(l, mid, ls(p))build(mid+1, r, rs(p))

    4. 建立左右节点后非叶子节点 = 左右子节点的和: v a l ( p ) = v a l ( l s ( p ) ) + v a l ( r s ( p ) ) val(p) = val(ls(p)) + val(rs(p)) val(p)=val(ls(p))+val(rs(p))

    根据以上建树过程,我们以数组 a = 1 , 2 , 3 , 4 , 5 a = {1,2,3,4,5} a=1,2,3,4,5为例建立线段树:

    在这里插入图片描述

    可以看到:不同于基础线段树,可持久化线段树的下标不再遵循堆的规律,这种建树方式我们称为动态开点

    结构体封装版:

    #define ls(x) tree[x].ls
    #define rs(s) tree[x].rs
    #define val(x) tree[x].val
    #define mark(x) tree[x].mark
    struct node{
        int val, mark = INT_MIN;
        int ls, rs;
    }tree[MAXN];
    
    void build(int l = 1, int r = n, int p = 1){
        if(l == r) val(p) = a[l];
        else{
            ls(p) = ++cnt, rs(p) = ++cnt;
            int mid = (l + r) >> 1;
            build(l, mid, ls(p));
            build(mid + 1, r, rs(p));
            val(p) = val(ls(p)) + val(rs(p));
        }
    }
    

    建树完毕后,上述线段树已经静态化,后续的修改操作通过增加新节点来实现。

    2.单点修改

    假设现在要对 A [ 4 ] A[4] A[4] − 2 -2 2,则操作步骤如下:

    首先建立新根结点,更新根节点记录数组: r o o t [ f l a g ] = + + c n t root[flag] = ++cnt root[flag]=++cnt

    在这里插入图片描述

    创建新节点后对其进行处理。由于我们要修改的元素 A [ 4 ] A[4] A[4]位于右子树,因此左子树部分保持不变,可以继续使用。因此将原左子树与新节点相连,同时新建右子节点。

    在这里插入图片描述

    继续处理, A [ 4 ] A[4] A[4]位于当前结点左子树,右子树保持不变继续使用,因此新建左子节点,将原右子节点与新节点相连。

    继续访问左子节点发现到达叶子结点,对原数据进行处理后再逐层回溯,更新路径上的结点值。

    在这里插入图片描述

    单点修改的操作到此结束。可以看到,对于最初版本的线段树,其任何数据未被改变。

    void update(int x, int d, int p, int q, int cl = 1, int cr = n){
        if (cl == cr) val(q) = val(p) + d; // 给叶子节点赋值
        else{
            ls(q) = ls(p), rs(q) = rs(p); // 复制节点
            int mid = (cl + cr) / 2;
            if (x <= mid) ls(q) = ++cnt, update(x, d, ls(p), ls(q), cl, mid); 
            // 创建新节点作为左儿子,然后往左递归
            else rs(q) = ++cnt, update(x, d, rs(p), rs(q), mid + 1, cr); 
            // 创建新节点作为右儿子,然后往右递归
            val(q) = val(ls(q)) + val(rs(q)); // 根据子节点给当前节点赋值
        }
    }
    

    3.区间查询

    区间查询与基础线段树几乎一致,只需要额外关注查询的版本对应的根节点即可。

    int query(int l, int r, int p, int cl = 1, int cr = n){
        if (cl > r || cr < l) return 0;
        else if (cl >= l && cr <= r) return val(p);
        else{
            int mid = (cl + cr) / 2;
            return query(l, r, ls(p), cl, mid) + query(l, r, rs(p), mid + 1, cr);
        }
    }
    

    4.区间修改

    我们需要再次回到 L a z y Lazy Lazy标记上进行讨论:

    对于 L a z y Lazy Lazy标记,我们其实有两种实现方案:

    1. 标记上下传,也就是我们最常用的 p u u s h _ u p 、 p u s h _ d o w n puush\_up、push\_down puush_uppush_down操作;
    2. 标记永久化:标记时不用 p u u s h _ u p 、 p u s h _ d o w n puush\_up、push\_down puush_uppush_down,而是在查询的时候干预数据。

    二者的一大区别在于,标记上下传会引发修改结点路径上的点的更新,而标记永久化不会影响树上的点。

    这点区别是非常有意义的:考虑一棵可持久化线段树,如果从某节点上传,则到根节点路径上的点都会被修改,而可持久化结构导致了某些结点的复用,这会引发多个版本的线段树更新,无法指定是哪一版本;同理,下传标记也会引发不必要的点的更新。因此,我们只能通过标记永久化对可持久化线段树进行修改。

    于是,我们在查询时需要额外带上一个标记: m k mk mk

    我们不妨再回顾一下查询的过程:

    在这里插入图片描述

    我们曾在线段树的查询过程中了解到:查询的过程就是不断地查询区间的交集,以此不断地缩小查找范围。

    如上图所示,假设查询到①所示的区间则返回该节点的值,因为他是待查询区间的子集;②所示的区间则需要向右递归搜索、③向左递归搜索。

    不同于基础线段树,可持久化线段树需要进行额外加永久化标记的操作,即:查询到待查区间的子集时,返回(该节点值 + + +子集元素个数 × \times ×永久化标记)

    同时,递归查询时也要额外对标记进行累加。这点也十分容易理解:

    我们思考永久标记的意义:对于当前节点所管辖的区间元素全部加某个值(或者做出某种改变),因此向下查询子集时应该带上当前节点的标记,相当于将标记进行了下放

    ll query(int l, int r, int p, int cl = 1, int cr = n, ll mk = 0){
        if (cl > r || cr < l) return 0;
        else if (cl >= l && cr <= r) return val(p) + mk * (cr - cl + 1); // 加上带的标记
        else{
            int mid = (cl + cr) >> 1;
            return query(l, r, ls(p), cl, mid, mk + mark(p)) + query(l, r, rs(p), mid + 1, cr, mk + mark(p)); // 带着标记传递
        }
    }
    

    对于 u p d a t e update update操作,其基本过程如下:

    1. 首先对当前节点进行复制;
    2. 判断:如果当前节点管辖区间合法,且是待修改区间的子集,那么对当前新的节点(复制后的节点)的标记执行加操作;
    3. 如果不满足 2 2 2条件,则判断待修改区间是否由左子树管辖、是否由右子树管辖,如果是则复制节点,递归向左\右建点更新。

    值得注意的是,由于缺少传递标记,因此由子节点给当前节点赋值可能会发生错误。

    为了得到全包含的区间并计算真实长度,我们只需要定义区间为 [ m a x ( l , c l ) , m i n ( r , c r ) ] [max(l, cl), min(r, cr)] [max(l,cl),min(r,cr)]即可(保证其为带查询区间的子集)。

    void update(int l, int r, int d, int p, int q, int cl = 1, int cr = n){
        ls(q) = ls(p), rs(q) = rs(p), mark(q) = mark(p); // 复制节点
        if (cl >= l && cr <= r && cr > cl) mark(q) += d;
        else{
            int mid = (cl + cr) >> 1;
            if (cl <= r && mid >= l) ls(q) = ++cnt, update(l, r, d, ls(p), ls(q), cl, mid);// 提前进行判断,以免新建不必要的节点
            if (mid + 1 <= r && cr >= l) rs(q) = ++cnt, update(l, r, d, rs(p), rs(q), mid + 1, cr);
                
        }
        val(q) = val(p) + (min(cr, r) - max(cl, l) + 1) * d; // 根据需要更新的区间长度计算当前节点的值
    }
    

    三、主席树

    区别于一般的可持久化线段树,主席树是可持久化权值线段树。

    下面简单介绍一下主席树的构造过程:

    1.建立空树

    void build(int l = 1, int r = n, int p = 1){
        val(p) = 0;
        if (l != r){
            ls(p) = ++cnt, rs(p) = ++cnt;
            int mid = (l + r) / 2;
            build(l, mid, ls(p));
            build(mid + 1, r, rs(p));
        }
    }
    

    2.区间离散化

    int C[MAXN], L[MAXN], ori[MAXN];
    void discretize(int A[], int n){
        memcpy(C, A, sizeof(int) * n);     // 复制
        sort(C, C + n);                    // 排序
        int l = unique(C, C + n) - C;      // 去重
        for (int i = 0; i < n; ++i){
            L[i] = lower_bound(C, C + l, A[i]) - C + 1; // 查找
            ori[L[i]] = A[i]; // 保存离散化后的数对应的原数
        }
    

    3.插入离散化数据

    for (int i = 0; i < n; i++){
        roots[i + 1] = ++cnt;
        update(L[i], 1, roots[i], roots[i + 1]);
    }
    

    4.查询区间第 K K K大/小

    我们已经有了求[1, r]内第k大数的方法(查询相应历史版本即可),而求[l, r]内第k小数,只需对kth函数稍作修改。注意,我们在求kth时会用到当前左儿子对应的区间和,现在要排除[1, l-1],那么把这部分和减去即可。

    这一部分的思想与权值树状数组很相似。

    int kth(int k, int p, int q, int cl = 1, int cr = n){
        if (cl == cr) return ori[cl];
        int mid = (cl + cr) / 2;
        if (val(ls(q)) - val(ls(p)) >= k) return kth(k, ls(p), ls(q), cl, mid); // 往左搜
        else return kth(k - (val(ls(q)) - val(ls(p))), rs(p), rs(q), mid + 1, cr); // 往右搜
    }
    

    时间复杂度 O ( log ⁡ n ) O(\log n) O(logn)

    本文部分内容参考自算法学习笔记(50): 可持久化线段树 - 知乎 (zhihu.com)

    展开全文
  • 题目链接https://www.luogu.com.cn/problem/P3919 代码 #include<iostream> #include<string> #include<map> //#include<unordered_map> #include<queue> ...algori
  • 前言 不得不说,持久化数据结构...主席树实质上就是一棵可持久化线段树,它的具体实现可以看下面。 让我们从值域线段树开始说起 要学主席树,我们就要先学值域线段树。 值域线段树的区间存的并不...
  • 可持久化线段树总结

    2021-06-11 12:40:14
    普通的可持久化线段树的用法就是利用动态开点,在一次修改中只新建有修改的结点,从而实现可以调用某次修改前的线段树。例如在单点修改中,每次更改的最多只有线段树的一条链,则修改需要的时间复杂度与空间复杂度均...
  • 思路:关键点是lazy标记不下传,区间修改直接新开一棵线段树。 详情参见: https://blog.csdn.net/kirito16/article/details/47266801 #include #define maxn 100005 using namespace std; typedef long ...
  • Bzoj 2653 题目描述: 一个长度为n的序列a,设其排过序之后为b,其中位数定义为b[n/2],其中a,b从0开始标号,除法取下整。给你一个 长度为n的序列s。回答Q个这样的询问:s的左端点在[a,b]之间,右端点在[c,d]...
  • 这道题可以用主席树,也就是可持久化线段树来解决,所以大概还是要学一下什么叫做可持久化线段树可持久化线段树基于普通的线段树延伸而成,普通的线段树往往能解决在更新后某段区间内的查询问题,但是不能知道...
  • 主席树,也就是可持久化线段树,实际上就是查询区间 k 大的数据结构,并没有名字所说的那么牛逼,只是应用了持久化思路的线段树而已。 那么什么是持久化思路呢? 我们先看这个问题:查询区间 k 大。你肯定...
  • 洛谷 P3834 【模板】可持久化线段树 2(主席树) 题目链接 题目背景 这是个非常经典的主席树入门题——静态区间第 k 小。 数据已经过加强,请使用主席树。同时请注意常数优化。 题目描述 如题,给定 n 个整数构成的...
  • 有关线段树的经典问题(势能线段树、李超线段树线段树维护单调子序列)的总结请看神仙 xyz32768xyz32768xyz32768 的这篇文章:[学习笔记]线段树骚操作选讲 1. 线段树的合并与分裂 1.1 BZOJ2212 我们考虑一道经典...
  • 之后每次询问就从提问的那个root去进行线段树上的查找即可 代码 #include<bits/stdc++.h> using namespace std; const int maxn=4e7+5; const int maxm=1e6+5; int n,m,cnt,root[maxn],a[maxm]; struct ...
  • 于是该题变成了可持久化线段树,时间复杂度O(n*log(n))。 CODE: #include #include #include #include #include #include #include #include using namespace std; const int maxn=100100; const int ...
  • 主席树太费空间了,而本题也无需维护任何区间信息,只是查询历史版本点值,没必要构造可持久化线段树,我们可以构建结构类似于 BST 的持久化数据结构,这样每个非叶节点也会带有权值,不会被浪费掉 Code; #include...
  • 因为这道题是多次询问,需要我们记录,我们利用可持久化线段树的储存信息,上面那一道题的中途记录的 ans 就类似于前缀和,我们就可以利用可持久化线段树来维护区间和,我们就不断去寻找前缀和判断是否可以继续构成...
  • 题目链接:https://www.luogu.org/problemnew/show/P3919 思路:直接按题意写就行。更新直接更新值就行。 #include<bits/stdc++.h> using namespace std; ...#define LL long Long ...int L[max...
  • 使用一个next[],记录改颜色下一次出现的位置,并用可持久化线段树进行维护,查询时该区间内next[i]>r的个数即使颜色种数 注意next需要设置最右端点,即n+1 #include <bits/stdc++.h> #define inf 0x7...
  • 一种持久化数据结构,本质上是可持久化线段树,若加上前缀和思想便为主席树。 其思想为:单点修改时,只有被修改的点到根的一条链上的点会发生改变,建一个新根,添一条新链,并与不改变的点相连。以此为基础,...
  • 学习这篇博客之前需要先了解可持久化线段树是什么,在这附上一篇我之前写的关于可持久化线段树的博客,感兴趣的小伙伴可以看一下。 (67条消息) 可持久化线段树_AC__dream的博客-CSDN博客 在普通线段树上进行区间...
  • 可持久化线段树学习笔记变量释义核心流程典型例题 变量释义 这里以求区间第k大的例子来解释可持久化线段树 #define N 200005 int a[N]; //原数列,这里假设a的范围同N int b[N]; //去重后的数列 int root[N]; //每一...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,763
精华内容 2,705
关键字:

可持久化线段树