526互联

动态树&Splay学习笔记

发布时间 2023-07-01 10:26:24作者: Forever1507

前置芝士：Splay

LCT(Link-Cut Tree)

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

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

基本思想:

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