首页 > 其他分享 >动态树&Splay学习笔记

动态树&Splay学习笔记

时间:2023-07-01 10:34:40浏览次数:36  
标签:实边 原树中 原树 Splay 笔记 平衡 动态 节点

前置芝士:Splay

LCT(Link-Cut Tree)

使用场景:动态树问题。
基本概念:

  • 原树:给定的原始树。
  • 实边:在原树中节点 \(cur\) 选取一个子节点 \(son\),则 \(cur-son\) 的连边为实边。
  • 虚边:不是实边。
  • 实链:由实边构成的链。

基本思想:

  • 将原树中的一条链,用一颗平衡树(一般是 Splay)来维护,其中平衡树的中序遍历是原树中深度从浅到深的一条路径。
  • 维护平衡树的森林,森林中的节点与原树中的节点一一对应。
  • 一颗平衡树维护的是原树中的一条实链。

标签:实边,原树中,原树,Splay,笔记,平衡,动态,节点
From: https://www.cnblogs.com/Forever1507/p/17518915.html

相关文章

  • Splay
    概念Splay树(伸展树),是一种平衡BST它通过伸展操作不断将某个节点旋转到根节点,使得整棵树仍然满足BST的性质,能够在均摊\(O(\logn)\)时间内完成插入,查找和删除操作,并且保持平衡而不至于退化为链。实现rotate其保证不破坏BST的性质不破坏节点维护的信息root必须指向旋转后......
  • docker使用笔记
    @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@docker批量启动与停止容器::dockerstart$(dockerps-a-q)试试看 dockerstop$(dockerps-a-q)试试看 @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@centos7安装shipyard没有本地容器及镜像:方法:.设置防火墙[root@c2~]#firewall-cmd--z......
  • oracle11gr2笔记(一)
    一,使用scoot用户被锁。解决办法:(http://ciiiso.blog.51cto.com/8779682/1432869/)二,使用root用户登录系统无法sqlplus,提示说permissiondenied.原因为没有source用户oracle下的./bash_profile。解决办法:在.bash_profile里面加上里面的变量。三,无法用root用户登录系统,办法:(http://jingy......
  • mysql5.7.13 使用笔记
    社区版下载地址:https://dev.mysql.com/downloads/mysql/ 安装:http://www.linuxidc.com/Linux/2016-04/130414.htm     (配置文件my.cnf在网页的最下面)更新yum源:tar解压失败:http://alany.blog.51cto.com/6125308/1422299###############################################......
  • VisionPro学习笔记(2)——图像转换工具ImageCovertTool
    众所周知,VisionPro是一款功能强大的机器视觉软件,用于开发和部署机器视觉应用程序。其中ImageConvertTool是其中一个重要的工具,用于图像转换和处理。本文将介绍如何使用ImageConvertTool进行图像转换,并探讨其背后的原理。写之前先吐槽一下,引出自己的原因,哈哈哈(当然一个小......
  • 【任务分配】基于matlab实现多无人机动态任务分配附matlab代码
    ✅作者简介:热爱科研的Matlab仿真开发者,修心和技术同步精进,matlab项目合作可私信。......
  • 动态规划之二维费用的背包问题
    问题二维费用的背包问题是指:对于每件物品,具有两种不同的费用;选择这件物品必须同时付出这两种代价;对于每种代价都有一个可付出的最大值(背包容量)。问怎样选择物品可以得到最大的价值。设这两种代价分别为代价1和代价2,第i件物品所需的两种代价分别为a[i]和b[i]。两种代价可付出的最......
  • 动态规划之 附录二:背包问题的搜索解法
    《背包问题九讲》的本意是将背包问题作为动态规划问题中的一类进行讲解。但鉴于的确有一些背包问题只能用搜索来解,所以这里也对用搜索解背包问题做简单介绍。大部分以01背包为例,其它的应该可以触类旁通。简单的深搜对于01背包问题,简单的深搜的复杂度是O(2^N)。就是枚举出所有2^N......
  • 动态规划之 附录一:USACO中的背包问题
    USACO是USAComputingOlympiad的简称,它组织了很多面向全球的计算机竞赛活动。USACOTrainng是一个很适合初学者的题库,我认为它的特色是题目质量高,循序渐进,还配有不错的课文和题目分析。其中关于背包问题的那篇课文(TEXTKnapsackProblems)也值得一看。另外,USACOContest是US......
  • 动态规划之 背包问题问法的变化
    以上涉及的各种背包问题都是要求在背包容量(费用)的限制下求可以取到的最大价值,但背包问题还有很多种灵活的问法,在这里值得提一下。但是我认为,只要深入理解了求背包问题最大价值的方法,即使问法变化了,也是不难想出算法的。例如,求解最多可以放多少件物品或者最多可以装满多少背包的空......