🏗️ 第三部分：核心数据结构
几乎出现在每一道 USACO Bronze 和 Silver 题目中的数据结构——前缀和、排序、双指针、栈、映射和线段树。
📚 10 章 · ⏱️ 预计 2-3 周 · 🎯 目标：解决 USACO Bronze 题目
第三部分：核心数据结构
预计用时：2-3 周
第三部分是竞赛编程开始变得有趣的地方。你将学习几乎出现在每一道 USACO Bronze 和 Silver 题目中的数据结构——以及能把 O(N²) 暴力解法变成 O(N) 优雅方案的技巧。
涵盖的主题
| 章节 | 主题 | 核心思想 |
|---|---|---|
| 第 3.1 章 | STL 核心用法 | 掌握强大的内置容器：sort、map、set、queue、stack |
| 第 3.2 章 | 数组与前缀和 | O(N) 预处理后，O(1) 回答区间求和查询 |
| 第 3.3 章 | 排序与搜索 | 排序 + 二分查找，把很多 O(N²) 问题变成 O(N log N) |
| 第 3.4 章 | 双指针与滑动窗口 | 用两个协调移动的指针高效处理子数组/对 |
| 第 3.5 章 | 单调栈与单调队列 | O(N) 求下一个更大元素、滑动窗口最大/最小值 |
| 第 3.6 章 | 栈、队列与双端队列 | LIFO/FIFO 处理的有序数据结构 |
| 第 3.7 章 | 哈希技术 | 快速键查找、多项式哈希、滚动哈希 |
| 第 3.8 章 | 映射与集合 | O(log N) 查找、唯一元素集合、频率统计 |
| 第 3.9 章 | 二分答案 | 把枚举答案转化为「猜+验证」的二分问题 |
| 第 3.10 章 | 字符串算法 | KMP 字符串匹配、Trie 树（字典树）、01-Trie |
💡 树形数据结构（二叉树、并查集、线段树、树状数组）已归入第五部分：图论算法（第 5.4～5.7 章）。
学完本部分后能解决什么问题
完成第三部分后，你将能够挑战：
-
USACO Bronze： 大多数 Bronze 题目使用第三部分的技术
- 区间查询（位置 L 到 R 之间 X 类型的奶牛有多少头？）
- 排序问题（最近点对、排名、调度）
- 频率统计（每个值出现多少次？）
- 栈相关问题（括号匹配、单调处理）
-
USACO Silver 入门：
- 二分答案（攻击性奶牛、绳子切割）
- 滑动窗口最大/最小值
- 差分数组实现区间更新
引入的关键算法
| 技术 | 章节 | USACO 相关度 |
|---|---|---|
| 一维前缀和 | 3.2 | 品种统计、区间查询 |
| 二维前缀和 | 3.2 | 网格上的矩形区域求和 |
| 差分数组 | 3.2 | 区间更新、单点查询 |
带自定义比较器的 std::sort | 3.3 | 几乎所有 Silver 题目 |
二分查找（lower_bound、upper_bound） | 3.3 | 计数、区间查询 |
| 二分答案 | 3.3 | 攻击性奶牛、画家分区 |
| 单调栈 | 3.5 | 下一个更大元素、直方图 |
| 滑动窗口（单调队列） | 3.5 | 窗口最小/最大值 |
频率映射（unordered_map） | 3.7 | 统计出现次数 |
| 有序集合操作 | 3.8 | 第 K 小元素、区间查询 |
前置条件
开始第三部分前，请确认你能做到：
- 从零编写并编译 C++ 程序（第 2.1 章）
-
正确使用
for循环和嵌套循环（第 2.2 章） -
使用数组和
vector<int>（第 2.3 章）
注意： 第 3.1 章（STL 核心用法）是本部分的第一章，将在后续章节用到之前先教你
std::sort、map、set等关键 STL 容器。
本部分学习建议
- 第 3.2 章（前缀和） 是 Bronze 中测试最频繁的技术。确保你能在 5 分钟内从零实现它。
- 第 3.3 章（二分查找） 介绍「二分答案」——这是 Silver 级别的技术，是普通解法和优秀解法的分水岭。
- 不要跳过练习题。 每章的练习题都是专门为培养所需直觉而精选的。
- 完成第 3.3 章后，你已经具备解决大多数 USACO Bronze 题目的工具。在继续学习前，尝试解 5-10 道 Bronze 题目。
🏆 USACO 技巧： 在 USACO Bronze 级别，最常用的技术是：模拟（第 2.1–2.3 章）、排序（第 3.3 章）和前缀和（第 3.2 章）。掌握这三项，几乎可以解决任何 Bronze 题目。
出发！