数据结构，是信息学竞赛的基石，也是NOI考核中分量最重、灵活性最强的模块之一。无论是初涉竞赛的新手，还是冲击国赛的顶尖选手，对数据结构的理解深度与运用熟练度，直接决定了代码效率与解题上限。
福利资料：为协助信息学竞赛生高效备考，特整理《2014-2025年信息学竞赛试题及答案》pdf资料
2026年NOI大纲解读十二：数据结构
一、 知识点概览
大纲对提高级数据结构的要求分为以下五大模块：
- 线性结构包含双端栈、双端队列、有序队列(单调队列)、优先队列，以及用于解决RMQ(区间最值查询)问题的倍增表(ST表)。
- 集合与森林深入理解等价类与并查集。掌握树与二叉树的转化(孩子兄弟表示法)，这是解决复杂树形问题的基础。
- 特殊树(重中之重)进阶数据结构的试金石：线段树与树状数组(维护区间信息的利器)、字典树(Trie树，处理字符串)，以及难度更高的笛卡尔树、二叉平衡树(AVL、Treap、Splay等)和基环树。
- 常见图图论模型的扩展：稀疏图、偶图(二分图)、欧拉图、有向无环图(DAG)，以及连通图、强连通图与重连通图。
- 哈希表快速匹配的魔法：数值、排列、字符串哈希函数的构造，以及常见的哈希冲突解决方法(如拉链法、开放寻址法)。
二、 常见考点与易错点分析
在实际比赛中，高级数据结构往往伴随着极高的代码复杂度和隐蔽的Bug：
并查集的“路径压缩”与“按秩合并”易错点：只写了 fa[x] = find(fa[x])的路径压缩，但在某些被刻意构造的数据下(如不允许路径压缩的回滚操作)，时间复杂度会退化。或者在找祖先时误写成了 return find(fa[x])而没有将值赋回数组。 对策：熟练掌握路径压缩模板，理解什么时候需要配合按秩合并(启发式合并)。
ST表(倍增表)的位运算边界易错点：在预处理 ST 表时，内外层循环顺序写反(正确应是外层枚举区间长度，内层枚举起点)。查询时，计算容易出现精度问题。对策：牢记预处理、查询的流程，强烈建议使用预处理的数组替代库函数log2()。
线段树的“懒标记(Lazy Tag)”下传分析：这是线段树最容易写挂的地方。懒标记未及时下传(PushDown)、或者下传时没有累加父节点的标记，导致区间修改失效。 考点：永远记住“修改和查询触及到子节点前，必须先下传标记”。同时，注意线段树数组必须开到 的大小。
哈希冲突与双哈希易错点：使用单哈希处理字符串匹配时，模数被出题人“卡”(如常见的 配合特定的底数，容易出现哈希碰撞)。 对策：掌握双哈希技巧，使用两个大质数分别取模，极大降低冲突概率。
三、 C++ 示例代码：并查集与ST表模板
这里展示提高级必不可少的并查集(带路径压缩)与ST表(区间最大值)的核心代码。
四、 典型真题解析
例题 1：并查集时间复杂度(CSP-S 初赛题改编)
五、 结构化梳理：思维导图
推荐阅读：
