可持久化线段树

xyzqwq · 2024-06-19 20:50:27 · 个人记录

可持久化线段树 ，顾名思义，就是可以保留每一个历史版本，并且支持在历史版本上进行操作的线段树。

为什么要可持久化呢?有的时候离线维护扫描线之类的东西时，就需要在时间轴里穿梭，这就需要历史版本；权值线段树如果能可持久化，就可以维护区间的数据，达到静态树套树的效果。

那么如何可持久化呢？

首先，最暴力的做法就是，开n个线段树，但是这样肯定会爆空间，所以，我们得想点别的招。

如图，这是一个普通的线段树。 我们把第7个数加上3，如图。

仔细观察，就会发现，被修改的节点实际上只是一条链，长度为\log n。

于是，著名神犇hjt突发奇想，如果每次修改只维护一条链的话，空间复杂度就变成O(n+m\log n)了呀。

于是就有了可持久化线段树，也叫主席树（能猜到原因吧）

如图，在可持久化线段树里给第7个数加上3。

从这个图中，我们可以看出可持久化线段树的诀窍在于——复用历史版本的节点。

可持久化线段树只会增加需要修改的节点，而不需要修改的节点就可以使用以前的结构，这种思想被称为“函数式编程“，所以可持久化线段树也叫”函数式线段树“。

核心代码

void build(int &x,int l,int r){
    //建树操作，即第0个版本，所有版本复用的基础
    x=++tot;//可持久化线段树使用动态开点的方式，因此需要有lsrs数组存储左右儿子节点
    if(l==r){
        tr[x]=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(ls[x],l,mid),build(rs[x],mid+1,r);
    //因为x是引用形式，所以会直接给lsrs数组赋值
}
void change(int u,int &x,int l,int r,int k,int p){
    x=++tot;
    tr[x]=tr[u],ls[x]=ls[u],rs[x]=rs[u];
    //复制原节点
    if(l==r){
        tr[x]=p;
        return;
    }
    int mid=(l+r)/2;
    if(k<=mid) change(ls[u],ls[x],l,mid,k,p);//修改左儿子，右儿子直接复用原节点的右儿子
    else change(rs[u],rs[x],mid+1,r,k,p);//同理
}

例题1：可持久化数组

洛谷P3919

维护这样的一个长度为 N 的数组，支持如下几种操作：

1. 在某个历史版本上修改某一个位置上的值
2. 访问某个历史版本上的某一位置的值

此外，每进行一次操作（对于操作2，即为生成一个完全一样的版本，不作任何改动），就会生成一个新的版本。版本编号即为当前操作的编号（从1开始编号，版本0表示初始状态数组）

题目分析

很明显，这一个可持久化线段树模板题，需要单点修改，单点查询，套用模板即可。

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10,M=5e7+10;//可持久化线段树大概需要O(4n+mlogn)的空间，一般直接开N<<5
int tr[M],root[N],ls[M],rs[M],tot=0,a[N];
void build(int &x,int l,int r){
    x=++tot;
    if(l==r){
        tr[x]=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(ls[x],l,mid),build(rs[x],mid+1,r);
}
void change(int u,int &x,int l,int r,int k,int p){
    x=++tot;//动态开点
    tr[x]=tr[u],ls[x]=ls[u],rs[x]=rs[u];//复制节点
    if(l==r){
        tr[x]=p;
        return;
    }
    int mid=(l+r)/2;
    if(k<=mid) change(ls[u],ls[x],l,mid,k,p);
    else change(rs[u],rs[x],mid+1,r,k,p);
}
int query(int x,int l,int r,int k){
    if(l==r) return tr[x];
    int mid=(l+r)/2;
    if(k<=mid) return query(ls[x],l,mid,k);
    return query(rs[x],mid+1,r,k);
}
int n,m;
int main(){
    scanf("%d%d",&n,&m);//本题稍微有点卡常，需要用printf和scanf
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    build(root[0],1,n);
    for(int i=1;i<=m;i++){
        int v,opt,k,p;
        scanf("%d%d",&v,&opt);
        if(opt==1){
            scanf("%d%d",&k,&p);
            change(root[v],root[i],1,n,k,p);
        }
        else{
            scanf("%d",&k);
            printf("%d\n",query(root[v],1,n,k));
            root[i]=root[v];
        }
    }
}

例题2：静态区间第k小

洛谷P3834

给定n 个整数构成的序列 a，将对于指定的闭区间 [l,r] 查询其区间内的第 k 小值。

题目分析

如果没有区间操作，查询第k小可以用权值线段树实现，如果有要支持区间操作呢？

我们建一颗可持久化权值线段树，如图，把\{2,4,1,3\}这个数列的数依次插入。

仔细观察，就会发现第i棵树保存着前i个数的信息（设初始化的树为第0棵）

也就是说，这个可持久化线段树可以说是数列的“前缀树”。

你能想到什么？

可持久化线段树满足区间可加减性，所以我们可以用前缀和的方式找出维护[l,r]个数的信息的树。

也就是拿出第l-1棵树和第r棵树，两者相减，结果就是[l,r]的信息。

而在相减后的树上找第k小相信大家都已经会了。

那么就可以写出代码了！

注：这题数据很水，题面给|a_i |\le 10^9，但实际上的数据范围是0 \le a_i \le 10^6，甚至不需要离散化的优化，就可以过。

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int tr[N<<5],ls[N<<5],rs[N<<5],root[N],tot=0;
void build(int &x,int l,int r){
    //建树
    x=++tot;
    if(l==r) return;
    int mid=(l+r)/2;
    build(ls[x],l,mid),build(rs[x],mid+1,r);
}
void insert(int u,int &x,int l,int r,int k){
    x=++tot;//动态开点
    tr[x]=tr[u]+1,ls[x]=ls[u],rs[x]=rs[u];//复制该节点的所有信息（可以直接在节点上+1，否则还得pushuo一遍）
    if(l==r)  return; 
    int mid=(l+r)/2;
    if(k<=mid) insert(ls[u],ls[x],l,mid,k);
    else insert(rs[u],rs[x],mid+1,r,k);
}
int query(int u,int v,int l,int r,int k){
    int mid=(l+r)/2,lx=tr[ls[v]]-tr[ls[u]];//两颗树信息相减得到的左儿子信息
    if(l==r) return l;//如果只有一个数，第几大都是这个数了，直接返回
    if(k<=lx) return query(ls[u],ls[v],l,mid,k);
    return query(rs[u],rs[v],mid+1,r,k-lx);//二分查找第k小
}
int n,m;
int main(){
    cin>>n>>m;
    build(root[0],0,1e6);//建树
    for(int i=1;i<=n;i++){
        int t;
        cin>>t;
        insert(root[i-1],root[i],0,1e6,t);
    }
    while(m--){
        int l,r,k;
        cin>>l>>r>>k;
        cout<<query(root[l-1],root[r],0,1e6,k)<<endl;
    }
}

实际上，这份代码在除了洛谷以外的其它OJ上是AC不了的，因为题面上|a_i|\le 10^9的数据范围使代码必须要有离散化的优化，这里给出优化代码。

//其他部分和前面无异，这以后是离散化代码
int n,m,tt=0;
map<int,int>mp;//使用map离散化，使用sort离散化也可以
int val[N],a[N];
int main(){
    cin>>n>>m;
    build(root[0],1,n);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        mp[a[i]]=0;
    }
    for(auto it:mp){
    //map会自己排序，在遍历的过程中标上映射后的序号
        mp[it.first]=++tt;
        val[tt]=it.first;
    }
    for(int i=1;i<=n;i++) insert(root[i-1],root[i],1,n,mp[a[i]]);
    while(m--){
        int l,r,k;
        cin>>l>>r>>k;
        cout<<val[query(root[l-1],root[r],1,n,k)]<<endl;
    }
}

套路1：二维数点

接下来我们介绍关于可持久化线段树的一种重要套路——“二维数点”。

这类套路的关键在于，把题目转化为一个类似于求满足某种如 l\le i\le r,a[i]\le k 的条件的 i 的个数。

如果以 i 和 a[i] 为两条坐标轴的话，上述转化实际上是要求如图

中蓝色部分点的个数，顾名思义“二维数点”。

得到了这样的转化，就很容易用可持久化线段树做出这类题了。因为在一般的权值线段树上，查询权值小于某数的数的个数是容易的，只需在线段树上二分即可。而那个 l\le i\le r 的限制只需把树变成可持久化线段树即可。

接下来通过几个例题来熟悉这种套路。

[SDOI2009] HH的项链

[SDOI2009] HH的项链

题意

给定数字 a_i，每次给出 l,r，查询 [l,r] 区间内不同 a_i 的个数。

题目分析

这个问题的难点在于问题的局部性，如果求全局不同数字的个数，很容易用权值线段树解决。现在问题加入了区间的限制，我们就需要考虑转化。

一个很容易想到的做法是，建一颗可持久化权值线段树，在节点上维护某一段权值上某个数的个数。然而问题在于，如果对于某个 a_i 出现了多次，加到节点上就会算重复。

所以解决问题的关键在于，如何能把每个出现的节点只记录一次。

我们设 nxt[i] 是 i 后下一个与 a_i 相同的数。这样，只需要计算 [l,r] 区间内，满足 nxt[i]>r 的 i 的数量（这说明下一个与 a_i 相同权值的数不在 [l,r] 中，也就是说，i 是最后一个 a_i 出现的位置。这就转化为了，只对 i 出现计一次数）

细观限制条件

这就是刚刚我们提到的二维数点问题，于是将 nxt[i] 作为值存入主席树中，对于 l,r 的限制直接转化为 root[r] 和 root[l-1] 两颗树的联查，在查询的过程中二分出大于 r 的数的个数即可。

Army Creation

CF813E

题意

对于一个数列 a[i]，每次给出 l,r，查询每次问 [l,r] 内最多可以选多少个数，满足同一个数的出现次数不超过 k。

题目分析

问题即是求所有在 [l,r] 中出现次数不超过 k 的个数。仿照上一题的做法，要想对于每个数，只计数一次，我们可以对于每个 i 向前找 k 个与之相同权值的数。如果这个数的位置不在 [l,r] 中（即这个数的位置 <l），就说明这个数在 [l,r] 中出现次数不超过 k，且由于我们进行了如此转化，就使得对于每个满足的条件的数，只会累加答案一次。

设 pre[i] 为 i 前第 k 个与 a[i] 权值相同的数，细观限制条件

又是一个二维数点问题，例行公事即可。

值得注意的是 pre[i] 的求法，考虑对于每个权值开一个队列，而后当队列长度为 k 时记下 pre[i] 即可。给出代码：

for(int i=1;i<=n;i++){
    if(q[a[i]].size()==k) pre[i]=q[a[i]].front(),q[a[i]].pop();
    else pre[i]=0;
    q[a[i]].push(i);
    insert(root[i],root[i-1],0,n,pre[i]);
}

如果读者有耐心思考前两题的解决过程，可能会发现，二者将问题转化为二维数点的过程中，不约而同地将其转化为 “位置”。以位置为一个偏序关系加入数点。

请记住，对于主席树问题，要么存入位置对权值做手段（即可持久化权值线段树），要么存入权值对位置做操作（即可持久化位置线段树），读者应该辨别二者的关系（尤其在离散化后，二者近乎是对偶的，弄混的话很难调出）

而对于二维数点问题，所需要的约束条件大多要转化为位置关系，下面这道题就是一个有趣的例子（如果能够想到位置的转化，题目就容易做出了）

P4137 Rmq Problem / mex

P4137

题意

给定一个数列 a[i]，每次询问一个区间内最小没有出现过的自然数。

题目分析

这道题与前两道题的区别在于，前两题是“计数”类问题，大抵要求出满足某条件的数的个数。而本题则是“找数”问题，要找出一个满足条件的（唯一确定的）数。

这提示我们，在做本题时不一定要遵循着二维数点的一般套路。

前文我们说过

对于主席树问题，要么存入位置对权值做手段（即可持久化权值线段树），要么存入权值对位置做操作（即可持久化位置线段树）。

本题按照前两题的做法似乎很难沿用（当然读者可以自行尝试思考），所以我们可以反过来思考，如果对于权值来查询位置呢？

这就“拨开云雾见青天”了，考虑对于每个权值 a[i]，找到对应这个 a[i] 的最小的位置 i，设其为 \mathrm{f[a[i]]=i}，而后对于所有 a[i]（这里就变为对权值查找位置了），求其 \mathrm{f[a[i]]<l} 的最小 a[i]。

请思考这个过程，\mathrm{f[a[i]]<l} 自然就是在说这个 a[i] 出现的位置不在 [l,r] 中，而只需求出满足此条件最小的 a[i]。细观条件“在 [l,r] 中没出现，最小”这即是 mex 的定义。

而观察限制条件

这又是一个二维数点问题，只不过维护信息时要维护最小值。

本题的奥妙所在在于转换思维——“对于权值维护其位置”，只要知道了这一点，其他的转化就是平凡的了。

套路2：二分+主席树

二分+主席树。顾名思义，对于一个问题进行二分答案时，以主席树进行判定。

这类题的关键点仍在于转化，把问题转化为二分答案后，判定就成了主席树的问题。

P2839 [国家集训队] middle

P2839

题意

每次求左端点在 [a,b] 中，右端点在 [c,d] 中的区间的中位数的最大值。

这里的中位数指的是，对于一个长为 n 的数组 b[i]，其中位数定义为 \mathrm{b[\frac{n}{2}]}。

题目分析

针对中位数自然很容易想到二分。所以我们考虑对排好序的数组二分中位数。于是问题就转化为了，对于一个数 mid，判断其是否为左端点在 [a,b] 中，右端点在 [c,d] 中的区间的中位数。

考虑转化，对于每个数 a[i]，将比 a[i] 小的数改为 1，其余为0。这样对于每个数

Sign on Fence

CF484E

题意

要你在区间 [l,r] 内选一个长度为k的区间，求区间最小数的最大值。

题目分析

看到 “区间最小数的最大值”，很容易想到二分（最值的最值事实上已经成为一种二分经典套路），即二分区间最小数。问题就转化为了对于一个数 mid，判断其是否为区间的最小值。

对于每个数 mid，将其左边的数极左

套路3：树上主席树

P2633 Count on a tree

P3302 [SDOI2013] 森林