可持久化线段树 + 主席树 || 超详细解释 + 模板

 

注意：可持久化线段树 不一定是 求区间第 k 大的 =-= 不要把这两东西扯在一起啊

心血来潮 把这个基础算法结构补了

呐 先了解一下 可持久化线段树 是什么

自然是 可持久化 + 线段树 啦 多用于询问第m次修改后 某 节点 || 区间 的 值

线段树自然是很好理解的(这个不知道就去补一下吧)

然而可持久化怎么弄呢 总不能每次都copy整棵树吧 不然时空复杂度都打得要死

因此 聪明的三维生物——裸猿人类们啊 发现

在修改一个 节点 || 区间 时啊 改变的只有他的祖先们

因此 我们只需要将该 节点 || 区间涉及的点 和 他们的祖先 复制一遍 赋上修改后该 节点 || 区间 的值 即可

首先是 单点修改(区间修改全靠自觉啦) 具体细节见代码 题目仍旧是洛谷的模板

Tip1:单点 修改 && 查询 建树只需将序列二分下去 区间记录 左儿子 右儿子 节点上记录 点权值

Tip2:储存 节点 和 区间 的 数组 大概开 树上节点数的20倍(虽然本题我看有人开10倍 但我爆了 超凶的 =-=)

下面是代码加注释 真的超详细的=w=

#include <iostream>
#include <cstdio>
using namespace std;
const int MAX = 20000010;
struct Persistable_Segment_tree
{
	int ls,rs,v;//分别是该位置代表的节点或区间的左儿子右儿子和权值
} tr[MAX];
int edit[1 << 20] = {1},w[1 << 20],tot;//edit储存节点版本 注意第一个(下标0)赋值为1表第一个版本 w储存点初始权值
int build(int l,int r)
{//此处不能直接用++tot代替pos 因为跳转到子程序中继续搜索下去 tot值会增加 而此处值代表当前节点编号 应不变
	int pos = ++tot;//tot是当前数组末尾的位置 ++tot则是在末尾处新建储存节点或区间的相关信息 充分利用空间OwO真是太厉害了
	if (l == r)//区间左右相等 即只包括一个点 则只存点权
	{
		tr[pos].v = w[l];//记录初始点权
		return pos;//pos是当前节点的编号 需返回 用以让其父亲节点记录他
	}
	int mid = (l + r) >> 1;//二分存中点
	tr[pos].ls = build(l,mid);//记录当前节点的左儿子编号
	tr[pos].rs = build(++mid,r);//记录当前节点的右儿子编号
	return pos;//返回当前节点编号 需返回 用以让其父亲节点记录他
}
int update(int ed,int l,int r,int p,int k)//在ed版本的基础上 修改p点权值为k 记录当前区间最左&&最右端的点l&&r 
{//此处不能直接++tot代替pos 因为跳转到子程序中继续搜索下去 tot值会增加 而此处值代表当前节点编号 应不变
	int pos = ++tot;//记录当前节点编号 充分利用空间OwO真是太奇妙了
	if (l == r)//当搜索到单个节点了
	{
		tr[pos].v = k;//记录修改后节点权值
		return pos;//返回当前节点编号 让当前版本的父亲记录他
	}
	tr[pos].ls = tr[ed].ls;//将之前的该节点左儿子复制 (引用-->「把子节点指向前驱节点以备复用」)
	tr[pos].rs = tr[ed].rs;//将之前的该节点右儿子复制 因为之后只会改变两儿子之一的值 这样子可以确定该节点位置
	int mid = (l + r) >> 1;//二分存中点
	if (p <= mid) tr[pos].ls = update(tr[ed].ls,l,mid,p,k);//向下寻找 逼近p点 更改pos点的左儿子
	else tr[pos].rs = update(tr[ed].rs,++mid,r,p,k);//向下寻找 逼近p点 更改pos点的右儿子 用tr[ed]的原因是此时tr[pos]只有1深度的孩子的值
	return pos;//返回pos pos作为该点父亲的某个儿子的位置 用以记录
}
int found(int ed,int l,int r,int p)
{//ed是 某版本 储存区间1~n的值 的位置
	if (l == r) return tr[ed].v;//找到该点 此时ed已经变为 记录当前版本的p点的位置了 其v则是当前版本的p点的权值 返回
	int mid = (l + r) >> 1;
	if (p <= mid) return found(tr[ed].ls,l,mid,p);//向下寻找 逼近p点 ed变为ed的左儿子
	else return found(tr[ed].rs,++mid,r,p);//向下寻找 逼近p点 ed变为ed的右儿子
}
int main()
{
	int n,m,edition,mode,node,weight;//恪尽职守的变量定义
	scanf("%d%d",&n,&m);//发人深省的范围输入
	for (int a = 1 ; a <= n ; a ++) scanf("%d",&w[a]);//循规蹈矩的节点输入
	build(1,n);//建树 从区间 1 ~ n 开始递归 找左右儿子
	for (int a = 1 ; a <= m ; a ++)//循序渐进的命令处理
	{
		scanf("%d%d%d",&edition,&mode,&node);//五花八门的命令输入
		if (mode % 2)//巧妙绝伦的判断
		{
			scanf("%d",&weight);//扑朔迷离的补充输入
			edit[a] = update(edit[edition],1,n,node,weight);//update解释见子程序
		}//以update此时求出tr数组的末尾 edit[a]意为在第a个版本时修改的点为edit[a-1]到edit[a]的点(上面那行程序让本人想了很久很久)
		else//机智无比的转折
		{
			edit[a] = edit[edition];//因为复制没有创建新节点 因此当前版本的所有点等于当前版本(不是第a-1的版本)之前的所有点
			printf("%d\n",found(edit[edition],1,n,node));//输出查询某edition的某node的值
		}
	}
	return 0;//逢考必备的结尾
}

其实这行数似乎比线段树的代码还少=-=这世道究竟......

 

好了接下来是 主席树 不会讲的太详细哈 =-=

2018.9.8 经过一个多月偶尔的攻关 Frocean 还是决定向 STL 低下了头 QAQ

手打离散化完全不行啦 查询的时候还是要去重 气死人了

主席树是用到了前缀和的思想 =-=

然而一开始看网上各位 dalao 的解释完全不懂 然后通过各种神奇的方式弄清了——

首先套用一下 “ 对于原序列的每一个前缀 [ 1 ... i ] 建立出一棵线段树维护值域上每个数出现的次数，则其树是可减的 ”

什么鬼东西 原序列哪里有前缀 不是输入一个个权值嘛 而且每个前缀建一棵树 这是要爆炸

呵 (轻蔑) 事实上这个的意思是......我还是举个例子吧

首先我们要把所有数的边界弄出来做线段树的边界 (什么线段树啊 都没说清楚) 别急 说好了举例子的

例如我们一个数列 5 个数 互不相同 比如 233 19260817 6666 19491001 和 1000000007 五个数

最小最大是什么? 好找到了我们拿他们做线段树的边界......等等这会死人的啊

于是离散一下 =-= 变成 1 3 2 4 和 5 到时候求答案转换回去即可

好了线段树怎么造呢 看我强迫症画了十五分钟的图

差不多了吧 =-= 意思很清楚

每次读入一个数 然后包含他离散后数值的树的区间 size 都加一 相当于单点修改

如果求区间 l 到 r 的 最小值 就用 第 r 次更新后树的形态 减去 第 l - 1 (记住是 l - 1) 次更新的树的形态

因此我们不能在空间只有 n 的 线段树上做这事......之前不是有可持久化线段树嘛

那我们对于每次更新到的点 像可持久化线段树一样 把加入第 i 个点当成第 i 个版本 然后同样多加一堆节点就好了 然后就没有然后了哈

话说网上那些图都不画单数个节点的真的是烦躁啊......

Tip1 : 初始离散化 + 去重 用 unique 就好 手打离散化 + 去重我是实在懒得弄 已经贡献了一页的记录了 当然没有 Splay 的 三页那么恐怖

Tip2 : 主席树建树先确定边界 然后只用记每个点的左儿子和右儿子哈 权值到时候搜到第 k 大的时候返回点位置即可

Tip3 : 主席树插入大概和上面的那树差不多 于是关于 edit 和 ed 的 自觉上翻

Tip4 : 主席树查询很重要 细看哦 没有细讲主要是懒得画图......

洛谷的模板戳这里 还有注释'可能'在代码里面哦 我对我的码风莫名自信~

#include <algorithm>
#include <cstdio>
using namespace std;
const int MAXN = 200005;
struct tree {
	int l,r,siz;//l r 找位置 然后 siz 就是当前区间内的数的数量
} tr[MAXN << 5];
int tot,v[MAXN],w[MAXN];
int edit[MAXN];
int build(int l,int r)
{//建树 确定区间递归下去到哪个区间 记录编号 返回最终给edit[0] = 1 确定第一次更新时的根节点
	int pos = ++tot;
	if (l == r) return pos;
	int mid = (l + r) >> 1;
	tr[pos].l = build(l,mid);
	tr[pos].r = build(++mid,r);
	return pos;
}
int insert(int ed,int l,int r,int i)
{//同 可持久化线段树
	int pos = ++tot;
	tr[pos].l = tr[ed].l;
	tr[pos].r = tr[ed].r;
	tr[pos].siz = tr[ed].siz + 1;
	if (l == r) return pos;
	int mid = (l + r) >> 1;
	if (i <= mid) tr[pos].l = insert(tr[ed].l,l,mid,i);
	else tr[pos].r = insert(tr[ed].r,++mid,r,i);
	return pos;
}
int out(int l,int r,int i,int j,int k)
{// 查到点了返回点权 其实可以放在最外层..
	if (l == r) return w[l];
	int ex = tr[tr[j].l].siz - tr[tr[i].l].siz;
	//important ex是当前区间左儿子区间的size值 这里用到了二叉查找树的思想
	int mid = (l + r) >> 1;
	if (ex >= k) return out(l,mid,tr[i].l,tr[j].l,k);
	return out(++mid,r,tr[i].r,tr[j].r,k - ex);
}//减去后是剩下要查的区间里第k大的点数 之前是之前(相对的)全部区间里第k大的点数
int main()
{
	int n,q,i,j,k;
	scanf("%d%d",&n,&q); for (int a = 1 ; a <= n ; ++ a)
	scanf("%d",&v[a]),w[a] = v[a];
	sort(w + 1, w + 1 + n);
	int len = unique(w + 1, w + 1 + n) - w - 1;
	edit[0] = build(1, len);
	for (int a = 1 ; a <= n ; ++ a) {
		int pos = lower_bound(w + 1,w + 1 + len,v[a]) - w;
		edit[a] = insert(edit[a - 1],1,len,pos);
	}
	while (q--) {
		scanf("%d%d%d",&i,&j,&k);
		printf("%d\n", out(1,len,edit[i - 1],edit[j],k));
	}
	return 0;
}