🏗️ Part 3: Core Data Structures
The data structures that appear in nearly every USACO Bronze and Silver problem — prefix sums, sorting, two pointers, stacks, maps, and segment trees.
📚 11 Chapters · ⏱️ Estimated 2-3 weeks · 🎯 Target: Solve USACO Bronze problems
Part 3: Core Data Structures
Estimated time: 2–3 weeks
Part 3 is where competitive programming starts getting exciting. You'll learn the data structures that appear in nearly every USACO Bronze and Silver problem — and techniques that can turn O(N²) brute force into O(N) elegance.
What Topics Are Covered
| Chapter | Topic | The Big Idea |
|---|---|---|
| Chapter 3.1 | STL Essentials | Master the powerful built-in containers: sort, map, set, queue, stack |
| Chapter 3.2 | Arrays & Prefix Sums | Answer range sum queries in O(1) after O(N) preprocessing |
| Chapter 3.3 | Sorting & Searching | Sort + binary search turns many O(N²) problems into O(N log N) |
| Chapter 3.4 | Two Pointers & Sliding Window | Efficiently process subarrays/pairs with two coordinated pointers |
| Chapter 3.5 | Monotonic Stack & Monotonic Queue | Next greater element, sliding window max/min in O(N) |
| Chapter 3.6 | Stacks, Queues & Deques | Order-based data structures for LIFO/FIFO processing |
| Chapter 3.7 | Hashing Techniques | Fast key lookup, polynomial hashing, rolling hash |
| Chapter 3.8 | Maps & Sets | O(log N) lookup, unique collections, frequency counting |
| Chapter 3.9 | Introduction to Segment Trees | Efficient range queries and point updates in O(log N) |
| Chapter 3.10 | Fenwick Tree (BIT) | Efficient prefix-sum with point updates, inversion count |
| Chapter 3.11 | Binary Trees | Tree traversals, BST operations, balanced trees |
What You'll Be Able to Solve After This Part
After completing Part 3, you'll be ready to tackle:
-
USACO Bronze: Most Bronze problems use Part 3 techniques
- Range queries (how many cows of type X in positions L to R?)
- Sorting problems (closest pair, ranking, scheduling)
- Frequency counting (how many times does each value appear?)
- Stack-based problems (balanced brackets, monotonic processing)
-
USACO Silver Intro:
- Binary search on the answer (aggressive cows, rope cutting)
- Sliding window maximum/minimum
- Difference arrays for range updates
Key Algorithms Introduced
| Technique | Chapter | USACO Relevance |
|---|---|---|
| 1D Prefix Sum | 3.2 | Breed counting, range queries |
| 2D Prefix Sum | 3.2 | Rectangle sum queries on grids |
| Difference Array | 3.2 | Range update, point query |
std::sort with custom comparator | 3.3 | Nearly every Silver problem |
Binary search (lower_bound, upper_bound) | 3.3 | Counting, range queries |
| Binary search on answer | 3.3 | Aggressive cows, painter's partition |
| Monotonic stack | 3.5 | Next greater element, histogram |
| Sliding window (monotonic deque) | 3.5 | Window min/max |
Frequency map (unordered_map) | 3.7 | Counting occurrences |
| Ordered set operations | 3.8 | K-th element, range queries |
Prerequisites
Before starting Part 3, make sure you can:
- Write and compile a C++ program from scratch (Chapter 2.1)
-
Use
forloops and nested loops correctly (Chapter 2.2) -
Work with arrays and
vector<int>(Chapter 2.3)
Note: Chapter 3.1 (STL Essentials) is the first chapter of this part and will teach you
std::sort,map,set, and other key STL containers before you need them in later chapters.
Tips for This Part
- Chapter 3.2 (Prefix Sums) is the most frequently tested technique in Bronze. Make sure you can implement it from scratch in 5 minutes.
- Chapter 3.3 (Binary Search) introduces "binary search on the answer" — this is a Silver-level technique that separates good solutions from great ones.
- Don't skip the practice problems. Each chapter's problems are specifically chosen to build the intuition you need.
- After finishing Chapter 3.3, you have enough tools for most USACO Bronze problems. Try solving 5–10 Bronze problems before continuing.
🏆 USACO Tip: At USACO Bronze, the most common techniques are: simulation (Chapters 2.1–2.3), sorting (Chapter 3.3), and prefix sums (Chapter 3.2). If you master these, you can solve almost any Bronze problem.
Let's dive in!