初次接触主席树，还没有找到很好的板子，就自己先瞎写了一段，常数有点大。那就先说两句主席树的思想。
主席树
主席树，又称函数式线段树，支持访问线段树的历史版本，可以有自定义个版本的完整的线段树，主席树利用这些线段树之间的共同数据来减少空间消耗和时间访问。
主席树本质上就是线段树，它不仅能够访问当前版本线段树的状态，同时还能回去访问某个历史版本的状态，并在其上做出改变，还能再次保存改变后的状态，实现可持久化。
因为每次修改某个历史版本的单点值，只需改变从该叶子结点到根节点的logn个结点的值，所以也就只需要新建logn个结点就可创建一个新的线段树。
为了节省空间，数据池结构体结点里不再保存区间信息[l, r]，而是作为递归参数传递(MLE了好久)
至于数据池的大小，是maxn的20倍左右即可(logn倍)。
当前使用的主席树板子里的变量：
tree[]: 结点(结构体)数组，数据池，使用新结点时从这里面拿，这里面的结点可能是根节点，也可能是叶子节点等各种结点。
root[i]: 版本i的树根在tree[]中的位置(下标)。
结点里只保存其左右孩子的位置和区间信息，没有父亲结点，因为一个结点可能有多个父亲结点，是多个线段树版本的一部分。
P3919 【模板】可持久化线段树
先看一道最最基础的板子。首先在初始数组上建立版本编号为0的线段树，此后每一次改变值，建立新的线段树，都需要从根节点开始到叶子结点共新建logn(树高)个结点。访问线段树时就是用普通线段树的访问方式即可，只需要有一个树根就可访问该线段树，访问和更新叶子节点值都是从上往下访问。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
struct tree{
int left, right, val; //左右孩子
int l, r; //区间
}tree[maxn*15];
int n, m;
int top, cur; //top表示tree结点的使用情况，cur表示当前线段树版本的编号
int nums[maxn];
int root[maxn];
inline int build(int l, int r){ //区间[l, r] 创建结点来存储区间[l,r]同时返回该结点的下标
int cur = ++top;
tree[cur].l = l, tree[cur].r = r;
if (l==r){
tree[cur].val = nums[l];
return cur;
}
int mid = (l+r)>>1;
tree[cur].left = build(l, mid);
tree[cur].right = build(mid+1, r);
return cur;
}
inline int add(int src, int target_idx, int val){ //在src结点里寻找target并修改值为val，同时返回结点下标
int cur = ++top;
tree[cur].l = tree[src].l, tree[cur].r = tree[src].r;
if (tree[src].l == tree[src].r){
tree[cur].val = val;
return cur;
}
if (target_idx <= tree[tree[src].left].r){
tree[cur].left = add(tree[src].left, target_idx, val);
tree[cur].right = tree[src].right;
}else{
tree[cur].right = add(tree[src].right, target_idx, val);
tree[cur].left = tree[src].left;
}
return cur;
}
inline int search(int src, int target_idx){
if (tree[src].l == tree[src].r){
return tree[src].val;
}
if (target_idx <= tree[tree[src].left].r) return search(tree[src].left, target_idx);
else return search(tree[src].right, target_idx);
}
inline 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*10 + ch-'0';
ch = getchar();
}
return x*f;
}
int main(){
int edi, opt, loc, val;
cur = top = 0;
//scanf ("%d %d", &n, &m);
n = read(), m = read();
for (int i=1; i<=n; i++) nums[i] = read();//scanf ("%d", nums+i);
root[cur++] = build(1, n);
for (int i=1; i<=m; i++){
//scanf ("%d %d", &edi, &opt);
edi = read(), opt = read();
if (opt&1){
//scanf ("%d %d", &loc, &val);
loc = read(), val = read();
root[cur++] = add(root[edi], loc, val);
}else{
//scanf ("%d", &loc);
loc = read();
root[cur++] = root[edi];
printf ("%d\n", search(root[edi], loc));
}
}
return 0;
}P3834 【模板】可持久化线段树 2（主席树）
第k小数字
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 2e5+5;
struct num{
int val, idx;
int ser;
}nums[maxn];
int n, m;
int ser[maxn];
struct tree{
int left, right, val; //val为区间内值的个数
int l, r;
}tree[maxn*30]; //数据池
int top; //数据池的使用信息
int root[maxn]; //存储各个版本的根的位置(数据池中的下标)
inline int build(int l, int r){ //建立初始空树
int tmp = ++top;
tree[tmp].l = l, tree[tmp].r = r;
if (l==r){
tree[tmp].val = 0;
return tmp;
}
int mid = (l+r)>>1;
tree[tmp].left = build(l, mid);
tree[tmp].right = build(mid+1, r);
tree[tmp].val = 0;
return tmp;
}
inline int add(int src, int target_idx){ //在src版本的线段树上，更改target_idx处的值为val，返回新树根
int tmp = ++top;
tree[tmp].l = tree[src].l, tree[tmp].r = tree[src].r;
if (tree[src].l == tree[src].r){
tree[tmp].val = tree[src].val + 1;
return tmp;
}
;
if (target_idx <= tree[tree[src].left].r){
tree[tmp].left = add(tree[src].left, target_idx);
tree[tmp].right = tree[src].right;
}else{
tree[tmp].right = add(tree[src].right, target_idx);
tree[tmp].left = tree[src].left;
}
tree[tmp].val = tree[tree[tmp].left].val + tree[tree[tmp].right].val;
return tmp;
}
inline int search(int rt1, int rt2, int k){
if (tree[rt2].l == tree[rt2].r){
return tree[rt2].l;
}
int l = tree[tree[rt2].left].val-tree[tree[rt1].left].val, r = tree[tree[rt2].right].val-tree[tree[rt1].right].val;
if (l >= k) return search(tree[rt1].left, tree[rt2].left, k);
return search(tree[rt1].right, tree[rt2].right, k-l);
}
inline bool cmp1(struct num a, struct num b){
if (a.val != b.val) return a.val < b.val;
return a.idx < b.idx;
}
inline bool cmp2(struct num a, struct num b){
return a.idx < b.idx;
}
inline 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*10 + ch-'0';
ch = getchar();
}
return x*f;
}
int main(){
int t, l, r, k;
t = 1;
while (t--){
top = 0;
n = read(), m = read();
for (int i=1; i<=n; i++){
nums[i].val = read();
nums[i].idx = i;
}
sort(nums+1, nums+n+1, cmp1);
for (int i=1; i<=n; i++){
nums[i].ser = i;
ser[i] = nums[i].val;
}
sort(nums+1, nums+n+1, cmp2);
root[0] = build(1, n);
for (int i=1; i<=n; i++){
root[i] = add(root[i-1], nums[i].ser);
}
for (int i=1; i<=m; i++){
l=read(), r=read(), k=read(); //scanf ("%d %d %d", &l, &r, &k);
printf ("%d\n", ser[search(root[l-1], root[r], k)]);
}
}
return 0;
}Kth number
现在正式说一下这题是如何用到主席树的。
我们先把原数组离散化，因为我们只需要用到原来数组中元素之间的大小关系，和数值其实没太大关系，那我们可以先把它排个序，从小到大，然后编个号1,,n，用编号来表示每个数，这样就把数值比较离散的数组变成数值都在n内的数了，编号大的数值就大，编号小的数值就小。
每个版本的线段树中，对于表示区间[l, r]的结点，其权值为大小编号在[l,r]内的数的个数。而不是原数组中的位置区间[l,r]。那么两个线段树内的权值相减，就是这两个线段树对应位置区间内的所有数构成的线段树了。我们要找从小到大查询第k小数即可。
回到原来的序列，把数组内的数一次插入主席树中，第i个数所在的就是第i个版本的线段树，插入的权值是：这个元素的编号所在位置+1。
注意结构体内去掉区间信息，只保存左右孩子和权值
build(): 建立初始线段树，返回树根下标
add(): 新加一个版本，在原来某个版本的基础上修改，返回树根下标
search(): 在某个版本上查找
三个函数都把区间信息[l, r]作为参数传递。
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 1e5+5;
struct num{
int val, idx;
int ser;
}nums[maxn];
int n, m;
int ser[maxn];
struct tree{
int left, right, val; //val为区间内值的个数
//int l, r;
}tree[maxn*30]; //数据池
int top; //数据池的使用信息
int root[maxn]; //存储各个版本的根的位置(数据池中的下标)
inline int build(int l, int r){ //建立初始空树
int tmp = ++top;
//tree[tmp].l = l, tree[tmp].r = r;
if (l==r){
tree[tmp].val = 0;
return tmp;
}
int mid = (l+r)>>1;
tree[tmp].left = build(l, mid);
tree[tmp].right = build(mid+1, r);
tree[tmp].val = 0;
return tmp;
}
inline int add(int src, int l, int r, int target_idx){ //在src版本的线段树上，更改target_idx处的值, 返回新树根
int tmp = ++top;
if (l==r){
tree[tmp].val = tree[src].val + 1;
return tmp;
}
int mid = (l+r)>>1;
if (target_idx <= mid){
tree[tmp].left = add(tree[src].left, l, mid, target_idx);
tree[tmp].right = tree[src].right;
}else{
tree[tmp].right = add(tree[src].right, mid+1, r, target_idx);
tree[tmp].left = tree[src].left;
}
tree[tmp].val = tree[tree[tmp].left].val + tree[tree[tmp].right].val;
return tmp;
}
inline int search(int rt1, int rt2, int l, int r, int k){
if (l==r){
return l;
}
int x = tree[tree[rt2].left].val-tree[tree[rt1].left].val;
int y = tree[tree[rt2].right].val-tree[tree[rt1].right].val;
int mid = (l+r)>>1;
if (x >= k) return search(tree[rt1].left, tree[rt2].left, l, mid, k);
return search(tree[rt1].right, tree[rt2].right, mid+1, r, k-x);
}
inline bool cmp1(struct num a, struct num b){
if (a.val != b.val) return a.val < b.val;
return a.idx < b.idx;
}
inline bool cmp2(struct num a, struct num b){
return a.idx < b.idx;
}
inline 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*10 + ch-'0';
ch = getchar();
}
return x*f;
}
int main(){
int t, l, r, k;
t = read();
while (t--){
top = 0;
n = read(), m = read();
for (int i=1; i<=n; i++){
nums[i].val = read();
nums[i].idx = i;
}
sort(nums+1, nums+n+1, cmp1);
for (int i=1; i<=n; i++){
nums[i].ser = i;
ser[i] = nums[i].val;
}
sort(nums+1, nums+n+1, cmp2);
root[0] = build(1, n);
for (int i=1; i<=n; i++){
root[i] = add(root[i-1], 1, n, nums[i].ser);
}
for (int i=1; i<=m; i++){
l=read(), r=read(), k=read();
printf ("%d\n", ser[search(root[l-1], root[r], 1, n, k)]);
}
}
return 0;
}
//////////////////////////////////////////////////////////////////////////
最后在说一下成功提交hdu的技巧，至于为什么我总是能写出不能成功提交的代码，说真的，鬼知道。。。
我发现每次我一提交，会显示网络无法连接，然后提交的代码会缺失后面一部分，按某个百分比缺失。。。要命的是还是一下提交好几发wc，，然后我就想到在代码后面加上一行无穷多的斜线//////////，这样前面的有效的代码会全部成功提交，后面的斜线可能会缺失一部分，这样也是成功提交了的，，，反正AC了。
如果还是提交失败，那是你后面的斜线不够多。
0 条评论