高级数据结构 学习笔记

前言 本文主要根据 OIwiki 的数据结构部分展开，也按照常见的考点加入了一些图论、字符串领域的数据结构。本文只包含最基本的理论介绍，相关的实现方式、具体的解题思路和代码都放在站内其他文章中。 后续做到比较好的数据结构题也会添加进这篇文章中来。 块状数据结构 分块初步 经典例题1：参见站内文章 LOJ6280 分块入门 区间和 解题笔记 总体思路：寻找一种合理的分块方式，操作区间中不是整块的部分暴力求解，是整块的部分打标记。 寻找最优分块方式，通常是对最坏时间复杂度求最小值，取得最小值时的约束条件可以得到最优块长。 在分块的基础上，依然可以使用差分、前缀和等方式来优化算法。差分、前缀和不仅可以对原序列使用，也可以对块序列使用。 相关注意事项： 块长不一定等于块数。 区间两端点在同一个块中，必须特判..