线段树学习笔记下

可持久化线段树

上面两篇是几年前写的，笔者今日才加以整理，如有错误请见谅。

线段树加上版本就是可持久化线段树。

Problem Intro

给定一个数组，只需要单点修改和单点查询，但要维护版本。

具体说，每一次操作可能从任意版本读取，也可以从任意版本修改。

提交地址可见模板题。

Solution

image helper
如图，当插入时可以再拉一条路径作为新的版本，不必再新建一个数组，复杂度 $\times\text{dep})$ 。

然后考虑访问，对于每一个版本考虑只存储其根结点，后面的点使用动态开点即可。

这就是可持久化线段树（主席树）。其实不算太难。

Code

#include <bits/stdc++.h>using namespace std;int n, m, a[26000001];
struct node{int l, r, lp, rp, val;
} tree[26000001];int cnt = 0, tot = 0, ver[26000001];void save_ver(int rt){ver[++tot] = rt;
}
int get_ver(int x){return ver[x];
}int build(int l, int r){int ind = cnt; cnt++;tree[ind].l = l, tree[ind].r = r;if(l == r){tree[ind].val = a[l];return ind;}int mid = (l + r) >> 1;tree[ind].lp = build(l, mid);tree[ind].rp = build(mid + 1, r);return ind;
}
int mod(int x, int y, int k){int ind = cnt; cnt++;tree[ind].l = tree[x].l, tree[ind].r = tree[x].r;if(tree[ind].l == tree[ind].r){tree[ind].val = k;return ind;}int mid = (tree[ind].l + tree[ind].r) >> 1;tree[ind].lp = tree[x].lp, tree[ind].rp = tree[x].rp;if(y <= mid)tree[ind].lp = mod(tree[x].lp, y, k);elsetree[ind].rp = mod(tree[x].rp, y, k);return ind;
}
int query(int x, int y){if(tree[x].l == tree[x].r)return tree[x].val;int mid = (tree[x].l + tree[x].r) >> 1;if(y <= mid)return query(tree[x].lp, y);elsereturn query(tree[x].rp, y);
}
double solve(int testcase, ...){double used_time = clock();scanf("%d%d", &n, &m);for(int i = 1; i <= n; i++){scanf("%d", a + i);}ver[0] = build(1, n);for(int i = 1; i <= m; i++){int v, op, x, y;scanf("%d%d%d", &v, &op, &x);if(op == 1){scanf("%d", &y);save_ver(mod(get_ver(v), x, y));}else{int curr = query(get_ver(v), x);printf("%d\n", curr);save_ver(mod(get_ver(v), x, curr));}}return clock() - used_time;
}signed main(){ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);#ifndef ONLINE_JUDGEprintf("Solved, used time %.0lfms.\n", solve(1, "local"));
#elsesolve(1, ONLINE_JUDGE);	
#endifreturn 0;
}