数据结构笔记 [2] 可持久化线段树

keepwatcher_kensap · 2024-10-08 21:23:25 · 算法·理论

Part 1 前置 1 · 权值线段树

常规线段树是将长度 n 的序列划分为若干个部分，此时线段是底部存储的是 a_{1\dots n} 的值。但我们发现无法新增一个值 a_{n+1} 到线段树中。于是我们换种思路，我们存储 a_{1 \dots n} 中 a_{\min} \dots a_{\max} 的个数，也就是存数的个数，这样就可以新增 a_{n+1} 了。

对于区间 [l,r] 的第 k 小值，我们每次考虑 [l,mid],[mid+1,r] 两个子区间，判断 k 出现在哪个区间即可，具体地：

• 若 val_{[l,mid]} \leq k，说明 k 小值出现在区间 [l,mid]。
• 若 val_{[l,mid]} > k，说明 k 小值出现在区间 [mid+1,r]。

反推则可以求出数值 x 在区间的排名：

• 若 mid \leq x，说明 x 在区间 [l,mid]，排名为 [1,mid-l+1]。
• 若 mid > x，说明 x 在区间 [mid+1,r]，排名为 [mid-l+2,r-l+1]。

Part 2 前置 2 · 离散化

在使用权值线段树时常发现 a_i 的数值会过大或过小，例如 a_i>10^9，此时我们将 a_{\min} \dots a_{\max} 都开一个空间就会炸。我们发现 a_{1 \dots n} 中至多有 n 种可能的数值，于是我们将 b_i 定义为 a_i 的数值在 a_{1\dots n} 中是第几小，这样可以将 a 转化为一个 1 \dots n 的排序 b 数组。具体地：

• 将 a 复制一份，得到 c 数组。
• 排序 c 数组。
• 定义 mp，表示 a_i 的数值在 a_{1\dots n} 中是第几小，有 mp_{c_i}=i。（记得判重）
• 令 b_i=mp_{a_i} 。
• 定义 mq，表示序数为 i 的数值对应 a_i，有 mq_i=c_i。

于是我们拿着转换而来的 b 数组去构造权值线段树，再转化为 a 数组的答案即可。

进一步的，关于判重的过程，我们可以用 c++ 自带的 unique 实现（自己查资料吧反正我也不会。

Part 3 引入

我们知道线段树可以求区间极值，而权值线段树可以求区间第 k 大值。但这都只对当前状态有效，如果要在更新后访问历史版本就做不到了。当我们将每颗线段树都开一个专门的空间，那必炸。于是我们考虑如何节约空间。

如果是红色框中的值发生了修改，绿色表示前后线段树相同的点，蓝色和橙色表示前后独有的点。我们会发现，只是修改了一条链，也就是 \log n 个点。

Part 4 建树 & 修改 & 求值

建树

原先线段树中每个点存储三个数值 ls,rs,val，表示左结点，右节点，权值。我们按照线段树的方法建好原版树。

inline void Build(int l,int r,int id)
{
    if (l==r) { val[id]=...;return ; }
    int mid=l+(r-l)/2;
    ls[id]=++cnt,rs[id]=++cnt; // 建新点
    Build(l,mid,ls[id]),Build(mid+1,r,rs[id]);
    val[id]=val[ls[id]]+val[rs[id]];
    return ;
}

修改

我们考虑对图中橙色点，也就是新改变的点开空间。为了记录每一时刻线段树的状态，我们对每一个时刻都开一个根节点。可以让 ls,rs 其中一个连接原本线段树的一半，另一个连接新的点，并往下细分。存储某一状态就是存储该状态的根节点。

inline void Update(int l,int r,int id,int nid,int p,int x)
// id为原先点,nid为更新后的点
{
    if (l==p && r==p) { val[nid]=x;return ; }
    int mid=l+(r-l)/2;
    if (l<=p && p<=mid) // 答案在左区间
    {
        ls[nid]=++cnt,rs[nid]=rs[id],Update(l,mid,ls[id],ls[nid],p,x);
    }
    if (mid+1<=p && p<=r) // 答案在右区间
    {
        rs[nid]=++cnt,ls[nid]=ls[id],Update(mid+1,r,rs[id],rs[nid],p,x);
    }
    val[nid]=val[ls[nid]]+val[rs[nid]];
    return ;
}

如上，这个新的线段树的根节点就是未做任何修改的 nid，即未开始修改前一刻的 all+1。记录下每一时刻时线段树的根，下次就可以直接调用了。

求值

很显然和普通的线段树没有本质上的区别。

inline int Query(int l,int r,int s,int t,int id)
// [l,r]为当前区间,[s,t]为目标区间
{
    if (l>t || r<s) return 0;
    if (l>=s && r<=t) return val[id];
    int mid=l+(r-l)/2;
    return Query(l,mid,s,t,ls[id])+Query(mid+1,r,s,t,rs[id]);
}

例题

P3919 【模板】可持久化线段树 1（可持久化数组）

我们每次进行 Update 的时候，都记录当前线段树的根节点，调用任何历史状态的线段树都是需要调用其根节点的。

我们知道每次更新都会新增 \log n 个点，最多进行 m 次更新，因此空间需要开到 m \log n，只要不炸就尽量开大吧，可以用 sizeof(数组名)/1024/1024 的方式来查询该数组所占的空间（单位 MB）。

#include <bits/stdc++.h>
using namespace std;
const int maxn=50000005;
int n,m,a[maxn],rt[maxn],cnt=1;
int ls[maxn],rs[maxn],val[maxn];
inline int Read()
{
    int x=0,y=1;
    char ch=getchar();
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') y=-1;ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+int(ch-'0');ch=getchar();
    }
    return x*y;
}
inline void Build(int l,int r,int id)
{
    if (l==r) { val[id]=a[l];return ; }
    int mid=l+(r-l)/2;
    ls[id]=++cnt,rs[id]=++cnt;
    Build(l,mid,ls[id]),Build(mid+1,r,rs[id]);
    val[id]=val[ls[id]]+val[rs[id]];
    return ;
}
inline void Update(int l,int r,int id,int nid,int p,int x)
{
    if (l==p && r==p) { val[nid]=x;return ; }
    int mid=l+(r-l)/2;
    if (l<=p && p<=mid)
    {
        ls[nid]=++cnt,rs[nid]=rs[id],Update(l,mid,ls[id],ls[nid],p,x);
    }
    if (mid+1<=p && p<=r)
    {
        rs[nid]=++cnt,ls[nid]=ls[id],Update(mid+1,r,rs[id],rs[nid],p,x);
    }
    val[nid]=val[ls[nid]]+val[rs[nid]];
    return ;
}
inline int Query(int l,int r,int s,int t,int id)
{
    if (l>t || r<s) return 0;
    if (l>=s && r<=t) return val[id];
    int mid=l+(r-l)/2;
    return Query(l,mid,s,t,ls[id])+Query(mid+1,r,s,t,rs[id]);
}
int main()
{
    n=Read(),m=Read();
    for (int i=1;i<=n;i++) a[i]=Read();
    Build(1,n,1),rt[0]=1;
    for (int i=1;i<=m;i++)
    {
        int v=Read(),op=Read(),loc=Read();
        if (op==1)
        {
            int value=Read();
            rt[i]=++cnt;
            Update(1,n,rt[v],rt[i],loc,value);
        }
        if (op==2)
        {
            rt[i]=rt[v];
            printf("%d\n",Query(1,n,loc,loc,rt[v]));
        }
    }
    return 0;
}

Part 5 特定值 & 排名

上文是以线段树的形式操作，同理可用权值线段树（你应该会吧。

对于区间 [l,r] 的第 k 小值，我们可以先建立一个完全空的权值线段树。将原数组 a 的值一个个加入，记录下每次该状态下的权值线段树，同上文线段树。于是我们就得到了 n 个权值线段树，第 i 个权值线段树记录 a_{1 \dots i} 各数值的情况。

我们不难发现，权值线段树是存在加减法的，也就是权值线段树对应的点之间相加减。区间 [l,r] 的权值线段树就是区间 [1,r] 的权值线段树减去区间 [1,l-1] 的权值线段树。于是我们就得到了一颗代表目标区间的权值线段树，按照普通权值线段树的方法就可以求出特定值 & 排名。

inline int Ranking(int l,int r,int ln,int rn,int kn)
对于区间[lc,rc]的第kc大值，可用Ranking(1,n,rt[lc-1],rt[rc],kn)求出
{
    if (l==r) return l;
    int mid=l+(r-l)/2;
    int lv=val[ls[rn]]-val[ls[ln]];
    if (kn<=lv) return Ranking(l,mid,ls[ln],ls[rn],kn);
    return Ranking(mid+1,r,rs[ln],rs[rn],kn-lv);
}

例题

P3834 【模板】可持久化线段树 2

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e7+5;
int n,m,a[maxn],ls[maxn],rs[maxn],val[maxn];
int all=1,c[maxn],rt[maxn];
map<int,int> mp,mq;
inline int Read()
{
    int x=0,y=1;
    char ch=getchar();
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') y=-1;ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+int(ch-'0');ch=getchar();
    }
    return x*y;
}
inline void Prepare()
{
    for (int i=1;i<=n;i++) c[i]=a[i];
    sort(c+1,c+n+1);
    unique(c+1,c+n+1);
    for (int i=1,j=0;i<=n;i++)
    {
        if (i!=1 && c[i]==c[i-1]) continue;
        mp[c[i]]=++j,mq[j]=c[i];
    }
    for (int i=1;i<=n;i++) a[i]=mp[a[i]];
    return ;
}
inline void Build(int l,int r,int id)
{
    val[id]=0;
    if (l==r) return ;
    int mid=l+(r-l)/2;
    ls[id]=++all,rs[id]=++all;
    Build(l,mid,ls[id]),Build(mid+1,r,rs[id]);
    return ;
}
inline void Update(int l,int r,int id,int nid,int p)
{
    if (l==p && r==p) { val[nid]=val[id]+1;return ; }
    int mid=l+(r-l)/2;
    if (l<=p && p<=mid)
    {
        ls[nid]=++all,rs[nid]=rs[id],Update(l,mid,ls[id],ls[nid],p);
    }
    if (mid+1<=p && p<=r)
    {
        rs[nid]=++all,ls[nid]=ls[id],Update(mid+1,r,rs[id],rs[nid],p);
    }
    val[nid]=val[ls[nid]]+val[rs[nid]];
    return ;
}
inline int Ranking(int l,int r,int ln,int rn,int kn)
{
    if (l==r) return l;
    int mid=l+(r-l)/2;
    int lv=val[ls[rn]]-val[ls[ln]];
    if (kn<=lv) return Ranking(l,mid,ls[ln],ls[rn],kn);
    return Ranking(mid+1,r,rs[ln],rs[rn],kn-lv);
}
int main()
{
    n=Read(),m=Read();
    for (int i=1;i<=n;i++) a[i]=Read();
    Prepare(),Build(1,n,1);
    rt[0]=1;for (int i=1;i<=n;i++)
    {
        rt[i]=++all,Update(1,n,rt[i-1],rt[i],a[i]);
    }
    for (int i=1;i<=m;i++)
    {
        int lm=Read(),rm=Read(),km=Read();
        printf("%d\n",mq[Ranking(1,n,rt[lm-1],rt[rm],km)]);
    }
    return 0;
}

Part 6 扩展 · 可持久化并查集

还是公用空间的原理，但我不想写了……

Part 7 后记

啊啊啊啊啊马上要 CSP 2024 第二轮了，S 组一等奖我就买下我心心念念的 Jellycat 的龙。

参考文献：

https://oi-wiki.org/ds/persistent-seg/

https://zhuanlan.zhihu.com/p/250565583