可持久化 DS 学习笔记

2026/7/22 20:40:23

前言

矮压怎么又是 $DS$
LZY：为什么没有可持久化
msjing：还在咕

可持久化

什么是可持久化捏？
就是利用一些操作，存储曾经的信息而不是覆盖
比如可持久化并查集（不会呢），你就可以查一个点曾经的连通性
有了可持久化，我们就可以进行很多在线操作
那可持久化可以维护什么问题捏？
~~我也不知道~~
基本所有在线的暴力过不去的都可以用可持久化过

主席树

主席树全称是可持久化权值线段树，e，我也不知道为啥叫主席树
主席树的实现依据线段树，主要可以维护任意区间的各种玩意
我们看一道典题

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

其实你可以先去做主席树 $1$
~~我是不会告诉你我 void 写成 int 然后没有写返回值叫了 inf 发 RE 的~~
这个问题需要查区间第 $k$ 小，那么我们可以利用主席树，保留之前的版本，然后就可以方便的查询
怎么记录之前的信息？直接每个版本搞一棵线段树
显然这不太行，所以我们考虑减少一些没必要的操作
我们发现在加入一个新值而产生新状态时，有一些点是不变的，所以我们就可以只建改的点，而这些点是 $\log$ 级别的，时空都可以接受
~~从 oiwiki 偷张图~~

persistent-seg

这个东西明显不能用普通线段树的维护方式搞，所以动态开点
那主席树会搞了，如何求这个问题呢？
我们利用一下前缀和的思想，我们发现求 $[l,r]$ 的区间其实是 $[1,r]$ 减掉 $[1,l-1]$
~~我也不知道为什么~~
行了现在就搞完了，记得数组开大点

点击查看代码

#include<bits/stdc++.h>
#define lson tr[rt].l
#define rson tr[rt].r
using namespace std;
constexpr int maxn=1e6+10,inf=0x7f7f7f7f;
int read()
{int x=0,f=1;char ch=getchar();while (ch<'0' || ch>'9'){if (ch == '-') f=-1;ch=getchar();}while (ch>='0' && ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;
}
int n,m,a[maxn];
int root[maxn];
int seg;
struct segtree
{struct _ {int l,r,sum;}tr[maxn*100];void Pus(int rt) {tr[rt].sum=tr[lson].sum+tr[rson].sum;}void Upd(int lrt,int &nrt,int l,int r,int p,int v){
//        cerr << lrt << " "<< nrt << " "<<l << " " <<r << " " << p << " " << v << endl;if (!nrt) nrt=++seg;tr[nrt]=tr[lrt];if (l == r){tr[nrt].sum+=v;return;}int mid=(l+r) >> 1;if (p<=mid) Upd(tr[lrt].l,tr[nrt].l=++seg,l,mid,p,v);else Upd(tr[lrt].r,tr[nrt].r=++seg,mid+1,r,p,v);Pus(nrt);}int Que(int lrt,int nrt,int l,int r,int p){if (l == r) return l;int mid=(l+r) >> 1;int k=tr[tr[nrt].l].sum-tr[tr[lrt].l].sum;if (p<=k) return Que(tr[lrt].l,tr[nrt].l,l,mid,p);else return Que(tr[lrt].r,tr[nrt].r,mid+1,r,p-k);}
}S;int main()
{
//	freopen("P3834_6.in","r",stdin);n=read(),m=read();for (int i=1;i<=n;i++) a[i]=read(),S.Upd(root[i-1],root[i],0,1e9,a[i],1);for (int i=1;i<=m;i++){int x=read(),y=read(),z=read();printf("%d\n",S.Que(root[x-1],root[y],0,1e9,z));}return 0;
}

接下来再我们搞几道例题

例题P2633 Count on a tree

其实你观察一下，发现需要在树上搞
那么~~直接重剖~~考虑让查变成区间的东西
我们知道主席树有优良的前缀能力，我们可以搞个柿子

$sum[x]+sum[y]−sum[lca]−sum[fa[lca]]$

这个柿子搞完后就可以直接主席树干干干了
这个是sbmqwm改出来的谢谢你喵
sbmqwm：没事喵
~~其实sbmqwm 5 秒就改出来了~~

点击查看代码

#include<bits/stdc++.h>
#define lson tr[rt].l
#define rson tr[rt].r
using namespace std;
constexpr int maxn=1e6+10,inf=0x7f7f7f7f;
int read()
{int x=0,f=1;char ch=getchar();while (ch<'0' || ch>'9'){if (ch == '-') f=-1;ch=getchar();}while (ch>='0' && ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;
}
int n,m,a[maxn],b[maxn];
int root[maxn];
int seg;
int h[maxn],to[maxn],nxt[maxn],tot;
void add(int x,int y) {tot++,to[tot]=y,nxt[tot]=h[x],h[x]=tot;}
struct segtree
{struct _ {int l,r,sum;}tr[maxn*100];void Upd(int lrt,int &nrt,int l,int r,int p){nrt=++seg;tr[nrt]=tr[lrt];tr[nrt].sum++;if (l == r) return;int mid=(l+r) >> 1;if (p<=mid) Upd(tr[lrt].l,tr[nrt].l,l,mid,p);else Upd(tr[lrt].r,tr[nrt].r,mid+1,r,p);}int Que(int lrt,int nrt,int lca,int lcafa,int l,int r,int p){if (l == r) return l;int mid=(l+r) >> 1;int k=tr[tr[nrt].l].sum+tr[tr[lrt].l].sum-tr[tr[lca].l].sum-tr[tr[lcafa].l].sum;if (p<=k) return Que(tr[lrt].l,tr[nrt].l,tr[lca].l,tr[lcafa].l,l,mid,p);else return Que(tr[lrt].r,tr[nrt].r,tr[lca].r,tr[lcafa].r,mid+1,r,p-k);}
}S;
struct Tree_Line_Pow_Divide_to_Lca
{int fa[maxn],son[maxn],top[maxn],dep[maxn],siz[maxn];int dfn[maxn],rnk[maxn],cnt;void dfs1(int x){son[x]=-1;siz[x]=1;S.Upd(root[fa[x]],root[x],1,n,a[x]);for (int i=h[x];i;i=nxt[i]){int y=to[i];if (dep[y]) continue;dep[y]=dep[x]+1;fa[y]=x;dfs1(y);siz[x]+=siz[y];if (son[x] == -1 || siz[y]>siz[son[x]]) son[x]=y;}}void dfs2(int x,int t){top[x]=t;cnt++;dfn[x]=cnt;rnk[cnt]=x;if (son[x] == -1) return;dfs2(son[x],t);for (int i=h[x];i;i=nxt[i]){int y=to[i];if (y == son[x] || y == fa[x]) continue;dfs2(y,y);}}int 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;}
}T;
int ans;
int main()
{n=read(),m=read();for (int i=1;i<=n;i++) a[i]=b[i]=read();sort(b+1,b+1+n);int s=unique(b+1,b+1+n)-b-1;for (int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+s,a[i])-b;for (int i=1;i<n;i++){int x=read(),y=read();add(x,y);add(y,x);}T.dep[1]=1,T.dfs1(1),T.dfs2(1,1);for (int i=1;i<=m;i++){int x=read()^ans,y=read(),z=read();int lca=T.lca(x,y);ans=S.Que(root[x],root[y],root[lca],root[T.fa[lca]],1,n,z);ans=b[ans];printf("%d\n",ans);}return 0;
}

~~依旧热衷于重剖求 LCA~~

例题P4587 [FJOI2016] 神秘数

这个东西非常难搞
~~我们发现毫无思路呢~~
我们进行一波非常牛比的转化
先考虑什么情况可以使答案增加，对 $a$ 排序，设当前可以拼出的数都在 $[1,sum]$ 内，当且仅当 $a_i<=sum+1$ 才可以，此时答案扩展到 $[1,sum+p]$
那这个东西太man了，所以优化优化
我们发现我们需要求出在 $[l,r]$ 区间内且值域大小在 $[sum_{pre}+2,sum+1]$ 范围的数的和
然后重复上述
不好理解对吧，我们模拟一下
我们拿题目的序列模拟
对于 $S[1,1,1,4,13]$，首先设 $sum=0,ans=sum+1=1,pre_sum=-1$
然后，我们查询 $[1,1]$，有 $3$ 个 $1$，让 $sum=3,ans=sum+1=4$
然后查询 $[2,4]$，有 $1$ 个 $4$，让 $sum=3+4=7,ans=sum+1=8$
然后查 $[5,8]$，发现没有数，结束，答案为 $ans=8$
实现的话你就没必要模拟了，直接让 $sum = que([1,sum+1])$
然后没啥了
我不会告诉你我上面传 $1$ 下面查 $0$ 的

批注 2026-07-22 200359

点击查看代码

#include<bits/stdc++.h>
#define lson tr[rt].l
#define rson tr[rt].r
using namespace std;
constexpr int maxn=1e6+10,inf=0x7f7f7f7f;
int read()
{int x=0,f=1;char ch=getchar();while (ch<'0' || ch>'9'){if (ch == '-') f=-1;ch=getchar();}while (ch>='0' && ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;
}
int n,m,a[maxn];
int root[maxn];
int seg;
struct segtree
{struct _ {int l,r,sum;}tr[maxn*100];void Upd(int lt,int &nw,int l,int r,int p,int v){nw=++seg;tr[nw]=tr[lt];tr[nw].sum+=v;if (l == r) return;int mid=(l+r) >> 1;if (p<=mid) Upd(tr[lt].l,tr[nw].l,l,mid,p,v);else Upd(tr[lt].r,tr[nw].r,mid+1,r,p,v);}int Que(int lt,int nw,int l,int r,int L,int R){int res=0;if (L<=l && r<=R) return tr[nw].sum-tr[lt].sum;int mid=(l+r) >> 1;if (L<=mid) res+=Que(tr[lt].l,tr[nw].l,l,mid,L,R);if (R>mid) res+=Que(tr[lt].r,tr[nw].r,mid+1,r,L,R);return res;}
}S;
int main()
{n=read();for (int i=1;i<=n;i++) a[i]=read(),S.Upd(root[i-1],root[i],1,1e9,a[i],a[i]);m=read();for (int i=1;i<=m;i++){int x=read(),y=read();int sum=0,ans=1;while (78+13 == 91){sum=S.Que(root[x-1],root[y],1,1e9,1,ans);if (sum>=ans) ans=sum+1;else break;}printf("%d\n",ans);}return 0;
}