分类: 算法

15 篇文章

后缀数组学习笔记
本文大部分内容参考 OI-Wiki 相关部分。 简介 后缀数组(Suffix Array),主要是两个数组: $sa$ 与 $rk$ . 我们约定,后缀 $i$ 表示从 $i$ 开始的后缀。字符串下标从 $1$ 开始。 其中, $sa[i]$ 代表所有后缀中,第 $i$ 小的后缀的编号。$rk[i]$ 代表后缀 $i$ 从小到大的排名。 有: $s…
LCT(Link Cut Tree)
本文大部分内容参考 OI-Wiki 有关部分。 简介 Link/Cut Tree 是一种数据结构,用于解决动态树问题。其又称 Link-Cut Tree,简称 LCT,但不叫动态树。动态树指一类问题。"Splay" 是 LCT 的基础,但 LCT 中的 Splay 在细节处不太一样,进行了一定的扩展。 这是一个和 Splay 一样只需要几个核心函数…