通信设备中lct是什么意思

问题描述

精选答案

LCT全称是link-cut-tree，实际上是一个很强的数据结构。

其实LCT可以看做树链剖分的升级版，是因为线段树这个东西就只能是静态的。而且就算把线段树强行动态一下，重链剖分这种复杂度基于静态的东西也会被卡。LCT是把树分成很多条链，每一条链都用splay维护一下。