可持久化快速入门
可持久化
目录- 可持久化
- 可持久化思想
- 可持久化数组
- 支持
- 实现: 线段树
- 可持久化线段树
- 可持久 但只能持久一点点
- 支持: 区间第 \(k\) 大
- 实现: 线段树
- 点睛之笔
- 可持久 真正的可持久
- 可持久 但只能持久一点点
- 其它的可持久化数据结构
- 可持久化并查集
- 可持久化栈
- ……
- 什么数据结构不能可持久化?
- 完结撒花
可持久化思想
在对于一次操作，不改变原本的数据，而是：
- 对于会被修改的部分新增一些节点保存修改；
- 保留原有数据间的组织关系；
- 记录下当前操作的起始编号；
从记录下的版本编号，根据原有的组织关系遍历整个数据结构
可持久化数组
支持
- 历史版本单点修改
- 历史版本单点询问
实现: 线段树
struct Segment_Tree_Node { int Son[2];//Son[0]:left son; 1:right; int Value; Segment_Tree_Node(int s1,int s2,int val) { Son[1] = s1; Son[2] = s2; Value = val; } }; int Cnt;//虚假的内存池 Segment_Tree_Node node[Maxn * 60];//空间大小为 O((N+M)logN):原树大小为O(NlogN),每次修改新增一条链
-
读入: 读入数组长度及数组
-
建树: 对原数组建树
int Build(int l, int r) //对[l,r]进行建树,并返回树根节点的值 { int u = ++Cnt; //从内存(假)中取一个节点 if (l == r) node[u] = Segment_Tree_Node(0, 0, a[l]); //是叶子节点则 else { //并没有到叶子节点 int mid = l + r >> 1; //将区间一分为二 node[u].Son[0] = Build(l, mid); //对左区间建树 node[u].Son[1] = Build(mid + 1, r); //对右区间建树 } return u; //返回根节点编号 } -
查询:从对应版本的根节点进入即可访问到对应版本
int Ask(int u, int l, int r, int p) { if (l == r) //左右边界重合, 递归查询结束 return node[u].Value; //返回当前的值 else { //递归查询没有结束 int mid = l + r >> 1; //将当前询问的区间一分为二 int f = mid < p; //锁定在当前区间的左半部(f=0),还是右半部(f=1) f ? l = mid + 1 : r = mid; //更新的待查询区间的左右边界 return Ask(node[u].Son[f], l, r, p); //返回递归查询的结果 } } -
修改: 对于历史版本的修改只会影响到一条链(不超过 $ LogN$? 个节点),因此新建一条链存储继承的组织关系和修改即可
int Edit(int v, int l, int r, int p, int x) { int u = ++Cnt; //从虚假的内存池里面拿一个点 node[u] = node[v]; //继承历史版本的一切 if (l == r) //找到了需要修改的节点 node[u].Value = x; //修改当前节点的value就好 else { //还没有找到修改的单点 int mid = l + r >> 1; //将当前区间一分为二 int f = mid < p; //锁定需要修改的节点在当前区间的左半部(f=0),还是右半部(f=1) f ? l = mid + 1 : r = mid; //更新的待查询区间的左右边界 node[u].Son[f] = Edit(node[v].Son[f], l, r, p, x); //递归执行修改, 并更新这条链的组织关系 } return u; //返回新树的根节点 } -
完整代码:例题: 洛谷 P3834 【模板】可持久化线段树 2（主席树）
#includeusing namespace std; #define endl '\n' #define rep(i, a, b) for (int i = (a), i##ss = (b); i <= i##ss; ++i) #define per(i, a, b) for (int i = (a), i##ss = (b); i >= i##ss; --i) #define debug(x) cerr << "||debug: " << (#x) << " = " << x << '\n' typedef double db; typedef long long ll; typedef pair
可持久化线段树
可持久 但只能持久一点点
既然我们已经用可持久化线段树实现了数组的可持久化,那么怎么能满足于单点的查询呢?
区间查询 配合 权值线段树, 我们就能实现区间第k小(大)的查询了
权值线段树: 下标为权值, 节点记录该(数值大小的)区间内的元素个数
一种比较显然而不计代价的做法是: 可以对每个$ [1,i] $ 区间内的做一棵权值线段树
为什么要这么做呢?
因为如此一来, 只需要将 \(r\) 的线段树减去 \(l-1\)? 的线段树, 再在得到的线段树上做一个查找就能解决这个问题啦!
虽然这个做法时空复杂度都很笨逼
但是只需要运用一下刚才用过的可持久化技术, 每个点的版本都从前一个点继承就可以快速切题了233
支持: 区间第 \(k\) 大
- 查询静态序列的区间第 \(k\) 大
实现: 线段树
struct Tree_Node { int Son[2]; int Sum; Tree_Node(int s1=0, int s2=0, int sum=0) { Son[1] = s1; Son[2] = s2; Sum = sum; } }; int Cnt = 0; Tree_Node node[Persistent_Segment_Tree_Maxn << 5];
-
读入数组,并离散化
-
建树: 每个结点的版本都从前一个节点版本继承而来
Edition[0] = pst.Build(1, N);//建空树 rep(i, 1, n) Edition[i] = pst.Modify(Edition[i - 1], 1, N, b[i]);//继承前一个版本并且新增一个元素int Build(int l, int r) { int u = ++Cnt; if (l == r) node[u] = Tree_Node(0, 0, 0); else { int mid = l + r >> 1; node[u].Son[0] = Build(l, mid); node[u].Son[1] = Build(mid + 1, r); node[u].Sum = 0; } return u; } int Modify(int v, int l, int r, int x) { /* 当前处理区间为 [l,r] 上一个版本中 管辖当前区间的节点编号为 v , 新的节点node[u] 将继承自它 并管辖当前修改完成后的当前区间 需要在x元素上新增 */ int u = ++Cnt; node[u] = node[v]; if (l == r) node[u].Sum++; else { int mid = l + r >> 1; int f = mid < x; f ? l = mid + 1 : r = mid; node[u].Son[f] = Modify(node[v].Son[f], l, r, x); node[u].Sum++; } return u; } -
查询: 并不不要真正的将两棵线段树对应点做差形成一个新的线段树233, 只需要把两个当前点的左子树大小做个差, 判断一下该进入左子树查询还是右子树查询即可
int Ask(int u, int v, int l, int r, int k) { /* Tree(u)-Tree(v)得到的树的第k大的数 */ if (l == r) return l; int f = node[ls(u)].Sum - node[ls(v)].Sum; if (f < k) return Ask(rs(u), rs(v), (l + r >> 1) + 1, r, k - f); else return Ask(ls(u), ls(v), l, l + r >> 1, k); } -
完整代码: 例题: 洛谷 - P3834 【模板】可持久化线段树 2 (主席树)
#includeusing namespace std; #define endl '\n' #define rep(i, a, b) for (int i = (a), i##ss = (b); i <= i##ss; ++i) #define per(i, a, b) for (int i = (a), i##ss = (b); i >= i##ss; --i) #define debug(x) cerr << "||debug: " << (#x) << " = " << x << '\n' typedef double db; typedef long long ll; typedef pair v; public: int Discretize(int a[], int number) { for (int i = 1; i <= number; i++) v.push_back(a[i]); sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); return v.size(); } int Get_Discretize(int x) { return lower_bound(v.begin(), v.end(), x) - v.begin() + 1; } int Back_Discretize(int x) { return v[x - 1]; } }; DISCRETIZE dc; int n, m, N, a[Maxn], b[Maxn], Edition[Maxn]; const int Persistent_Segment_Tree_Maxn = 2e5 + 50; struct Persistent_Segment_Tree { #define ls(u) node[u].Son[0] #define rs(u) node[u].Son[1] struct Tree_Node { int Son[2]; int Sum; Tree_Node(int s1=0, int s2=0, int sum=0) { Son[1] = s1; Son[2] = s2; Sum = sum; } }; int Cnt = 0; Tree_Node node[Persistent_Segment_Tree_Maxn << 5]; int Build(int l, int r) { int u = ++Cnt; if (l == r) node[u] = Tree_Node(0, 0, 0); else { int mid = l + r >> 1; node[u].Son[0] = Build(l, mid); node[u].Son[1] = Build(mid + 1, r); node[u].Sum = 0; } return u; } int Modify(int v, int l, int r, int x) { /* 当前处理区间为 [l,r] 上一个版本中 管辖当前区间的节点编号为 v , 新的节点node[u] 将继承自它 并管辖当前修改完成后的当前区间 需要在x元素上新增 */ int u = ++Cnt; node[u] = node[v]; if (l == r) node[u].Sum++; else { int mid = l + r >> 1; int f = mid < x; f ? l = mid + 1 : r = mid; node[u].Son[f] = Modify(node[v].Son[f], l, r, x); node[u].Sum++; } return u; } int Ask(int u, int v, int l, int r, int k) { /* Tree(u)-Tree(v)得到的树的第k大的数 */ if (l == r) return l; int f = node[ls(u)].Sum - node[ls(v)].Sum; if (f < k) return Ask(rs(u), rs(v), (l + r >> 1) + 1, r, k - f); else return Ask(ls(u), ls(v), l, l + r >> 1, k); } }; Persistent_Segment_Tree pst; int main() { n = Get(), m = Get(); rep(i, 1, n) a[i] = Get(); N = dc.Discretize(a, n); rep(i, 1, n) b[i] = dc.Get_Discretize(a[i]); Edition[0] = pst.Build(1, N); rep(i, 1, n) Edition[i] = pst.Modify(Edition[i - 1], 1, N, b[i]); for (int l, r, k; m; m--) { l = Get(), r = Get(), k = Get(); printf("%d\n", dc.Back_Discretize(pst.Ask(Edition[r], Edition[l - 1], 1, N, k))); } return 0; } /* */ int Get() { bool flag = true; int Rec = 0; char c; for (c = getchar(); !isdigit(c) && c != '-'; c = getchar()) ; if (c == '-') flag = false, c = getchar(); for (; isdigit(c); c = getchar()) Rec = (Rec * 10) - '0' + c; return flag ? Rec : (-Rec); }
点睛之笔
我想 你应该已经注意到了 混进来了个什么东西呢？
让我们用一道题来加深你对它的感悟吧
例题: 洛谷 - P2633 Count on a tree
可持久 真正的可持久
已经是一个写过可持久化线段树的人了，我想你已经将目光投向了怎么修改历史版本
比如, 怎样去实现一个实现一个带修改的区间第 \(k\) 大呢?
是的 到目前为止我们写过的可持久都只能在当前的版本上进行修改
如果想要实现真正的可持久, 修改历史版本, 时间复杂度会退化到 $ O(NlogN)$? ,因为我们?需要修改继承自该版本的每一个版本
联系一下上两道题题目?
嗯……
似乎已经有什么想法浮现了
是的
差分
做区间第 \(k\)? 大的时候我们其实是把两个权值线段树的前缀和做了差
那么 如果我们用树状数组的组织形式来组织权值线段树的各个版本呢？
没毛病 一切就迎刃而解了
注意一下开的空间
其它细节比较简单，附上完整代码：
#include
using namespace std;
#define endl '\n'
#define rep(i, a, b) for (int i = (a), i##ss = (b); i <= i##ss; ++i)
#define per(i, a, b) for (int i = (a), i##ss = (b); i >= i##ss; --i)
#define debug(x) cerr << "||debug: " << (#x) << " = " << x << '\n'
typedef double db;
typedef long long ll;
typedef pair pii;
typedef unsigned long long ull;
const db Pi = acos(-1.0);
const db eps = 1e-6;
inline int Get();
const int Maxn = 1e6 + 5;
const int Maxm = 1e6 + 5;
const int Persistent_Segment_Tree_Maxn = 2e6 + 500;
struct Operation
{
int Operation_Kind;
int x, y, k;
};
struct DISCRETIZE
{
private:
vector v;
public:
int Discretize(int a[], int number)
{
for (int i = 1; i <= number; i++)
v.push_back(a[i]);
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
return v.size();
}
int Get_Discretize(int x)
{
return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}
int Back_Discretize(int x)
{
return v[x - 1];
}
};
struct Persistent_Segment_Tree
{
struct Tree_Node
{
int Son[2];
int Value;
};
int Cnt;
Tree_Node node[Persistent_Segment_Tree_Maxn << 5];
int Add_Componient[Persistent_Segment_Tree_Maxn];
int Del_Componient[Persistent_Segment_Tree_Maxn];
#define ls(u) node[u].Son[0]
#define rs(u) node[u].Son[1]
//从上一个版本继承全部 并实现修改
int Modify(int v, int l, int r, int x, int Delta)
{
/*
v: node number in last version
[l,r]: the segment under operation
x: the index to be changed
val: 1/-1 to change means delete the original one and add a new one
*/
int u = ++Cnt;
node[u] = node[v];
node[u].Value += Delta;
if (l != r)
{
int mid = l + r >> 1;
int f = mid < x;
f ? l = mid + 1 : r = mid;
node[u].Son[f] = Modify(node[v].Son[f], l, r, x, Delta);
}
return u;
}
//版本号组合放在 Add 和 Del 里, 查询思路不变
int Ask(int l, int r, int k)
{
if (l == r) //敌人伏诛
return l; //押送回帝国
int f = 0;
rep(i, 1, Add_Componient[0]) f += node[ls(Add_Componient[i])].Value;
rep(i, 1, Del_Componient[0]) f -= node[ls(Del_Componient[i])].Value;
if (f < k)
{
rep(i, 1, Add_Componient[0]) Add_Componient[i] = rs(Add_Componient[i]); //全军团跃迁至权值域 R悬臂
rep(i, 1, Del_Componient[0]) Del_Componient[i] = rs(Del_Componient[i]);
l = (l + r >> 1) + 1; //坐标校准
k -= f; //武器功率校准
}
else
{
rep(i, 1, Add_Componient[0]) Add_Componient[i] = ls(Add_Componient[i]);
rep(i, 1, Del_Componient[0]) Del_Componient[i] = ls(Del_Componient[i]);
r = l + r >> 1;
}
return Ask(l, r, k); //开炮!
}
};
int n, N, m;
int a[Maxn];
int b[Maxn]; //离散化数组
int Edition[Maxn]; //版本号 下标为原数组编号 存储数据参考树状数组
Operation operations[Maxm]; //记录操作便于离散化
DISCRETIZE dc; //离散化类
Persistent_Segment_Tree pst; //可持久化线段树类
char c;
int LowBit(int x)
{
return x & (-x);
}
int BIT_Ask(int l, int r, int k)
{
/*
询问的区间应由两个版本的前缀和可持久化线段树做差得到
采用树状数组的方式组织前缀和线段树
*/
pst.Add_Componient[0] = 0;
pst.Del_Componient[0] = 0;
for (int i = r; i; i -= LowBit(i))
pst.Add_Componient[++pst.Add_Componient[0]] = Edition[i];
for (int i = l - 1; i; i -= LowBit(i))
pst.Del_Componient[++pst.Del_Componient[0]] = Edition[i];
return pst.Ask(1, N, k);
}
void BIT_Modify(int x, int lat_y, int new_y)
{
a[x] = new_y;
lat_y = dc.Get_Discretize(lat_y);
new_y = dc.Get_Discretize(new_y);
for (int i = x; i <= n; i += LowBit(i))
{
Edition[i] = pst.Modify(Edition[i], 1, N, lat_y, -1);
Edition[i] = pst.Modify(Edition[i], 1, N, new_y, 1);
}
}
void Prepera(int x, int y) // 在 x 位置上插入元素 y
{
y = dc.Get_Discretize(y);
for (int i = x; i <= n; i += LowBit(i)) //在用的只有 n 个版本
Edition[i] = pst.Modify(Edition[i], 1, N, y, 1);
}
int main()
{
// freopen("Test.in", "r", stdin);
// freopen("Test.out", "w", stdout);
n = Get(), m = Get();
rep(i, 1, n) b[i] = a[i] = Get();
b[0] = n;
rep(i, 1, m)
{
for (c = getchar(); c != 'Q' && c != 'C'; c = getchar())
;
operations[i].Operation_Kind = c == 'Q';
operations[i].x = Get(), operations[i].y = Get();
c == 'Q' ? operations[i].k = Get() : b[++b[0]] = operations[i].y;
}
N = dc.Discretize(b, b[0]);
rep(i, 1, n) Prepera(i, a[i]);
// debug(N);
rep(i, 1, m)
if (operations[i].Operation_Kind)
printf("%d\n", dc.Back_Discretize(BIT_Ask(operations[i].x, operations[i].y, operations[i].k)));
else
BIT_Modify(operations[i].x, a[operations[i].x], operations[i].y);
return 0;
}
/*
*/
int Get()
{
bool flag = true;
int Rec = 0;
char c;
for (c = getchar(); !isdigit(c) && c != '-'; c = getchar())
;
if (c == '-')
flag = false, c = getchar();
for (; isdigit(c); c = getchar())
Rec = (Rec * 10) - '0' + c;
return flag ? Rec : (-Rec);
}
其它的可持久化数据结构
可持久化并查集
由题可知: 可持久化并查集 \(=\)? 可持久化 \(+\)? 并查集 \(=\) ?可持久化数组 \(+\)? 并查集
"啪"一下就把模板题A了, 很快啊
附上完整的代码：(按秩压缩)
#include
using namespace std;
#define endl '\n'
#define rep(i, a, b) for (int i = (a), i##ss = (b); i <= i##ss; ++i)
#define per(i, a, b) for (int i = (a), i##ss = (b); i >= i##ss; --i)
#define debug(x) cerr << "||debug: " << (#x) << " = " << x << '\n'
typedef double db;
typedef long long ll;
typedef pair pii;
typedef unsigned long long ull;
const db Pi = acos(-1.0);
const db eps = 1e-6;
inline int Get();
const int Maxn = 2e5 + 5;
struct Persistent_Union_And_Find
{
struct Segment_Tree_Node
{
int Son[2];
pii leaf;
};
int Cnt;
Segment_Tree_Node node[8075050];
int Build(int l, int r)
{
int u = ++Cnt;
if (l == r)
node[u].leaf = make_pair(l, 1);
else
{
int mid = l + r >> 1;
node[u].Son[0] = Build(l, mid);
node[u].Son[1] = Build(mid + 1, r);
}
return u;
}
pii Find_Father(int u, int l, int r, int p)
{
if (l == r)
return node[u].leaf;
else
{
int mid = l + r >> 1;
int f = mid < p;
f ? l = mid + 1 : r = mid;
return Find_Father(node[u].Son[f], l, r, p);
}
}
int Edit(int v, int l, int r, int p, pii x)
{
int u = ++Cnt;
node[u] = node[v];
if (l == r)
node[u].leaf = x;
else
{
int mid = l + r >> 1;
int f = mid < p;
f ? l = mid + 1 : r = mid;
node[u].Son[f] = Edit(node[v].Son[f], l, r, p, x);
}
return u;
}
};
int n, m;
int Ans;
int Edition[Maxn];
int ver;
Persistent_Union_And_Find puf;
int main()
{
n = Get(), m = Get();
Edition[0] = puf.Build(1, n);
for (int op, x, y, i = 1; i <= m; i++)
{
op = Get(), x = Get();
if (op == 2)
{
Edition[i] = Edition[x];
continue;
}
y = Get();
Edition[i] = Edition[i - 1];
ver = i;
pii X, Y;
for (X = puf.Find_Father(Edition[i], 1, n, x); X.first != x; X = puf.Find_Father(Edition[i], 1, n, x))
x = X.first;
for (Y = puf.Find_Father(Edition[i], 1, n, y); Y.first != y; Y = puf.Find_Father(Edition[i], 1, n, y))
y = Y.first;
if (op == 1)
{
if (X.second < Y.second)
swap(X, Y);
if (X.second == Y.second)
X.second++;
Edition[i] = puf.Edit(Edition[i], 1, n, X.first, X);
Edition[i] = puf.Edit(Edition[i], 1, n, Y.first, X);
}
else
printf("%d\n", Ans = (X.first == Y.first));
}
return 0;
}
int Get()
{
bool flag = true;
int Rec = 0;
char c;
for (c = getchar(); !isdigit(c) && c != '-'; c = getchar())
;
if (c == '-')
flag = false, c = getchar();
for (; isdigit(c); c = getchar())
Rec = (Rec * 10) - '0' + c;
return flag ? Rec : (-Rec);
}
那么我为什么不写缩路径呢?
其实并不是我没写
#include
using namespace std;
#define endl '\n'
#define rep(i, a, b) for (int i = (a), i##ss = (b); i <= i##ss; ++i)
#define per(i, a, b) for (int i = (a), i##ss = (b); i >= i##ss; --i)
#define debug(x) cerr << "||debug: " << (#x) << " = " << x << '\n'
typedef double db;
typedef long long ll;
typedef pair pii;
typedef unsigned long long ull;
const db Pi = acos(-1.0);
const db eps = 1e-6;
inline int Get();
const int Maxn = 2e5 + 5;
struct Persistent_Union_And_Find
{
struct Segment_Tree_Node
{
int Son[2];
int Father;
};
int Cnt;
Segment_Tree_Node node[10000050];
int Build(int l, int r)
{
int u = ++Cnt;
if (l == r)
node[u].Father = l;
else
{
int mid = l + r >> 1;
node[u].Son[0] = Build(l, mid);
node[u].Son[1] = Build(mid + 1, r);
}
return u;
}
int Find_Father(int u, int l, int r, int p)
{
if (l == r)
return node[u].Father;
else
{
int mid = l + r >> 1;
int f = mid < p;
f ? l = mid + 1 : r = mid;
return Find_Father(node[u].Son[f], l, r, p);
}
}
int Edit(int v, int l, int r, int p, int x)
{
int u = ++Cnt;
node[u] = node[v];
if (l == r)
node[u].Father = x;
else
{
int mid = l + r >> 1;
int f = mid < p;
f ? l = mid + 1 : r = mid;
node[u].Son[f] = Edit(node[v].Son[f], l, r, p, x);
}
return u;
}
};
int n, m;
int Ans;
int Edition[Maxn];
int ver;
Persistent_Union_And_Find puf;
int Find(int x)
{
int fa = puf.Find_Father(Edition[ver], 1, n, x);
if (fa == x)
return fa;
fa = Find(fa);
Edition[ver] = puf.Edit(Edition[ver], 1, n, x, fa);
return fa;
}
int main()
{
n = Get(), m = Get();
Edition[0] = puf.Build(1, n);
for (int op, x, y, i = 1; i <= m; i++)
{
op = Get(), x = Get() ^ Ans;
if (op == 2)
{
Edition[i] = Edition[x];
continue;
}
y = Get() ^ Ans;
Edition[i] = Edition[i - 1];
ver = i;
x = Find(x);
y = Find(y);
if (op == 1)
Edition[i] = puf.Edit(Edition[i], 1, n, x, y);
else
printf("%d\n", Ans = (x == y));
}
return 0;
}
int Get()
{
bool flag = true;
int Rec = 0;
char c;
for (c = getchar(); !isdigit(c) && c != '-'; c = getchar())
;
if (c == '-')
flag = false, c = getchar();
for (; isdigit(c); c = getchar())
Rec = (Rec * 10) - '0' + c;
return flag ? Rec : (-Rec);
}
而是空间复杂度的限制
观察代码可以知道 路径压缩的并查集需要新建多少个版本是不确定的
经过尝试后发现 这道题开不下
显然可以知道,路径压缩加按秩合并的空间复杂度更高, 虽然也写了,就不贴了
可持久化栈
由于栈的操作只跟栈顶元素有关, 所以我们用链表来实现栈的功能
那么
- 压栈: 当前版本号\(->\)?待进栈元素\(->\)上一版本号指向的元素
- 弹栈: 当前版本号\(->\)上一版本号指向的元素
……
什么数据结构不能可持久化?
时间复杂度带有均摊分析的就不能可持久
以替罪羊树为例, 虽然它的插入/删除一个节点的时间复杂度均摊下来最坏是\(logN\)的
但是它的重构一次时间复杂度为 \(O(N)\)
如果我们多次访问重构前的版本,时间复杂度就会被卡成\(O(NM)\)?
同理, 平衡树如Splay,Treep也不能可持久化
那如果我们就要可持久化平衡树呢? 233 Fhq Treap 可以实现可持久