文档章节

【模板】左偏树

o
 osc_g8254g7s
发布于 2019/08/19 20:54
字数 1175
阅读 25
收藏 0

精选30+云产品,助力企业轻松上云!>>>

一、左偏树的定义和性质

  1. 左偏树是一棵二叉树,也是一种可并堆,拥有堆的性质,可以像堆一样合并。
  2. 左偏树顾名思义,有“左偏”的特点,既每个左子树节点的$dist$一定大于等于右子树节点的$dist$。
  3. 由性质2可得:$t[x].d=t[t[x].ch[1]].d+1$
  4. 同时,我们需要注意左偏树的$dist$并不意味着深度,跟深度无关。

讲了这么久$dist$,那么$dist$到底是什么?


二、$dist$的定义与含义

对于一个二叉树,我们定义一个节点的$dist$为它到离它最近的叶子节点的距离+1,叶子节点的$dist=1$,空节点的$dist=0$


三、核心操作

$Merge:合并操作$

详细见代码注释

int& rs(int x)//求右儿子
{
	return t[x].ch[t[t[x].ch[1]].d<t[t[x].ch[0]].d];//为了满足左偏树的性质2,须保证右子树节点的dist小于左子树节点的dist
}
int merge(int x,int y)//合并x,y
{
	if(!x||!y)return x+y;
	if(t[x].val>t[y].val)swap(x,y);//这个根据所须的左偏树是大根堆还是小根堆,这里是小根堆,反过来是大根堆
	rs(x)=merge(rs(x),y);//将右子树与y合并
	f[rs(x)]=x;//当需要更新父亲时加上
	t[x].d=t[rs(x)].d+1;//满足左偏树的性质3
	return x;
}

$Pop:删除x节点所在堆的最小值/最大值$

找到$x$所在堆的最小值/最大值,用并查集实现,接着合并$x$的左右子树

int find(int x){x==f[x]?x:f[x]=find(f[x]);}
void pop(int &x)
{
	x=find(x)//找到x所在堆的最大值/最小值
	x=merge(t[x].ch[0],t[x].ch[1]);//合并左右儿子
}

$Del:删除任意(x)编号节点$

注意:这里是删除任意编号节点,而不是任意权值节点,左偏树不支持删除任意权值节点

我们先合并$x$的左右儿子

接着更新$x$的父亲和$f[x]$的儿子

因为这样合并更新可能会破坏左偏的性质,所以需要遍历检查满不满足左偏性质,更新,直到满足左偏性质就可以结束或者到达根节点

void pushup(int x)
{
	if(!x)return ;//达到根节点,返回
	if(t[x].d!=t[rs(x)].d+1)//不满足左偏性质,更新
	{
		t[x].d=t[rs(x)].d+1;
		pushup(f[x]);
	}
}
int merge(int x,int y)
{
	if(!x||!y)return x|y;
	if(t[x].val>t[y].val)swap(x,y);
	f[rs(x)=merge(rs(x),y)]=x;
	pushup(x);
	return x;
}
void del(int x)
{
	int fx=f[x];//x的父亲
	int u=merge(t[x].ch[0],t[x].ch[1]);//合并左右儿子
	f[u]=fx;//更新合并后的节点的信息
	if(t[fx].ch[0]==x)t[fx].ch[0]=u;
	else t[fx].ch[1]=u;
	t[x].val=t[x].ch[0]=t[x].ch[1]=t[x].d=0;
	pushup(x);//遍历检查左偏性质
}

$Push:插入x节点$

新建一个节点,将其初始化为$x$

因为这个节点也可以视为一个堆,可以直接合并

void push(int &rt,int v)
{
	t[++cnt].val=v;
	t[cnt].ch[0]=t[cnt].ch[1]=t[cnt].d=0;
	rt=merge(rt,cnt);
}

在以$x$为根的整个堆加上/减去/乘上一个数

在根$x$上打标记,然后每一次合并堆或者删除根时下传

void pushdown(int x)//这里以加上一个数为例
{
	if(lazy[x])
	{
		t[t[x].ch[0]].val+=lazy[x];
		t[t[x].ch[1]].val+=lazy[x];
		lazy[t[x].ch[0]]+=lazy[x];
		lazy[t[x].ch[1]]+=lazy[x];
		lazy[x]=0;
	}
}

例题

  1. 模板题
    1. 洛谷P3377 【模板】左偏树(可并堆)
    2. 洛谷P2713 罗马游戏

给出洛谷P2713 罗马游戏的代码

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
struct Tree
{
	int val,ch[2],d;
}t[N];
int n,q;
int f[N];
bool dead[N];
int& rs(int x)
{
	return t[x].ch[t[t[x].ch[1]].d<t[t[x].ch[0]].d];
}
int merge(int x,int y)
{
	if(!x||!y)return x|y;
	if(t[x].val>t[y].val)swap(x,y);
	f[rs(x)=merge(rs(x),y)]=x;
    t[x].d=t[rs(x)].d+1;
	return x;
}
int find(int a)
{
	return a==f[a]?a:f[a]=find(f[a]);
}
char op[10];
int main()
{
	scanf("%d",&n);
	int a,b;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a);
		t[i].val=a;
		f[i]=i;
	}
	scanf("%d",&q);
	while(q--)
	{
		scanf("%s",op);
		if(op[0]=='M')
		{
			scanf("%d %d",&a,&b);
			int fx=find(a),fy=find(b);
			if(dead[a]||dead[b]||fx==fy)continue;
			f[fx]=f[fy]=merge(fx,fy);
		}
		else 
		{
			scanf("%d",&a);
			if(dead[a])
			{
				puts("0");
				continue;
			}
			a=find(a);
			dead[a]=1;
			f[a]=f[t[a].ch[0]]=f[t[a].ch[1]]=merge(t[a].ch[0],t[a].ch[1]);
			printf("%d\n",t[a].val);
		}
	}
	return 0;
}

  1. 例题
    1. 【XSY1985】【BZOJ1367】【Baltic2004】sequence
    2. 【XSY2488】【HDU5818】Joint Stacks

深深感觉到自己的渺小

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
目录

#模板 ##数学 [模板 - 整除分块]模板 - 组合数模板 - 线性筛模板 - 卢卡斯定理[模板 - 自适应辛普森积分] 模板 - 二次剩余模板 - 扩展欧几里得算法模板 - 扩展中国剩余定理模板 - 扩展大步小...

osc_bkdv2it5
2019/08/19
0
0
左偏树学习笔记

左偏树学习笔记 具体印象 普通的二叉堆只能实现普通的堆的功能。 如果需要支持合并操作,就需要使用可并堆,左偏树就是一种好写的可并堆。 左偏树是一颗二叉树,由于特殊性质,整棵树会集中在...

osc_02vmpq90
2019/02/04
1
0
左偏树详解

左偏树是一种比较常用的可并堆。那什么是可并堆呢?可并堆,顾名思义,是一种除了支持堆的基本操作外,还支持合并等操作的数据结构,如斜堆,左偏树,二项堆,配对堆,斐波那契堆等。 左偏树...

osc_qg4dad59
2019/08/14
0
0
【BZOJ1455】罗马游戏(左偏树)

#【BZOJ1455】罗马游戏(左偏树) 题面 BZOJ然而权限题。 题解 左偏树模板题。

osc_nmgdty43
2018/09/04
1
0
左偏树——可以标记合并的堆

左偏树: 左偏树(Leftist Tree)是一种可并堆的实现。左偏树是一棵二叉树,它的节点除了和二叉树的节点一样具有键值外,还有一个属性距离(dist)。 距离指的是这个点到某个叶子结点的最短距离 ...

osc_w6ajhfm8
2018/07/25
2
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周日乱弹 —— 那么长的绳子,你这是放风筝呢

Osc乱弹歌单(2020)请戳(这里) 【今日歌曲】 @ 巴拉迪维:黑豹乐队的单曲《无地自容》 耳畔突然响起旋律,是那首老歌。中国摇滚有了《一无所有》不再一无所有;中国摇滚有了《无地自容》不...

小小编辑
54分钟前
65
1
《吐血整理》-顶级程序员书单集

你知道的越多,你不知道的越多 给岁月以文明,而不是给文明以岁月 前言 王潇:格局决定了一个人的梦想,梦想反过来决定行为。 那格局是什么呢? 格局是你能够看见的深度、广度和密度。 王潇认...

敖丙
2019/12/11
8
0
我可以在Android版式中加下划线吗? - Can I underline text in an Android layout?

问题: 如何在Android布局xml文件中定义带下划线的文本? 解决方案: 参考一: https://stackoom.com/question/A31z/我可以在Android版式中加下划线吗 参考二: https://oldbug.net/q/A31z/...

法国红酒甜
56分钟前
26
0
干掉ELK | 使用Prometheus+Grafana搭建监控平台

什么是Prometheus? Prometheus是由SoundCloud开发的开源监控报警系统和时序列数据库(TSDB)。Prometheus使用Go语言开发,是Google BorgMon监控系统的开源版本。 Prometheus的特点 · 多维度...

木九天
今天
34
0
拉勾网拉你上勾

预览 需求简介 拉勾网是一个互联网行业的一个招聘网站,上面有许多职位,于是乎,小编想提取指定职位的基本信息(职位名,薪水,工作经验,工作地点,教育背景),然后插入 MongoDB 数据库,...

木下瞳
2019/04/17
20
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部