用户工具

站点工具


2020-2021:teams:no_morning_training:fayuanyu:lct

这是本文档旧的修订版!


lct

我说这是我本命数据结构有人信吗(

前置知识

请务必理解:
树剖
splay

参考论文:QTREE 解法的一些研究

原理

树剖维护重链,而lct维护实边。

我们令一个子树的树根 到 子树中最后访问的点的路径 是 实边
则最后一次访问的点,到树根的路径,全部为实边
每个点到它的儿子中的边最多有一条实边

2020-2021/teams/no_morning_training/fayuanyu/lct.1589557266.txt.gz · 最后更改: 2020/05/15 23:41 由 发源于