一份会超时的解法和一份能拿满分的解法之间的差别，很少仅仅在于巧思——通常是在恰当的时机选对了恰当的数据结构。
在竞赛编程中，你会拿到一道题、一个时间限制（通常是一到两秒）以及紧张的内存预算。同样的逻辑，会因为你的操作是在线性时间、对数时间还是常数时间内完成而决定通过与否。因此，熟练掌握一组聚焦的竞赛编程数据结构，是学生能做的回报最高的事情之一。下面我们将逐一讲解最重要的几种结构，大致按你应当学习的顺序排列，并把它们对应到各自能解锁的题型。
从基础打起
在伸手去拿任何花哨的工具之前，先把基本组件用熟。大多数赛题——以及绝大多数入门级题目——仅凭这些就能解决：
- 数组与动态数组（vector），用于按下标存储和前缀和。
- 栈与队列，用于排序、回溯和广度优先遍历。
- 哈希表与哈希集合，用于近似常数时间的查找、计数和去重。
- 有序集合与有序映射（平衡二叉搜索树），当你既需要查找又需要有序时使用。
- 优先队列（堆），用于始终取出下一个最小或最大的元素——它是 Dijkstra 算法和贪心调度的骨干。
在 C++ 中，所有这些都随标准模板库（STL）一同提供，这也是 C++ 在竞赛中始终流行的原因之一。把 STL 用熟，意味着你能把比赛时间花在思考问题本身，而不是重新实现一个堆。如果你才刚刚起步，我们的竞赛编程项目会通过有意识、有评分的练习培养这种熟练度，而不是零散地刷题。
能夺奖的那些结构
当基础变成本能之后，一小批更进阶的结构会在更难的组别中反复出现。其中三种值得单独点名：
并查集（Union-Find）
并查集（DSU）维护一组被划分为若干不相交集合的元素，提供两种操作：find（这个元素属于哪个集合？）和 union（合并两个集合）。配合路径压缩和按秩合并，两种操作都能在近乎常数的摊还时间内完成。它是连通性问题以及 Kruskal 最小生成树算法的标准工具。
树状数组（Fenwick Tree）
树状数组由 Peter Fenwick 于 1994 年首次提出，能在 O(log n) 时间内回答前缀和查询并完成单点更新。它占用与原数组相同的内存，且代码简短，因此当一道题纯粹是单点更新加区间求和时，它就是首选。
线段树（Segment Tree）
线段树是更通用的表亲。每个节点代表数组的一个区间，让你能够回答区间最小值、最大值、求和或 gcd 查询——并且借助懒惰传播，可以一次性更新整个区间。它占用的内存大约是树状数组的四倍，代码也更长，所以实用的判断法则很简单：
当你只需要单点更新下的区间求和时，伸手去拿树状数组。一旦你需要最小值、最大值、区间更新，或任何树状数组无法求逆的操作，就立刻换成线段树。
这如何对应到真实赛事
美国计算机奥林匹克竞赛（USACO）把这种进阶过程展现得淋漓尽致。它在一年中举办数场线上比赛，每场三道题、满分 1000 分，学生依次晋升四个组别：Bronze、Silver、Gold 和 Platinum。
- Bronze 奖励完全搜索、排序、贪心和基础数据结构。
- Silver 倚重图与树，外加栈和队列。
- Gold 引入滑动窗口以及单点更新区间求和问题——正是树状数组和线段树发挥价值的地方。
- Platinum 要求精通区间查询、掌握进阶的树技巧，并能创造性地组合上述各种结构。
这道阶梯令人鼓舞：你不必在第一天就掌握每一种结构。每个组别只要求一两件新工具，所以稳扎稳打的学习者可以一路攀登而不至于精疲力竭。在我们的赛事总览上浏览往年题目，是了解每个难度等级期待哪种结构的好方法。
一份实用的学习顺序
- 把数组、前缀和以及 STL 容器用熟。
- 加上栈、队列、堆和哈希表，直到它们成为本能。
- 学习并查集，然后是树状数组，再然后是线段树。
- 在经典题集上练习，并复盘每一道你没能做完的题。
持续且经过复盘的练习，每一次都胜过单纯堆量。如果你想要一条从 STL 基础到夺奖级区间查询的结构化路径——并得到经验丰富的教练的反馈——欢迎了解 BIAA 的竞赛编程方向，开始打造那套能把难题变成已解之题的工具箱。