用途可持久化线段树是很多可持久化数据结构的起点它允许查询修改某一版本的某一值或者查询静态区间第 小。值得一提的是允许访基础实现对于多个版本我们很明显可以对于每一个版本建一个线段树但是这样我们的空间会爆炸故我们考虑让前面的版本对当前版本有一定贡献考虑对于每一个版本有以下两种情况如果不需要修改节点我们就让指针指向上一个版本的这个未修改节点。如果是需要修改节点我们就对其新建一个节点。如图其实现依赖于用结构体维护 ,并且对于一个新节点我们先让其等于原节点并且给其一个新的编号再依次更新下面的节点。代码如下1 2 3 4 5 6struct node{ int val, ls, rs; }nd[N 7]; #define ls(k) nd[k].ls #define rs(k) nd[k].rs int newnode(int p){nd[ tot] nd[p];return tot;}修改操作可见因为每一个要修改的节点需要有一个新的编号所以我们需要让这个应修改节点变为这个编号其实现方法即为在 update 操作中将引入 编号的节点加上址传递即加上取地址符。其他和普通线段树没有什么很大的差异。代码如下1 2 3 4 5 6 7 8 9 10void update(int p, int l, int r, int x, int val) { p newnode(p);//变为新编号 if(l r){nd[p].val val;return ;}//更新值 int mid l r 1; if(x mid) update(ls(p), l, mid, x, val); else update(rs(p), mid 1, r, x, val); //pushup(p); //pushup 操作看题可有可无 }查询操作因为所有版本我们已经处理好了直接查询即可。当然你也可以使用可持久化数组。代码如下1 2 3 4 5 6 7ll query(int p, int l, int r, int x) { if(l r) return nd[p].val; int mid l r 1; if(x mid) return query(ls(p), l, mid, x); else return query(rs(p), mid 1, r, x); }基础实现例题1.P3919 【模板】可持久化线段树 1可持久化数组简要题意维护一个长度为 的数组 进行 次以下操作形如v 1 p c表示把版本 的 改为 。形如v 2 p输出版本 的 。对于每个操作都会生成一个对应的版本。其中 1≤,≤1061≤≤−109≤,≤109。如果当前是第 次操作则 0≤。版本 0 为原始数组。思路按照上面代码和思想模拟即可。1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48#includebits/stdc.h using namespace std; using ll long long; constexpr int N 1e6 66; int root[N], tot; struct Seg_Ment_Tree{ struct node{ int val, ls, rs; }nd[N 7]; #define ls(k) nd[k].ls #define rs(k) nd[k].rs int newnode(int p){nd[ tot] nd[p];return tot;} void update(int p, int l, int r, int x, int val) { p newnode(p); if(l r){nd[p].val val;return ;} int mid l r 1; if(x mid) update(ls(p), l, mid, x, val); else update(rs(p), mid 1, r, x, val); } ll query(int p, int l, int r, int x) { if(l r) return nd[p].val; int mid l r 1; if(x mid) return query(ls(p), l, mid, x); else return query(rs(p), mid 1, r, x); } }seg; int n, m, a; int main() { ios::sync_with_stdio(false);cin.tie(0), cout.tie(0); cin n m; for(int i 1;i n;i ) cin a, seg.update(root[0], 1, n, i, a);//初始化初始版本即原数组 for(int i 1;i m;i ) { int od, v, p, c; cin v od p; root[i] root[v];//当前版本为给定版本 if(od 1) { cin c; seg.update(root[i], 1, n, p, c);//修改 } else cout seg.query(root[i], 1, n, p) \n; } return 0; }2.P1383 高级打字机简要题意开始有一空串要进行 次以下操作形如T x表示在后面加入一字符 。形如U x表示撤销 次除操作三的操作。形如Q x表示查询当前字符串的第 个字符。≤105。思路板子按照模板 1 查询即可注意输入的字符还是数字不然会 WA还有注意分辨一下操作二和操作一都属于修改操作所以需要新建一个版本具体看代码。1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59#includebits/stdc.h using namespace std; using ll long long; constexpr int N 1e5 66; int root[N], tot; struct Seg_Ment_Tree{ struct node{ int val, ls, rs, su; }nd[N 7]; #define ls(k) nd[k].ls #define rs(k) nd[k].rs int newnode(int p){nd[ tot] nd[p];return tot;} void pushup(int p){nd[p].su nd[ls(p)].su nd[rs(p)].su;}//维护字符个数 void update(int p, int l, int r, int x, int val) { p newnode(p); if(l r){nd[p].val val;nd[p].su 1;return ;} int mid l r 1; if(x mid) update(ls(p), l, mid, x, val); else update(rs(p), mid 1, r, x, val); pushup(p); } ll query(int p, int l, int r, int x) { if(l r) return nd[p].val; int mid l r 1; if(x mid) return query(ls(p), l, mid, x); else return query(rs(p), mid 1, r, x); } }seg; int n, m, a, cnt; int main() { ios::sync_with_stdio(false);cin.tie(0), cout.tie(0); cin n; for(int i 1;i n;i ) { char c;cin c; if(c T) { char s;cin s; cnt ;//新建版本 root[cnt] root[cnt - 1];//等于上一个版本 seg.update(root[cnt], 1, 1e5, seg.nd[root[cnt]].su 1, s);//在上一个版本的后面加入一个字符 } else if(c U) { int s;cin s; cnt ;//新建版本 root[cnt] root[cnt - 1 - s];//等于 cnt - s 的但是我们 了所以让 cnt - 1 } else { int s;cin s; cout char(seg.query(root[cnt], 1, 1e5, s)) \n;//直接查询即可 } } return 0; }进阶一点的实现现在我们讨论静态区间第 小。先引入一下例题吧P3834 【模板】可持久化线段树 2简要题意给定一个长度为 的序列 询问 次 中 [,] 区间第 小的数的值。1≤,≤2×1050≤≤1091≤,≤1≤≤−1。可见我们很难在原序列中用原本思想直接在下标 修改因为我们第 小是关系大小而在下标 插入却无法比较大小的。那大小我们怎么处理呢考虑使用权值线段树来处理这样我们就可以处理大小关系。那 的范围太大了怎么办可持久化线段树是自带动态开点性质的我们只需关注题目的空间大小是不是过小了比如 125如果太小了就离散化一下即可。修改对于每一个位置我们考虑建立一个新版本并在新版本所维护的权值线段树上插入它的值。所以修改代码其实是没什么区别的但是 可能重复所以不能直接赋值。考虑我们还需要维护什么以及我们需不需要 pushup。显然的是我们需要查询前面区间的数的个数所以我们需要 pushup 来让父节点维护区间。代码如下1 2 3 4 5 6 7 8 9 10void pushup(int p){nd[p].val nd[ls(p)].val nd[rs(p)].val;} void update(int p, int l, int r, int x, int val) { p newnode(p); if(l r){nd[p].val val;return ;} int mid l r 1; if(x mid) update(ls(p), l, mid, x, val); else update(rs(p), mid 1, r, x, val); pushup(p); }查询但是我们怎么查询的我们考虑对于 [,] 我们现在已经有了对应的版本那一个 [1,−1][1,] 内有的数的个数的差不就是 [,] 中数的个数吗考虑到这个情况也可以推广到其他区间所以我们在查询时传入两个节点每一次判断前面的区间的数是否够 如果不够就在后面的区间里但是此时前面是有贡献的所以注意此时查询的 就要减去前面的数的个数了。注意传入的节点是 −1 和 所对应版本即可。对了此时两个节点要同时跳左右儿子哦。代码如下1 2 3 4 5 6 7 8ll query(int u, int v, int l, int r, int x) { if(l r) return l;//因为我们建的是权值线段树此时 l 就是我们对应的值 int k nd[ls(v)].val - nd[ls(u)].val; int mid l r 1; if(k x) return query(ls(u), ls(v), l, mid, x); else return query(rs(u), rs(v), mid 1, r, x - k); }1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49#includebits/stdc.h using namespace std; using ll long long; constexpr int N 1e6 66; int root[N], tot; struct Seg_Ment_Tree{ struct node{ int val, ls, rs; }nd[N 7]; #define ls(k) nd[k].ls #define rs(k) nd[k].rs int newnode(int p){nd[ tot] nd[p];return tot;} void pushup(int p){nd[p].val nd[ls(p)].val nd[rs(p)].val;} void update(int p, int l, int r, int x, int val) { p newnode(p); if(l r){nd[p].val val;return ;} int mid l r 1; if(x mid) update(ls(p), l, mid, x, val); else update(rs(p), mid 1, r, x, val); pushup(p); } ll query(int u, int v, int l, int r, int x) { if(l r) return l; int k nd[ls(v)].val - nd[ls(u)].val; int mid l r 1; if(k x) return query(ls(u), ls(v), l, mid, x); else return query(rs(u), rs(v), mid 1, r, x - k); } }seg; int n, m, a; int main() { ios::sync_with_stdio(false);cin.tie(0), cout.tie(0); cin n m; for(int i 1;i n;i ) { cin a; root[i] root[i - 1]; seg.update(root[i], 0, 1e9, a, 1); } for(int i 1;i m;i ) { int l, r, k;cin l r k; cout seg.query(root[l - 1], root[r], 0, 1e9, k) \n; } return 0; }例题1.P1533 可怜的狗狗简要题意是和上面一样的不重新打一遍了。数据范围1≤≤3×105,1≤≤5×104,0≤231且 互不相同。其实这个就是模板二注意空间限制比较小离散化一下就可以了。1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54#includebits/stdc.h using namespace std; using ll long long; constexpr int N 3e5 66; int root[N], tot, inf INT_MAX; struct Seg_Ment_Tree{ struct node{ int val, ls, rs; }nd[N 5]; #define ls(k) nd[k].ls #define rs(k) nd[k].rs int newnode(int p){nd[ tot] nd[p];return tot;} void pushup(int p){nd[p].val nd[ls(p)].val nd[rs(p)].val;} void update(int p, int l, int r, int x, int val) { p newnode(p); if(l r){nd[p].val val;return ;} int mid l r 1; if(x mid) update(ls(p), l, mid, x, val); else update(rs(p), mid 1, r, x, val); pushup(p); } int query(int u, int v, int l, int r, int x) { if(l r) return l; int k nd[ls(v)].val - nd[ls(u)].val; int mid l r 1; if(k x) return query(ls(u), ls(v), l, mid, x); else return query(rs(u), rs(v), mid 1, r, x - k); } }seg; int n, m, a[N], b[N]; int main() { ios::sync_with_stdio(false);cin.tie(0), cout.tie(0); cin n m; for(int i 1;i n;i ) { cin a[i];b[i] a[i]; } sort(b 1, b 1 n); for(int i 1;i n;i ) a[i] lower_bound(b 1, b 1 n, a[i]) - b; for(int i 1;i n;i ) { root[i] root[i - 1]; seg.update(root[i], 1, n, a[i], 1); } for(int i 1;i m;i ) { int l, r, k;cin l r k; cout b[seg.query(root[l - 1], root[r], 1, n, k)] \n; } return 0; }2.P3168 [CQOI2015] 任务查询系统简要题意有 个任务其统治区间为 [,]权值为 。询问 次强制在线询问对于 权值最小的 的任务的权值和。1≤,≤1051≤≤≤1≤≤107 为 1 到 的一个排列。这不是逗我呢吗《主席树不是只能单点插入吗怎么还要区间插入等等你别急主席树虽然只能单点插入但是它的版本传递有类似于前缀和的作用所以我们对于 和 1 进行权值线段树但是差分就可以了。注意一个位置的数可以有许多所以注意使用 vector 记录每个数。查询时注意是权值和所以我们要把左区间的贡献也算上。1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62#includebits/stdc.h using namespace std; using ll long long; constexpr int N 1e5 66; struct Persistent_Segment_Tree{ struct node{ ll val, su; int rs, ls; }nd[N 7]; int tot; #define ls(k) nd[k].ls #define rs(k) nd[k].rs #define val(k) nd[k].val #define su(k) nd[k].su void pushup(int p){val(p) val(ls(p)) val(rs(p));su(p) su(ls(p)) su(rs(p));} int newnode(int p){nd[ tot] nd[p];return tot;} void update(int p, int l, int r, ll x, ll val) { p newnode(p); if(l r){val(p) val;su(p) x * val;return ;} int mid l r 1; if(x mid) update(ls(p), l, mid, x, val); else update(rs(p), mid 1, r, x, val); pushup(p); } ll query(int p, int l, int r, ll x) { if(l r) return min(su(p), x * l);//注意可能有多个 l比较一下取最小即可 int mid l r 1; if(x val(ls(p))) return query(ls(p), l, mid, x); else return query(rs(p), mid 1, r, x - val(ls(p))) su(ls(p)); } }seg; ll Abs(ll x){return x 0 ? x : -x;} ll n, m, mx; int root[N]; vectorll v[N]; int main() { ios::sync_with_stdio(false);cin.tie(0), cout.tie(0); cin m n; for(int i 1;i m;i ) { ll x, y, z;cin x y z; v[x].push_back(z), v[y 1].push_back(-z); mx max(mx, z); } for(int i 1;i n;i ) { root[i] root[i - 1]; for(auto p : v[i]) seg.update(root[i], 1, mx, Abs(p), (p 0 ? 1ll : -1ll)); } ll lst 1; for(int i 1;i n;i ) { ll x, a, b, c;cin x a b c; a (lst * a b) % c 1; lst seg.query(root[x], 1, mx, a); cout lst \n; } return 0; }其他可持久化结构1. 可持久化数组非可持久化线段树实现一种可以访问历史版本的数组其实现依赖于每个版本对于其之前版本有一个变量指向对于每次修改我们都找到其对应位置的上一次修改的位置并且在其基础上进行修改。这样我们就不用每一次复制之前的版本以保证了空间复杂度。优点空间复杂度相对可持久化线段树较小好写缺点时间复杂度依赖于修改次数可能会被卡定义写法其实就是定义一个结构体维护前驱当前的值当前的位置用当前版本查询。我们用可持久化数组即可持久化线段树 1 来讲。代码如下1 2 3 4struct Persistent{ int val, i, pre; }; vectorPersistent vl(N);更改如果是加减法那还需要找前驱更改但这里是覆盖直接新建节点覆盖就可以了。代码如下1 2 3 4 5 6 7 8 9 10void change(int v, int p, int c) { now ; /* int s v; while(vl[s].i p s) s vl[s].pre; if(s 0) 如果是加减乘除等的话用得到这里 */ vl[now].val c;vl[now].i p;vl[now].pre v; }查询按照找前驱的思想就可以了生成一个完全相同的就是不更改原节点的值然后指向 就可以了。注意如果没找到就是原数组里的值。代码如下1 2 3 4 5 6 7 8 9 10int query(int v, int p) { now ; int s v; while(vl[s].i ! p s) s vl[s].pre; vl[now].i p;vl[now].pre v; //题目中要求生成一个完全一样的版本 if(s 0) return vl[now].val a[p]; return vl[now].val vl[s].val; }PS其实直接vl[now] vl[v]似乎也可以但是有个点卡这个了所以得用这个写法。1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57#includebits/stdc.h using namespace std; using ll long long; constexpr int N 1e6 66; struct Persistent{ int val, i, pre; }; vectorPersistent vl(N); int n, m, a[N], now; templatetypename T void read(Tx) { char c;int sign 1;x 0; // 判断是否是负数以及去掉前面多余的字符 do { c getchar(); if(c -) sign -1; }while(!isdigit(c)); do { x x * 10 c - 0; c getchar(); }while(isdigit(c)); x * sign; } //a 是原数组因为我的写法没有方法存 a //now 是当前版本 void change(int v, int p, int c) { now ; /* int s v; while(vl[s].i p s) s vl[s].pre; if(s 0) 如果是加的话用得到这里 */ vl[now].val c;vl[now].i p;vl[now].pre v; } int query(int v, int p) { now ; int s v; while(vl[s].i ! p s) s vl[s].pre; vl[now].i p;vl[now].pre v; //题目中要求生成一个完全一样的版本 if(s 0) return vl[now].val a[p]; return vl[now].val vl[s].val; } int main() { ios::sync_with_stdio(false);cin.tie(0), cout.tie(0); read(n), read(m); for(int i 1;i n;i ) read(a[i]); for(int i 1;i m;i ) { int v, od, p, c; read(v), read(od), read(p); if(od 1) { read(c); change(v, p, c); } else cout query(v, p) \n; } return 0; }2. 可持久化并查集它其实就是基于可持久化线段树维护的并查集每个节点的 这样就可以保证其可持久化。而其唯一一个区别是我们不可以用路径压缩因为其的时间复杂度是均摊单次 (()) 的。这就导致可能出题人出个卡路径压缩的数据给我们单次操作卡到 () 那不炸了吗。故我们需要一个严格 (log) 的优化方式即按秩合并。按秩合并有多种比如按深度按子树大小还有随机化会被卡。注意此时深度表示的是整棵树的最深节点的深度。其实现就是把深度或者子树大小小的并查集的父亲设为大的并查集。前面两种的时间复杂度为严格 (log) 但是随机化是可能退化到 (2) 的具体证明可以参考可持久化并查集的题解这里不过多赘述了。那我们在每个版本不仅要维护一个 还要维护一个 子树大小 或者 深度但对于每个版本我们都可以同时更新这几个建两棵可持久化线段树即可。于是我们的find函数就变为了1 2 3 4 5 6int find(int x) { while(fa.query(fa.root[now], 1, n, x) ! x) x fa.query(fa.root[now], 1, n, x); //在当前的版本查找到一个并查集的根暴力跳即可 return x; }merge就变为了1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17void merge(int x, int y) { x find(x), y find(y);//找根 if(x y) return ; int X siz.query(siz.root[now], 1, n, x), Y siz.query(siz.root[now], 1, n, y); //我写的是子树大小的查询当前版本以 x 和 y 为根的子树大小 if(X Y)//小的合并到大的 { fa.update(fa.root[now], 1, n, x, y); siz.update(siz.root[now], 1, n, y, X Y); } else { fa.update(fa.root[now], 1, n, y, x); siz.update(siz.root[now], 1, n, x, X Y); } }对于每一个新版本我们注意继承上一个版本如果有回溯版本就再另外赋值成那个版本就可以了。1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77#includebits/stdc.h using namespace std; using ll long long; constexpr int N 2e5 66; struct segmenttree{ int root[N]; struct node{ int val, ls, rs; }nd[N 7]; #define val(k) nd[k].val #define ls(k) nd[k].ls #define rs(k) nd[k].rs int tot 0; int newnode(int p){nd[ tot] nd[p];return tot;} void build(int p, int l, int r, int a[]) { p tot; if(l r) {val(p) a[l];return ;} int mid l r 1; build(ls(p), l, mid, a); build(rs(p), mid 1, r, a); } void update(int p, int l, int r, int x, int val) { p newnode(p); if(l r) {val(p) val;return ;} int mid l r 1; if(x mid) update(ls(p), l, mid, x, val); else update(rs(p), mid 1, r, x, val); } int query(int p, int l, int r, int x) { if(l r) return val(p); int mid l r 1; if(x mid) return query(ls(p), l, mid, x); else return query(rs(p), mid 1, r, x); } }fa, siz; int now; int n, m; int find(int x) { while(fa.query(fa.root[now], 1, n, x) ! x) x fa.query(fa.root[now], 1, n, x); return x; } void merge(int x, int y) { x find(x), y find(y); if(x y) return ; int X siz.query(siz.root[now], 1, n, x), Y siz.query(siz.root[now], 1, n, y); if(X Y) { fa.update(fa.root[now], 1, n, x, y); siz.update(siz.root[now], 1, n, y, X Y); } else { fa.update(fa.root[now], 1, n, y, x); siz.update(siz.root[now], 1, n, x, X Y); } } int main() { ios::sync_with_stdio(false);cin.tie(0), cout.tie(0); cin n m; for(int i 1;i n;i ) fa.update(fa.root[0], 1, n, i, i), siz.update(siz.root[0], 1, n, i, 1);//初始化 while(m --) { now ; fa.root[now] fa.root[now - 1], siz.root[now] siz.root[now - 1];//继承上一个版本 int op, x, y;cin op; if(op 1) cin x y, merge(x, y); else if(op 3) cin x y, cout (find(x) find(y)) \n; else cin x, fa.root[now] fa.root[x], siz.root[now] siz.root[x]; } return 0; }
可持久化线段树/主席树 学习笔记
用途可持久化线段树是很多可持久化数据结构的起点它允许查询修改某一版本的某一值或者查询静态区间第 小。值得一提的是允许访基础实现对于多个版本我们很明显可以对于每一个版本建一个线段树但是这样我们的空间会爆炸故我们考虑让前面的版本对当前版本有一定贡献考虑对于每一个版本有以下两种情况如果不需要修改节点我们就让指针指向上一个版本的这个未修改节点。如果是需要修改节点我们就对其新建一个节点。如图其实现依赖于用结构体维护 ,并且对于一个新节点我们先让其等于原节点并且给其一个新的编号再依次更新下面的节点。代码如下1 2 3 4 5 6struct node{ int val, ls, rs; }nd[N 7]; #define ls(k) nd[k].ls #define rs(k) nd[k].rs int newnode(int p){nd[ tot] nd[p];return tot;}修改操作可见因为每一个要修改的节点需要有一个新的编号所以我们需要让这个应修改节点变为这个编号其实现方法即为在 update 操作中将引入 编号的节点加上址传递即加上取地址符。其他和普通线段树没有什么很大的差异。代码如下1 2 3 4 5 6 7 8 9 10void update(int p, int l, int r, int x, int val) { p newnode(p);//变为新编号 if(l r){nd[p].val val;return ;}//更新值 int mid l r 1; if(x mid) update(ls(p), l, mid, x, val); else update(rs(p), mid 1, r, x, val); //pushup(p); //pushup 操作看题可有可无 }查询操作因为所有版本我们已经处理好了直接查询即可。当然你也可以使用可持久化数组。代码如下1 2 3 4 5 6 7ll query(int p, int l, int r, int x) { if(l r) return nd[p].val; int mid l r 1; if(x mid) return query(ls(p), l, mid, x); else return query(rs(p), mid 1, r, x); }基础实现例题1.P3919 【模板】可持久化线段树 1可持久化数组简要题意维护一个长度为 的数组 进行 次以下操作形如v 1 p c表示把版本 的 改为 。形如v 2 p输出版本 的 。对于每个操作都会生成一个对应的版本。其中 1≤,≤1061≤≤−109≤,≤109。如果当前是第 次操作则 0≤。版本 0 为原始数组。思路按照上面代码和思想模拟即可。1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48#includebits/stdc.h using namespace std; using ll long long; constexpr int N 1e6 66; int root[N], tot; struct Seg_Ment_Tree{ struct node{ int val, ls, rs; }nd[N 7]; #define ls(k) nd[k].ls #define rs(k) nd[k].rs int newnode(int p){nd[ tot] nd[p];return tot;} void update(int p, int l, int r, int x, int val) { p newnode(p); if(l r){nd[p].val val;return ;} int mid l r 1; if(x mid) update(ls(p), l, mid, x, val); else update(rs(p), mid 1, r, x, val); } ll query(int p, int l, int r, int x) { if(l r) return nd[p].val; int mid l r 1; if(x mid) return query(ls(p), l, mid, x); else return query(rs(p), mid 1, r, x); } }seg; int n, m, a; int main() { ios::sync_with_stdio(false);cin.tie(0), cout.tie(0); cin n m; for(int i 1;i n;i ) cin a, seg.update(root[0], 1, n, i, a);//初始化初始版本即原数组 for(int i 1;i m;i ) { int od, v, p, c; cin v od p; root[i] root[v];//当前版本为给定版本 if(od 1) { cin c; seg.update(root[i], 1, n, p, c);//修改 } else cout seg.query(root[i], 1, n, p) \n; } return 0; }2.P1383 高级打字机简要题意开始有一空串要进行 次以下操作形如T x表示在后面加入一字符 。形如U x表示撤销 次除操作三的操作。形如Q x表示查询当前字符串的第 个字符。≤105。思路板子按照模板 1 查询即可注意输入的字符还是数字不然会 WA还有注意分辨一下操作二和操作一都属于修改操作所以需要新建一个版本具体看代码。1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59#includebits/stdc.h using namespace std; using ll long long; constexpr int N 1e5 66; int root[N], tot; struct Seg_Ment_Tree{ struct node{ int val, ls, rs, su; }nd[N 7]; #define ls(k) nd[k].ls #define rs(k) nd[k].rs int newnode(int p){nd[ tot] nd[p];return tot;} void pushup(int p){nd[p].su nd[ls(p)].su nd[rs(p)].su;}//维护字符个数 void update(int p, int l, int r, int x, int val) { p newnode(p); if(l r){nd[p].val val;nd[p].su 1;return ;} int mid l r 1; if(x mid) update(ls(p), l, mid, x, val); else update(rs(p), mid 1, r, x, val); pushup(p); } ll query(int p, int l, int r, int x) { if(l r) return nd[p].val; int mid l r 1; if(x mid) return query(ls(p), l, mid, x); else return query(rs(p), mid 1, r, x); } }seg; int n, m, a, cnt; int main() { ios::sync_with_stdio(false);cin.tie(0), cout.tie(0); cin n; for(int i 1;i n;i ) { char c;cin c; if(c T) { char s;cin s; cnt ;//新建版本 root[cnt] root[cnt - 1];//等于上一个版本 seg.update(root[cnt], 1, 1e5, seg.nd[root[cnt]].su 1, s);//在上一个版本的后面加入一个字符 } else if(c U) { int s;cin s; cnt ;//新建版本 root[cnt] root[cnt - 1 - s];//等于 cnt - s 的但是我们 了所以让 cnt - 1 } else { int s;cin s; cout char(seg.query(root[cnt], 1, 1e5, s)) \n;//直接查询即可 } } return 0; }进阶一点的实现现在我们讨论静态区间第 小。先引入一下例题吧P3834 【模板】可持久化线段树 2简要题意给定一个长度为 的序列 询问 次 中 [,] 区间第 小的数的值。1≤,≤2×1050≤≤1091≤,≤1≤≤−1。可见我们很难在原序列中用原本思想直接在下标 修改因为我们第 小是关系大小而在下标 插入却无法比较大小的。那大小我们怎么处理呢考虑使用权值线段树来处理这样我们就可以处理大小关系。那 的范围太大了怎么办可持久化线段树是自带动态开点性质的我们只需关注题目的空间大小是不是过小了比如 125如果太小了就离散化一下即可。修改对于每一个位置我们考虑建立一个新版本并在新版本所维护的权值线段树上插入它的值。所以修改代码其实是没什么区别的但是 可能重复所以不能直接赋值。考虑我们还需要维护什么以及我们需不需要 pushup。显然的是我们需要查询前面区间的数的个数所以我们需要 pushup 来让父节点维护区间。代码如下1 2 3 4 5 6 7 8 9 10void pushup(int p){nd[p].val nd[ls(p)].val nd[rs(p)].val;} void update(int p, int l, int r, int x, int val) { p newnode(p); if(l r){nd[p].val val;return ;} int mid l r 1; if(x mid) update(ls(p), l, mid, x, val); else update(rs(p), mid 1, r, x, val); pushup(p); }查询但是我们怎么查询的我们考虑对于 [,] 我们现在已经有了对应的版本那一个 [1,−1][1,] 内有的数的个数的差不就是 [,] 中数的个数吗考虑到这个情况也可以推广到其他区间所以我们在查询时传入两个节点每一次判断前面的区间的数是否够 如果不够就在后面的区间里但是此时前面是有贡献的所以注意此时查询的 就要减去前面的数的个数了。注意传入的节点是 −1 和 所对应版本即可。对了此时两个节点要同时跳左右儿子哦。代码如下1 2 3 4 5 6 7 8ll query(int u, int v, int l, int r, int x) { if(l r) return l;//因为我们建的是权值线段树此时 l 就是我们对应的值 int k nd[ls(v)].val - nd[ls(u)].val; int mid l r 1; if(k x) return query(ls(u), ls(v), l, mid, x); else return query(rs(u), rs(v), mid 1, r, x - k); }1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49#includebits/stdc.h using namespace std; using ll long long; constexpr int N 1e6 66; int root[N], tot; struct Seg_Ment_Tree{ struct node{ int val, ls, rs; }nd[N 7]; #define ls(k) nd[k].ls #define rs(k) nd[k].rs int newnode(int p){nd[ tot] nd[p];return tot;} void pushup(int p){nd[p].val nd[ls(p)].val nd[rs(p)].val;} void update(int p, int l, int r, int x, int val) { p newnode(p); if(l r){nd[p].val val;return ;} int mid l r 1; if(x mid) update(ls(p), l, mid, x, val); else update(rs(p), mid 1, r, x, val); pushup(p); } ll query(int u, int v, int l, int r, int x) { if(l r) return l; int k nd[ls(v)].val - nd[ls(u)].val; int mid l r 1; if(k x) return query(ls(u), ls(v), l, mid, x); else return query(rs(u), rs(v), mid 1, r, x - k); } }seg; int n, m, a; int main() { ios::sync_with_stdio(false);cin.tie(0), cout.tie(0); cin n m; for(int i 1;i n;i ) { cin a; root[i] root[i - 1]; seg.update(root[i], 0, 1e9, a, 1); } for(int i 1;i m;i ) { int l, r, k;cin l r k; cout seg.query(root[l - 1], root[r], 0, 1e9, k) \n; } return 0; }例题1.P1533 可怜的狗狗简要题意是和上面一样的不重新打一遍了。数据范围1≤≤3×105,1≤≤5×104,0≤231且 互不相同。其实这个就是模板二注意空间限制比较小离散化一下就可以了。1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54#includebits/stdc.h using namespace std; using ll long long; constexpr int N 3e5 66; int root[N], tot, inf INT_MAX; struct Seg_Ment_Tree{ struct node{ int val, ls, rs; }nd[N 5]; #define ls(k) nd[k].ls #define rs(k) nd[k].rs int newnode(int p){nd[ tot] nd[p];return tot;} void pushup(int p){nd[p].val nd[ls(p)].val nd[rs(p)].val;} void update(int p, int l, int r, int x, int val) { p newnode(p); if(l r){nd[p].val val;return ;} int mid l r 1; if(x mid) update(ls(p), l, mid, x, val); else update(rs(p), mid 1, r, x, val); pushup(p); } int query(int u, int v, int l, int r, int x) { if(l r) return l; int k nd[ls(v)].val - nd[ls(u)].val; int mid l r 1; if(k x) return query(ls(u), ls(v), l, mid, x); else return query(rs(u), rs(v), mid 1, r, x - k); } }seg; int n, m, a[N], b[N]; int main() { ios::sync_with_stdio(false);cin.tie(0), cout.tie(0); cin n m; for(int i 1;i n;i ) { cin a[i];b[i] a[i]; } sort(b 1, b 1 n); for(int i 1;i n;i ) a[i] lower_bound(b 1, b 1 n, a[i]) - b; for(int i 1;i n;i ) { root[i] root[i - 1]; seg.update(root[i], 1, n, a[i], 1); } for(int i 1;i m;i ) { int l, r, k;cin l r k; cout b[seg.query(root[l - 1], root[r], 1, n, k)] \n; } return 0; }2.P3168 [CQOI2015] 任务查询系统简要题意有 个任务其统治区间为 [,]权值为 。询问 次强制在线询问对于 权值最小的 的任务的权值和。1≤,≤1051≤≤≤1≤≤107 为 1 到 的一个排列。这不是逗我呢吗《主席树不是只能单点插入吗怎么还要区间插入等等你别急主席树虽然只能单点插入但是它的版本传递有类似于前缀和的作用所以我们对于 和 1 进行权值线段树但是差分就可以了。注意一个位置的数可以有许多所以注意使用 vector 记录每个数。查询时注意是权值和所以我们要把左区间的贡献也算上。1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62#includebits/stdc.h using namespace std; using ll long long; constexpr int N 1e5 66; struct Persistent_Segment_Tree{ struct node{ ll val, su; int rs, ls; }nd[N 7]; int tot; #define ls(k) nd[k].ls #define rs(k) nd[k].rs #define val(k) nd[k].val #define su(k) nd[k].su void pushup(int p){val(p) val(ls(p)) val(rs(p));su(p) su(ls(p)) su(rs(p));} int newnode(int p){nd[ tot] nd[p];return tot;} void update(int p, int l, int r, ll x, ll val) { p newnode(p); if(l r){val(p) val;su(p) x * val;return ;} int mid l r 1; if(x mid) update(ls(p), l, mid, x, val); else update(rs(p), mid 1, r, x, val); pushup(p); } ll query(int p, int l, int r, ll x) { if(l r) return min(su(p), x * l);//注意可能有多个 l比较一下取最小即可 int mid l r 1; if(x val(ls(p))) return query(ls(p), l, mid, x); else return query(rs(p), mid 1, r, x - val(ls(p))) su(ls(p)); } }seg; ll Abs(ll x){return x 0 ? x : -x;} ll n, m, mx; int root[N]; vectorll v[N]; int main() { ios::sync_with_stdio(false);cin.tie(0), cout.tie(0); cin m n; for(int i 1;i m;i ) { ll x, y, z;cin x y z; v[x].push_back(z), v[y 1].push_back(-z); mx max(mx, z); } for(int i 1;i n;i ) { root[i] root[i - 1]; for(auto p : v[i]) seg.update(root[i], 1, mx, Abs(p), (p 0 ? 1ll : -1ll)); } ll lst 1; for(int i 1;i n;i ) { ll x, a, b, c;cin x a b c; a (lst * a b) % c 1; lst seg.query(root[x], 1, mx, a); cout lst \n; } return 0; }其他可持久化结构1. 可持久化数组非可持久化线段树实现一种可以访问历史版本的数组其实现依赖于每个版本对于其之前版本有一个变量指向对于每次修改我们都找到其对应位置的上一次修改的位置并且在其基础上进行修改。这样我们就不用每一次复制之前的版本以保证了空间复杂度。优点空间复杂度相对可持久化线段树较小好写缺点时间复杂度依赖于修改次数可能会被卡定义写法其实就是定义一个结构体维护前驱当前的值当前的位置用当前版本查询。我们用可持久化数组即可持久化线段树 1 来讲。代码如下1 2 3 4struct Persistent{ int val, i, pre; }; vectorPersistent vl(N);更改如果是加减法那还需要找前驱更改但这里是覆盖直接新建节点覆盖就可以了。代码如下1 2 3 4 5 6 7 8 9 10void change(int v, int p, int c) { now ; /* int s v; while(vl[s].i p s) s vl[s].pre; if(s 0) 如果是加减乘除等的话用得到这里 */ vl[now].val c;vl[now].i p;vl[now].pre v; }查询按照找前驱的思想就可以了生成一个完全相同的就是不更改原节点的值然后指向 就可以了。注意如果没找到就是原数组里的值。代码如下1 2 3 4 5 6 7 8 9 10int query(int v, int p) { now ; int s v; while(vl[s].i ! p s) s vl[s].pre; vl[now].i p;vl[now].pre v; //题目中要求生成一个完全一样的版本 if(s 0) return vl[now].val a[p]; return vl[now].val vl[s].val; }PS其实直接vl[now] vl[v]似乎也可以但是有个点卡这个了所以得用这个写法。1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57#includebits/stdc.h using namespace std; using ll long long; constexpr int N 1e6 66; struct Persistent{ int val, i, pre; }; vectorPersistent vl(N); int n, m, a[N], now; templatetypename T void read(Tx) { char c;int sign 1;x 0; // 判断是否是负数以及去掉前面多余的字符 do { c getchar(); if(c -) sign -1; }while(!isdigit(c)); do { x x * 10 c - 0; c getchar(); }while(isdigit(c)); x * sign; } //a 是原数组因为我的写法没有方法存 a //now 是当前版本 void change(int v, int p, int c) { now ; /* int s v; while(vl[s].i p s) s vl[s].pre; if(s 0) 如果是加的话用得到这里 */ vl[now].val c;vl[now].i p;vl[now].pre v; } int query(int v, int p) { now ; int s v; while(vl[s].i ! p s) s vl[s].pre; vl[now].i p;vl[now].pre v; //题目中要求生成一个完全一样的版本 if(s 0) return vl[now].val a[p]; return vl[now].val vl[s].val; } int main() { ios::sync_with_stdio(false);cin.tie(0), cout.tie(0); read(n), read(m); for(int i 1;i n;i ) read(a[i]); for(int i 1;i m;i ) { int v, od, p, c; read(v), read(od), read(p); if(od 1) { read(c); change(v, p, c); } else cout query(v, p) \n; } return 0; }2. 可持久化并查集它其实就是基于可持久化线段树维护的并查集每个节点的 这样就可以保证其可持久化。而其唯一一个区别是我们不可以用路径压缩因为其的时间复杂度是均摊单次 (()) 的。这就导致可能出题人出个卡路径压缩的数据给我们单次操作卡到 () 那不炸了吗。故我们需要一个严格 (log) 的优化方式即按秩合并。按秩合并有多种比如按深度按子树大小还有随机化会被卡。注意此时深度表示的是整棵树的最深节点的深度。其实现就是把深度或者子树大小小的并查集的父亲设为大的并查集。前面两种的时间复杂度为严格 (log) 但是随机化是可能退化到 (2) 的具体证明可以参考可持久化并查集的题解这里不过多赘述了。那我们在每个版本不仅要维护一个 还要维护一个 子树大小 或者 深度但对于每个版本我们都可以同时更新这几个建两棵可持久化线段树即可。于是我们的find函数就变为了1 2 3 4 5 6int find(int x) { while(fa.query(fa.root[now], 1, n, x) ! x) x fa.query(fa.root[now], 1, n, x); //在当前的版本查找到一个并查集的根暴力跳即可 return x; }merge就变为了1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17void merge(int x, int y) { x find(x), y find(y);//找根 if(x y) return ; int X siz.query(siz.root[now], 1, n, x), Y siz.query(siz.root[now], 1, n, y); //我写的是子树大小的查询当前版本以 x 和 y 为根的子树大小 if(X Y)//小的合并到大的 { fa.update(fa.root[now], 1, n, x, y); siz.update(siz.root[now], 1, n, y, X Y); } else { fa.update(fa.root[now], 1, n, y, x); siz.update(siz.root[now], 1, n, x, X Y); } }对于每一个新版本我们注意继承上一个版本如果有回溯版本就再另外赋值成那个版本就可以了。1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77#includebits/stdc.h using namespace std; using ll long long; constexpr int N 2e5 66; struct segmenttree{ int root[N]; struct node{ int val, ls, rs; }nd[N 7]; #define val(k) nd[k].val #define ls(k) nd[k].ls #define rs(k) nd[k].rs int tot 0; int newnode(int p){nd[ tot] nd[p];return tot;} void build(int p, int l, int r, int a[]) { p tot; if(l r) {val(p) a[l];return ;} int mid l r 1; build(ls(p), l, mid, a); build(rs(p), mid 1, r, a); } void update(int p, int l, int r, int x, int val) { p newnode(p); if(l r) {val(p) val;return ;} int mid l r 1; if(x mid) update(ls(p), l, mid, x, val); else update(rs(p), mid 1, r, x, val); } int query(int p, int l, int r, int x) { if(l r) return val(p); int mid l r 1; if(x mid) return query(ls(p), l, mid, x); else return query(rs(p), mid 1, r, x); } }fa, siz; int now; int n, m; int find(int x) { while(fa.query(fa.root[now], 1, n, x) ! x) x fa.query(fa.root[now], 1, n, x); return x; } void merge(int x, int y) { x find(x), y find(y); if(x y) return ; int X siz.query(siz.root[now], 1, n, x), Y siz.query(siz.root[now], 1, n, y); if(X Y) { fa.update(fa.root[now], 1, n, x, y); siz.update(siz.root[now], 1, n, y, X Y); } else { fa.update(fa.root[now], 1, n, y, x); siz.update(siz.root[now], 1, n, x, X Y); } } int main() { ios::sync_with_stdio(false);cin.tie(0), cout.tie(0); cin n m; for(int i 1;i n;i ) fa.update(fa.root[0], 1, n, i, i), siz.update(siz.root[0], 1, n, i, 1);//初始化 while(m --) { now ; fa.root[now] fa.root[now - 1], siz.root[now] siz.root[now - 1];//继承上一个版本 int op, x, y;cin op; if(op 1) cin x y, merge(x, y); else if(op 3) cin x y, cout (find(x) find(y)) \n; else cin x, fa.root[now] fa.root[x], siz.root[now] siz.root[x]; } return 0; }
