可持久化数据结构的前提是其拓扑排序是不变的；
比如线段树，我们改变的总是它维护的数值，他的结构一旦定下来就不会变了；
二、可持久化的核心思想是类似git操作，我们维护版本间的差异，而不是维护整个版本；
主席树
主席树又称可持久化线段树，其持久化的核心思想和引言的一致；
主席树难以进行区间修改操作(当然我们可以通过永久化懒标记实现, 一般碰不上)
也就是我们每修改一个节点，我们就创建一个新的副本，并在副本的基础上进行修改；
如图所示，假设我们修改了
1
,
2
,
4
,
8
1,2,4,8
1,2,4,8这条链，我们就创建这条链的一个备份，并且在这条链上修改；
每个版本我们都认为他是一颗线段树；
因为版本间只有若干节点的不同
因此其他相同节点是各个版本共用的；
空间大小因为线段树上的修改，每次只会涉及 4 l o g 2 n 4log_2n 4log2n左右的节点；
假设有 n n n个节点，一般来说空间只需要开 4 ∗ n + n l o g 2 n 4*n+nlog_2n 4∗n+nlog2n就够了；
如果要保险的话，开 n < < 5 n<<5 n<<5肯定够了…
例题一第K小数
首先，因为数值比较大，范围比较小，因此我们离散化处理一下；
其次，我们在数值上建立一颗线段树(注意不是区间)；
然后遍历数组的每一个元素，每遍历一个元素，我们就创建一个新的版本；
这样我们一共有 n + 1 n+1 n+1个版本(0~n)；
我们用 r o o t ( i ) root(i) root(i)表示第 i i i个版本的线段树根节点编号；
询问 [ L , R ] [L,R] [L,R]时，我们用第 R R R个版本的线段树减去第 L − 1 L-1 L−1个版本的线段树；
因为第 i i i个版本的线段树，表示的是 1 到 i 1到i 1到i以来所有改变的值；
因此第 R R R个版本减去第 L − 1 L-1 L−1个版本后;
我们就知道版本 [ L , R ] [L,R] [L,R]改变了什么；
也就是前缀和的思想；
又因为我们是每遍历到一个元素就更新一个版本；
因此求区间 [ L , R ] [L,R] [L,R]就转化为了求版本 [ L , R ] [L,R] [L,R]
如下图所示，比如我们要区间 [ 2 , 4 ] [2,4] [2,4]第二小的数；
第一棵树是版本 4 4 4，第二棵树是版本 1 1 1；
因为数值域
[
1
,
2
]
[1,2]
[1,2]只有一个数，
[
3
,
4
]
[3,4]
[3,4]有两个数，因此我们去右子树找；
在右子树的左子树就找到了我们的答案；
Code注意和普通线段树不同，我们的节点是不维护区间的；
节点中的 l , r l,r l,r是左右子树的坐标；
而我们存树则类似于图的链式前向星存法；
代码中的q代表新版本，p代表旧版本！！！
#include例题二、 题面#include #include #include #include using namespace std; typedef long long ll; const int N = 1e5 + 10; struct Node{ int lc,rc;//左右子树节点的编号 int sum;//当前节点里面维护了多少个数 }tr[N*4 + N*17]; vector ve; //root(i)表示第i个版本的线段树根节点编号 int n,m,root[N],cnt,a[N]; //映射到[1,n] int _get(int x){ return 1 + lower_bound(ve.begin(),ve.end(),x) - ve.begin(); } //在数值上建立线段树 int build(int l,int r){ int p = ++cnt; if(l == r) return p; int mid = (l+r) >> 1; tr[p].lc = build(l,mid); tr[p].rc = build(mid+1,r); return p; } //更新版本 int update(int p,int l,int r,int val){ int q = ++cnt; tr[q] = tr[p];//先复制上个版本 if(l == r){ ++tr[q].sum; return q; } int mid = (l+r) >> 1; if(val<=mid) tr[q].lc = update(tr[p].lc,l,mid,val); else tr[q].rc = update(tr[p].rc,mid+1,r,val); tr[q].sum = tr[tr[q].lc].sum + tr[tr[q].rc].sum; return q; } //返回第k小的数离散后的坐标 int query(int q,int p,int l,int r,int k){ if(l == r) return l; int sum = tr[tr[q].lc].sum - tr[tr[p].lc].sum; int mid = (l+r) >> 1; //去左树 if(k<=sum) return query(tr[q].lc,tr[p].lc,l,mid,k); //去右树 else return query(tr[q].rc,tr[p].rc,mid+1,r,k-sum); } int main(){ std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin >> n >> m; for(int i=1;i<=n;++i){ cin >> a[i]; ve.push_back(a[i]); } sort(ve.begin(),ve.end()); ve.erase(unique(ve.begin(),ve.end()),ve.end()); root[0] = build(1,ve.size()); for(int i=1;i<=n;++i){ root[i] = update(root[i-1],1,ve.size(),_get(a[i])); } int L,R,k,idx; while(m--){ cin >> L >> R >> k; idx = query(root[R],root[L-1],1,ve.size(),k); cout << ve[idx-1] << 'n'; } return 0; }
洛谷P3919
这题跟上题不太一样，有点传统线段树维护区间的味道；
上一道题更类似于权值线段树；
线段树节点维护的是左儿子、右儿子、当前节点的值；
因为这道题是类似维护区间，因此我们不需要离散化；
Code#include#include #include using namespace std; typedef long long ll; const int N = 1e6 + 10; struct Node{ int lc,rc,val; }tr[N<<5]; int cnt,n,m,a[N],root[N]; int build(int l,int r){ int q = ++cnt; if(l == r){ tr[q].val = a[l]; return q; } int mid = (l+r) >> 1; tr[q].lc = build(l,mid); tr[q].rc = build(mid+1,r); return q; } int update(int p,int l,int r,int loc,int val){ int q = ++cnt; tr[q] = tr[p]; if(l == r){ tr[q].val = val; return q; } int mid = (l+r) >> 1; if(loc <= mid) tr[q].lc = update(tr[p].lc,l,mid,loc,val); else tr[q].rc = update(tr[p].rc,mid+1,r,loc,val); return q; } int query(int p,int l,int r,int loc){ if(l == r){ return tr[p].val; } int mid = (l+r) >> 1; if(loc <= mid) return query(tr[p].lc,l,mid,loc); else return query(tr[p].rc,mid+1,r,loc); } int main(){ std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin >> n >> m; for(int i=1;i<=n;++i){ cin >> a[i]; } root[0] = build(1,n); for(int i=1,v,op,loc,val;i<=m;++i){ cin >> v >> op; if(op == 1){ cin >> loc >> val; root[i] = update(root[v],1,n,loc,val); }else{ cin >> loc; root[i] = root[v]; cout << query(root[v],1,n,loc) << 'n'; } } return 0; }
