LCT

引子 在古老且美妙的数据结构王国，一次，一个巨大的怪兽出现在了这个国家，这个怪兽是一棵树，打败这个怪兽只需要能快速求出这个怪兽任意一条路径上的和就可以了，可是他灵活多变，自己的手脚可以调换位置，或拿下来（边可以断掉或连上）身上的每一寸肌肤都可改变其硬度（点可以修改值） 树链剖分找到了$splay$， ......

P4219 [BJOI2014] 大融合 template <int N> struct LCT { int ch[N + 10][2], fa[N + 10]; bool rev[N + 10]; int sizl[N + 10], siz[N + 10]; bool getson(int p) ......

唔，其实我不会 Splay，但是我会 LCT。 众所周知，会 LCT 和会 Splay 是两回事，因为 LCT 只需要旋至根即可。 到现在还是不会，但是先把 LCT 的 Splay 写一下吧。 自己复习用的。 先给代码。 LCT code int isroot(int x) {return ch[f ......

LCT 小记 前言 在 OI 中，对于常规的树论问题，其树的形态一般是静态的。 但往往会存在一批毒瘤出题人，他们把树的形态变成了动态的，出现了 加边/删边 等操作。 而对于这类 「动态树问题」，我们有三种常见的数据结构可以维护，而本文将简单地引入其中的一种。 LCT。 以下简称这类处理动态树问题的数 ......

LCT学习笔记 LCT，（Link Cut Tree） ，是一种动态树，维护的是森林。可以维护作有两点连通性，两点路径权值和，连接两点和切断某条边、修改信息等。 LCT是用Splay来维护的。每颗Splay维护的是原森林中的一条路径。 性质一：Splay还要维护一个性质，那就是每颗Splay的中序遍 ......

//我坚信LCT可以平替树剖 #include<bits/stdc++.h> #define ls t[o].ch[0] #define rs t[o].ch[1] #define int long long using namespace std; const int N=500010; cons ......

初中生都能看懂的 LCT 学习笔记 这篇文章偏向入门，旨在尽可能解决一类问题——动态树，主要讲述并且整理 LCT 算法及其一些变式。 目前其变式例题作者还在整理之中，编者保证会把变式例题持续更新。 0.前置知识 splay。 我可以猜测一下，你们可能看到 splay，然后就可能去学了 splay 树 ......

不想了解基础知识的可以直接从 \(LCT\) 基础操作部分开始，前面不是很重要 目录\(LCT\)基础知识实链剖分辅助树一些性质\(LCT\) 基础操作函数定义函数实现 主要参考oi-wiki \(LCT\)基础知识 树上操作是算法竞赛中重要的操作 由于树的特殊性，使得维护一些子树信息和路径信息变得 ......

樱雪喵用时 3days 做了 ybtoj 的 3 道例题，真是太有效率了！！1 写死自己系列。 为了避免自己没学明白就瞎写东西误人子弟，这篇 Blog 拖到了现在。 图片基本沿用 OIwiki，原文跳步骤（主要是 access 部分）的就自己补画了一些。 不过反正也没啥人看？ 前置知识 Splay ......

其实是我 Li-Chao-Tree 哒！！ 考虑转移 \(f_x = \min f_{anc} + (d_{x} - d_{anc})p_x + q_x\) 其中 \(anc\) 为 \(x\) 的祖先，然后满足 \(d_{anc} \geq d_{x} - li_{x})\)。 考虑如果用权值线段 ......

贴个 $LCT$ 模板 **注意事项** 在 $cut$ 中是判断 $y$ 的左儿子,清零 $x$ 的左儿子 在 $access$ 中将 $x$ 的右儿子变成 $y$ 当维护最值的时候，将最值放在某一个数组里面 $LCT$ 内部存**下标**，不然不能带修 真的很吃细节 代码 ```cpp #inc ......

### Splay 核心代码。 总结就是双旋 ```cpp void rot(int x,int &k){ int y=tr[x].fa,z=tr[y].fa; int kd=(tr[y].son[0]==x)?0:1; if(y==k) k=x; else { if(tr[z].son[0]==y ......

以 P3690 为例。 ```cpp #include #define UP(i,s,e) for(auto i=s; isum = x->val ^ x->ls->sum ^ x->rs->sum; } void reverse(Node *); void pushdown(Node *x){ i ......

Splay：平衡树的一种，学名伸展树。 平衡树首先是一棵二叉搜索树（BST），满足性质：中序遍历单调递增。 根据这个性质，很容易在一棵 BST 上完成以下操作：插入一个数，查询一个数的排名，查询给定排名的数，删除一个数。 BST 可能是不平衡的，即左右子树相差很大。Splay 均摊后是平衡的，即时间 ......

## 动态树问题的引入 ### 静态树问题 静态树问题的一般形式如下： > 给定一个树，点和边可能有权。 > > 要对这个树按时间顺序进行一些操作和询问。 > > 操作可以修改点和边的权值。 > > 询问可以对链和子树进行询问。 通俗的讲，所有在整个过程中树的结构不变的树论问题就叫静态树问题。 ## ......

若每个节点存一个字符或权值，现在要快速匹配两条链，则可以使用此方法。 具体的操作和普通的 LCT 没有什么区别，但是十分的方便。 并且支持区间赋值等修改操作，十分优秀。 int base,p=100000267; void csh(){fi[0]=1;for(int i=1;i<N;i++)fi[i ......

A[洛谷P3690]维护一个森林，支持询问路径xor和，连边（已连通则忽略），删边（无边则忽略），改变点权。 B[洛谷P3203]$n$个装置编号为$0,...,n-1$，从$i$可以一步跳到$i+k_i$，支持修改$k_i$，询问从一个点开始几步跳出$n-1$。 C[洛谷P2486]给定一棵树，点 ......

动态树与LCT LCT：Link Cut Tree 可以用来解决动态地连接和删除 结合树链剖分（实链剖分）和Splay树 “原树实链从上到下，对应Splay树从左到右” 把原树转化到辅助树上操作 而辅助树由若干个Splay树用虚边相连得来 P3690 【模板】动态树（Link Cut Tree） 题 ......