span

🏆 C++ for Competitive Programming: A USACO Guide

From Zero to USACO Gold

The complete beginner's roadmap to competitive programming in C++, designed around USACO competition preparation.

No prior experience required. Written for clarity, depth, and contest readiness.

🎯 What Is This Book?

This book is a structured, self-contained course for students who want to learn competitive programming in C++ — specifically USACO (USA Computing Olympiad)

Unlike scattered online resources, this book gives you a single linear path: from writing your very first C++ program, through data structures and graph algorithms, all the way to solving USACO Gold problems with confidence. Every chapter builds on the previous one, with detailed worked examples, annotated C++ code, and SVG diagrams that make abstract algorithms visual and concrete.

If you've ever felt overwhelmed looking at USACO editorials, or if you know some programming but don't know what to learn next — this book was written for you.

✅ What You'll Learn

📊 Book Statistics

🗺️ Learning Path

🚀 Quick Start (5 Minutes)

Step 1: Install C++ Compiler

Windows: Install MSYS2, then: pacman -S mingw-w64-x86_64-gcc

macOS: xcode-select --install in Terminal

Linux: sudo apt install g++ build-essential

Verify: g++ --version (should show version ≥ 9)

Step 2: Get an Editor

VS Code + C/C++ extension + Code Runner extension

Step 3: Competition Template

Copy this to template.cpp — use it as your starting point for every problem:

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // freopen("problem.in", "r", stdin);   // uncomment for file I/O
    // freopen("problem.out", "w", stdout);

    // Your solution here

    return 0;
}

Step 4: Compile & Run

g++ -o sol solution.cpp -std=c++17 -O2 -Wall
./sol < input.txt

Step 5: Start Reading

Go to Chapter 2.1 and write your first C++ program. Then solve all practice problems before moving on. Don't skip the problems — that's where 80% of learning happens.

📚 How to Use This Book

The Reading Strategy That Works

1. Read actively: Code every example yourself. Don't just read — type it out.
2. Do the problems: Each chapter has 5–7 problems. Attempt every one before reading hints.
3. Read hints when stuck (after 20–30 minutes of genuine effort)
4. Review the Chapter Summary before moving on — it's a quick checklist.
5. Return to earlier chapters when a later chapter references them.

Practice Problems Guide

Each practice problem is labeled:

• 🟢 Easy — Directly applies the chapter's main technique
• 🟡 Medium — Requires combining ideas or a minor insight
• 🔴 Hard — Challenging; partial credit counts!
• 🏆 Challenge — Beyond chapter scope; try when ready

All hints are hidden by default (click to expand). Struggle first!

Reading Schedule

📖 Chapter Overview

Part 2: C++ Foundations (1–2 weeks)

Part 3: Core Data Structures (2–3 weeks)

Part 4: Greedy Algorithms (1 week)

Part 5: Graph Algorithms (2–3 weeks)

Part 6: Dynamic Programming (3–4 weeks)

Part 7: USACO Contest Guide (Read anytime)

Appendix & Reference

🔧 Setup Instructions

Compiler Setup

Verify with: g++ --version

Recommended Compile Flags

# Development (shows warnings, helpful for debugging)
g++ -o sol solution.cpp -std=c++17 -O2 -Wall -Wextra

# Contest (fast, silent)
g++ -o sol solution.cpp -std=c++17 -O2

Running with I/O Redirection

# Run with input file
./sol < input.txt

# Run and save output
./sol < input.txt > output.txt

# Compare output to expected
diff output.txt expected.txt

🌐 External Resources

🏅 Who Is This Book For?

✅ Middle school / high school students preparing for USACO Bronze through Silver

✅ Complete beginners with no prior programming experience (Part 2 starts from zero)

✅ Intermediate programmers who know Python or Java and want to learn C++ for competitive programming

✅ Self-learners who want a structured, complete curriculum instead of scattered tutorials

✅ Coaches and teachers looking for a comprehensive curriculum for their students

This book is NOT for:

• USACO Gold/Platinum (advanced data structures, network flow, geometry)
• General software engineering (no databases, web development, etc.)

🐄 Ready? Let's Begin!

Turn to Chapter 2.1 and write your first C++ program.

The path from complete beginner to USACO GOLD is roughly 200–400 hours of focused practice over 2–6 months. It won't always be easy — but every USACO GOLD and Gold competitor you admire started exactly where you are now.

The only way to get better is to write code, struggle with problems, and keep going. 🐄

Last updated: 2026 · Targets: USACO Bronze & GOLD · C++ Standard: C++17 35+ SVG diagrams · 150+ code examples · 130+ practice problems

Part 2: C++ Foundations

Before you can solve algorithmic problems, you need to speak the language. Part 2 is your crash course in C++ — from the very first program to functions, arrays, and vectors. You'll build the foundational skills needed for all later chapters.

What You'll Learn

Why C++?

Competitive programmers overwhelmingly choose C++ for two reasons:

1. Speed — C++ programs run faster than Python or Java, which matters when you have tight time limits (typically 1–2 seconds for up to 10^8 operations)
2. The STL — C++'s Standard Template Library gives you ready-made implementations of nearly every data structure and algorithm you'll ever need

Note: USACO accepts C++, Java, and Python. But C++ is by far the most common choice among top competitors, and this book focuses on it exclusively.

Tips for Part 2

• Type the code yourself. Don't copy-paste. Your fingers need to learn the syntax.
• Break things. Deliberately introduce errors and see what happens. Reading compiler errors is a skill.
• Run every example. Seeing output appear on screen cements understanding far better than just reading.

Let's dive in!

Chapter 2.1: Your First C++ Program

📝 Before You Continue: This is the very first chapter — no prerequisites! You don't need to have any programming experience. Just work through this chapter from top to bottom and you'll write your first real C++ program by the end.

Welcome! By the end of this chapter, you will have:

• Set up a working C++ environment (takes 5 minutes using an online compiler)
• Written, compiled, and run your first C++ program
• Understood what every single line of code does
• Learned about variables, data types, and input/output
• Solved 13 practice problems with full solutions

2.1.0 Setting Up Your Environment

Before writing any code, you need a place to write and run it. There are two options: online compilers (recommended for beginners — no installation required) and local setup (optional, for when you want to work offline).

Option A: Online Compilers (Recommended — Start Here!)

You only need a web browser. Open any of these sites:

Using Ideone (simplest for beginners):

1. Go to ideone.com
2. Select "C++17 (gcc 8.3)" from the language dropdown
3. Paste your code in the text area
4. Click the green "Run" button
5. See output in the bottom panel

That's it! No installation, no configuration.

Option B: Using CLion (Recommended Local IDE)

If you want to write and run C++ code offline on your own computer, we highly recommend CLion — a professional C/C++ IDE by JetBrains. It features intelligent code completion, one-click build & run, and a built-in debugger, all of which will significantly boost your productivity.

💡 Free for Students! CLion is a paid product, but JetBrains offers a free educational license for students. Simply apply with your .edu email on the JetBrains Student License page.

Installation Steps:

Step 1: Install a C++ Compiler (CLion requires an external compiler)

Step 2: Install CLion

1. Go to the CLion download page and download the installer for your OS
2. Run the installer and follow the prompts (keep the default options)
3. On first launch, choose "Activate" → sign in with your JetBrains student account, or start a free 30-day trial

Step 3: Create Your First Project

1. Open CLion and click "New Project"
2. Select "C++ Executable" and set the Language standard to C++17
3. Click "Create" — CLion will automatically generate a project with a main.cpp file
4. Write your code in main.cpp, then click the green ▶ Run button in the top-right corner to compile and run
5. The output will appear in the "Run" panel at the bottom

🔧 CLion Auto-Detects Compilers: On first launch, CLion automatically scans for installed compilers (GCC / Clang / MSVC). If detection succeeds, you'll see a green checkmark ✅ in Settings → Build → Toolchains. If not detected, verify that the compiler from Step 1 is correctly installed and added to your PATH.

Useful CLion Features for Competitive Programming:

• Built-in Terminal: The Terminal tab at the bottom lets you type test input directly
• Debugger: Set breakpoints, step through code line by line, and inspect variable values — an essential tool for tracking down bugs
• Code Formatting: Ctrl + Alt + L (Mac: Cmd + Option + L) automatically tidies up your code indentation

How to Compile and Run (Local)

Once you have g++ installed, here's how to compile and run:

g++ -o hello hello.cpp -std=c++17

Let's break down that command character by character:

Then to run it:

./hello        # Linux/Mac: ./ means "in current directory"
hello.exe      # Windows (the .exe is added automatically)

🤔 Why ./hello and not just hello? On Linux/Mac, the system won't run programs from the current folder by default (for security). The ./ explicitly says "look in the current directory."

2.1.1 Hello, World!

Every programming journey starts the same way. Here is the simplest complete C++ program:

#include <iostream>    // tells the compiler we want to use input/output

int main() {           // every C++ program starts executing from main()
    std::cout << "Hello, World!" << std::endl;  // print to the screen
    return 0;          // 0 = success, program ended normally
}

Run it, and you should see:

Hello, World!

What every line means:

Line 1: #include <iostream> This is a preprocessor directive — an instruction that runs before the actual compilation. It says "copy-paste the contents of the iostream library into my program." The iostream library provides cin (read input) and cout (print output). Without this line, your program can't print anything.

Think of it like: before you can cook, you need to bring the ingredients into the kitchen.

Line 3: int main() This declares the main function — the starting point of every C++ program. When you run a C++ program, the computer always starts executing from the first line inside main(). The int means this function returns an integer (the exit code). Every C++ program must have exactly one main.

Line 4: std::cout << "Hello, World!" << std::endl; This prints text. Let's break it down:

• std::cout — the "console output" stream (think of it as the screen)
• << — the "put into" operator; sends data into the stream
• "Hello, World!" — the text to print (the quotes are not printed)
• << std::endl — adds a newline (like pressing Enter)
• ; — every statement in C++ ends with a semicolon

Line 5: return 0; Exits main and tells the operating system the program finished successfully. (A non-zero return would signal an error.)

The Compilation Pipeline

Visual: The Compilation Pipeline

The diagram above shows the three-stage journey from source code to executable: your .cpp file is fed to the g++ compiler, which produces a runnable binary. Understanding this pipeline helps debug compilation errors before they happen.

2.1.2 The Competitive Programmer's Template

When solving USACO problems, you'll use a standard template. Here it is, fully explained:

#include <bits/stdc++.h>      // "batteries included" — includes ALL standard libraries
using namespace std;           // lets us write cout instead of std::cout

int main() {
    ios_base::sync_with_stdio(false);  // disables syncing C and C++ I/O (faster)
    cin.tie(NULL);                      // unties cin from cout (faster input)

    // Your solution code goes here

    return 0;
}

Why #include <bits/stdc++.h>?

This is a GCC-specific header that includes every standard library at once. Instead of writing:

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
// ... 20 more lines

You write one line. In competitive programming, this is universally accepted and saves time.

Note: bits/stdc++.h only works with GCC (the compiler USACO judges use). It's fine for competitive programming, but don't use it in production software.

Why using namespace std;?

The standard library puts everything inside a namespace called std. Without this line, you'd write std::cout, std::vector, std::sort everywhere. With using namespace std;, you write cout, vector, sort — much cleaner.

The I/O Speed Lines

ios_base::sync_with_stdio(false);
cin.tie(NULL);

These two lines make cin and cout much faster. Without them, reading large inputs can be 10× slower and cause "Time Limit Exceeded" (TLE) even if your algorithm is correct. Always include them.

🐛 Common Bug: After using these speed lines, don't mix cin/cout with scanf/printf. Pick one style.

2.1.3 Variables and Data Types

A variable is a named location in memory that stores a value. In C++, every variable has a type — the type tells the computer how much memory to reserve and what kind of data will go in it.

🧠 Mental Model: Variables are like labeled boxes

When you write:   int score = 100;

The computer does three things:
  1. Creates a box big enough to hold an integer (4 bytes)
  2. Puts the label "score" on the box
  3. Puts the number 100 inside the box

The Essential Types for Competitive Programming

#include <bits/stdc++.h>
using namespace std;

int main() {
    // int: whole numbers, range: -2,147,483,648 to +2,147,483,647 (about ±2 billion)
    int apples = 42;
    int temperature = -5;

    // long long: big whole numbers, range: about ±9.2 × 10^18
    long long population = 7800000000LL;  // the LL suffix means "this is a long long literal"
    long long trillion = 1000000000000LL;

    // double: decimal/fractional numbers
    double pi = 3.14159265358979;
    double percentage = 99.5;

    // bool: true or false only
    bool isRaining = true;
    bool finished = false;

    // char: a single character (stored as a number 0-255)
    char grade = 'A';     // single quotes for characters
    char newline = '\n';  // special: newline character

    // string: a sequence of characters
    string name = "Alice";         // double quotes for strings
    string greeting = "Hello!";

    // Print them all:
    cout << "Apples: " << apples << "\n";
    cout << "Population: " << population << "\n";
    cout << "Pi: " << pi << "\n";
    cout << "Is raining: " << isRaining << "\n";  // prints 1 for true, 0 for false
    cout << "Grade: " << grade << "\n";
    cout << "Name: " << name << "\n";

    return 0;
}

Visual: C++ Data Types Reference

Choosing the Right Type

Variable Naming Rules

Variable names follow strict rules in C++. Getting these right is essential — bad names lead to bugs, and illegal names won't compile at all.

The Formal Rules (Enforced by the Compiler)

✅ Legal names must:

• Start with a letter (a-z, A-Z) or underscore _
• Contain only letters, digits (0-9), and underscores
• Not be a C++ reserved keyword

❌ These will NOT compile:

⚠️ Case sensitive! score, Score, and SCORE are three completely different variables. This is a common source of bugs — be consistent.

Common Naming Styles

There are several widely-used naming conventions in C++. You don't have to pick one for competitive programming, but knowing them helps you read other people's code:

In competitive programming, camelCase and single-letter names are most common. In production code at companies, snake_case or camelCase are standard depending on the style guide.

Best Practices for Naming

1. Be descriptive — make the purpose clear from the name:

// ✅ Good — instantly clear what each variable stores
int numCows = 5;
long long totalMilk = 0;
string cowName = "Bessie";
int maxScore = 100;

// ❌ Bad — legal but confusing
int x = 5;            // What is x? Count? Index? Value?
long long t = 0;      // What is t? Time? Total? Temporary?
string n = "Bessie";  // n usually means "number" — misleading for a name!

2. Use conventional single-letter names only when the meaning is obvious:

// ✅ Acceptable — these are universally understood conventions
for (int i = 0; i < n; i++) { ... }    // i, j, k for loop indices
int n, m;                                // n = count, m = second dimension
cin >> n >> m;                           // in competitive programming, everyone does this

// ❌ Confusing — single letters with no clear convention
int q = 5;   // Is q a count? A query? A coefficient?
char z = 'A'; // Why z?

3. Constants should be ALL_CAPS to stand out:

const int MAX_N = 200005;        // maximum array size
const int MOD = 1000000007;      // modular arithmetic constant
const long long INF = 1e18;      // "infinity" for comparisons
const double PI = 3.14159265359; // mathematical constant

4. Avoid names that look too similar to each other:

// ❌ Easy to mix up
int total1 = 10;
int totall = 20;  // is this "total-L" or "total-1" with a typo?

int O = 0;        // the letter O looks like the digit 0
int l = 1;        // lowercase L looks like the digit 1

// ✅ Better alternatives
int totalA = 10;
int totalB = 20;

5. Don't start names with underscores followed by uppercase letters:

// ❌ Technically compiles, but reserved by the C++ standard
int _Score = 100;   // names like _X are reserved for the compiler/library
int __value = 42;   // double underscore is ALWAYS reserved

// ✅ Safe alternatives
int score = 100;
int myValue = 42;

Naming in Competitive Programming vs. Production Code

💡 For this book: We'll use a mix — descriptive names for clarity in explanations, but shorter names when solving problems under time pressure. The important thing is: you should always be able to look at a variable name and immediately know what it stores.

Deep Dive: char, string, and Character-Integer Conversions

Earlier in this chapter we briefly introduced char and string. Since many USACO problems involve character processing, digit extraction, and string manipulation, let's take a deeper look at these essential types.

char and ASCII — Every Character is a Number

A char in C++ is stored as a 1-byte integer (0–255). Each character is mapped to a number according to the ASCII table (American Standard Code for Information Interchange). You don't need to memorize the whole table, but knowing a few key ranges is extremely useful:

 Key relationships:
 • 'a' - 'A' = 32     (difference between lower and upper case)
 • '0' has ASCII value 48 (not 0!)
 • Digits, uppercase letters, and lowercase letters
   are each in CONSECUTIVE ranges

#include <bits/stdc++.h>
using namespace std;

int main() {
    char ch = 'A';

    // A char IS an integer — you can print its numeric value
    cout << ch << "\n";        // prints: A  (as character)
    cout << (int)ch << "\n";   // prints: 65 (its ASCII value)

    // You can do arithmetic on chars!
    char next = ch + 1;       // 'A' + 1 = 66 = 'B'
    cout << next << "\n";     // prints: B

    // Compare chars (compares their ASCII values)
    cout << ('a' < 'z') << "\n";   // 1 (true, because 97 < 122)
    cout << ('A' < 'a') << "\n";   // 1 (true, because 65 < 97)

    return 0;
}

char ↔ int Conversions — The Most Common Technique

In competitive programming, you constantly need to convert between character digits and integer values. Here's the complete guide:

1. Digit character → Integer value (e.g., '7' → 7)

char ch = '7';
int digit = ch - '0';    // '7' - '0' = 55 - 48 = 7
cout << digit << "\n";   // prints: 7

// This works because digit characters '0'~'9' have consecutive ASCII values:
// '0'=48, '1'=49, ..., '9'=57
// So ch - '0' gives the actual numeric value (0~9)

2. Integer value → Digit character (e.g., 7 → '7')

int digit = 7;
char ch = '0' + digit;   // 48 + 7 = 55 = '7'
cout << ch << "\n";      // prints: 7 (as the character '7')

// Works for digits 0~9 only

3. Uppercase ↔ Lowercase conversion

char upper = 'C';
char lower = upper + 32;           // 'C'(67) + 32 = 'c'(99)
cout << lower << "\n";            // prints: c

// More readable approach using the difference:
char lower2 = upper - 'A' + 'a';  // 'C'-'A' = 2, 'a'+2 = 'c'
cout << lower2 << "\n";           // prints: c

// Reverse: lowercase → uppercase
char ch = 'f';
char upper2 = ch - 'a' + 'A';    // 'f'-'a' = 5, 'A'+5 = 'F'
cout << upper2 << "\n";           // prints: F

// Using built-in functions (recommended for clarity):
cout << (char)toupper('g') << "\n";  // prints: G
cout << (char)tolower('G') << "\n";  // prints: g

4. Check character types (very useful in USACO)

char ch = '5';

// Check if digit
if (ch >= '0' && ch <= '9') {
    cout << "It's a digit!\n";
}

// Check if uppercase letter
if (ch >= 'A' && ch <= 'Z') {
    cout << "Uppercase!\n";
}

// Check if lowercase letter
if (ch >= 'a' && ch <= 'z') {
    cout << "Lowercase!\n";
}

// Or use built-in functions:
// isdigit(ch), isupper(ch), islower(ch), isalpha(ch), isalnum(ch)
if (isdigit(ch)) cout << "Digit!\n";
if (isalpha(ch)) cout << "Letter!\n";

5. A Classic Pattern: Extract Digits from a String

string s = "abc123def";
int sum = 0;
for (char ch : s) {
    if (ch >= '0' && ch <= '9') {
        sum += ch - '0';  // convert digit char to int and add
    }
}
cout << "Sum of digits: " << sum << "\n";  // 1+2+3 = 6

string Detailed Guide

string is C++'s built-in text type. Unlike a single char, a string holds a sequence of characters and provides many useful operations.

Basic operations:

#include <bits/stdc++.h>
using namespace std;

int main() {
    // Creating strings
    string s1 = "Hello";
    string s2 = "World";
    string empty = "";           // empty string
    string repeated(5, 'x');     // "xxxxx" — 5 copies of 'x'

    // Length
    cout << s1.size() << "\n";   // 5 (same as s1.length())

    // Concatenation (joining strings)
    string s3 = s1 + " " + s2;  // "Hello World"
    s1 += "!";                   // s1 is now "Hello!"

    // Access individual characters (0-indexed, just like arrays)
    cout << s3[0] << "\n";      // 'H'
    cout << s3[6] << "\n";      // 'W'

    // Modify individual characters
    s3[0] = 'h';                // "hello World"

    // Comparison (lexicographic, i.e., dictionary order)
    cout << ("apple" < "banana") << "\n";   // 1 (true)
    cout << ("abc" == "abc") << "\n";       // 1 (true)
    cout << ("abc" < "abd") << "\n";        // 1 (true, compares char by char)

    return 0;
}

Iterating over a string:

string s = "USACO";

// Method 1: index-based loop
for (int i = 0; i < (int)s.size(); i++) {
    cout << s[i] << " ";  // U S A C O
}
cout << "\n";

// Method 2: range-based for loop (cleaner)
for (char ch : s) {
    cout << ch << " ";    // U S A C O
}
cout << "\n";

// Method 3: range-based with reference (for modifying in-place)
for (char& ch : s) {
    ch = tolower(ch);     // convert each char to lowercase
}
cout << s << "\n";        // "usaco"

Useful string functions:

string s = "Hello, World!";

// Substring: s.substr(start, length)
string sub = s.substr(7, 5);     // "World" (starting at index 7, take 5 chars)
string sub2 = s.substr(7);       // "World!" (from index 7 to end)

// Find: s.find("text") — returns index or string::npos if not found
size_t pos = s.find("World");    // 7  (size_t, not int!)
if (s.find("xyz") == string::npos) {
    cout << "Not found!\n";
}

// Append
s.append(" Hi");                 // "Hello, World! Hi"
// or equivalently: s += " Hi";

// Insert
s.insert(5, "!!");               // "Hello!!, World! Hi"

// Erase: s.erase(start, count)
s.erase(5, 2);                   // removes 2 chars starting at index 5 → "Hello, World! Hi"

// Replace: s.replace(start, count, "new text")
string msg = "I love cats";
msg.replace(7, 4, "dogs");       // "I love dogs"

Reading strings from input:

// cin >> reads ONE WORD (stops at whitespace)
string word;
cin >> word;    // input "Hello World" → word = "Hello"

// getline reads the ENTIRE LINE (including spaces)
string line;
getline(cin, line);   // input "Hello World" → line = "Hello World"

// ⚠️ Remember: after cin >>, call cin.ignore() before getline!
int n;
cin >> n;
cin.ignore();          // consume the leftover '\n'
string fullLine;
getline(cin, fullLine); // now this reads correctly

Converting between string and numbers:

// String → Integer
string numStr = "42";
int num = stoi(numStr);         // stoi = "string to int" → 42
long long big = stoll("123456789012345"); // stoll = "string to long long"

// String → Double
double d = stod("3.14");       // stod = "string to double" → 3.14

// Integer → String
int x = 255;
string s = to_string(x);       // "255"
string s2 = to_string(3.14);   // "3.140000"

char Arrays (C-Style Strings) — Know They Exist

In C (and old C++ code), strings were stored as arrays of char ending with a special null character '\0'. You'll rarely need these in competitive programming (use string instead), but you should recognize them:

// C-style string (char array)
char greeting[] = "Hello";  // actually stores: H e l l o \0 (6 chars!)
// The '\0' (null terminator) marks the end of the string

// WARNING: you must ensure the array is big enough to hold the string + '\0'
char name[20];              // can hold up to 19 characters + '\0'

// Reading into a char array (rarely needed)
// cin >> name;             // works, but limited by array size
// scanf("%s", name);       // C-style, also works

// Converting between char array and string
string s = greeting;        // char array → string (automatic)
// string → char array: use s.c_str() to get a const char*

Why string is better than char[] for competitive programming:

⚡ Pro Tip for USACO: Always use string unless a problem specifically requires char arrays. String operations are cleaner, safer, and easier to debug. The only common use of char arrays in competitive programming is when reading very large inputs with scanf/printf for speed — but with sync_with_stdio(false), string + cin/cout is fast enough for 99% of USACO problems.

Quick Reference: Character/String Cheat Sheet

⚠️ Integer Overflow — The #1 Bug in Competitive Programming

What happens when a number gets too big for its type?

// Imagine int as a dial that goes from -2,147,483,648 to 2,147,483,647
// When you go past the maximum, it WRAPS AROUND to the minimum!

int x = 2147483647;  // maximum int value
cout << x << "\n";   // prints: 2147483647
x++;                 // add 1... what happens?
cout << x << "\n";   // prints: -2147483648  (OVERFLOW! Wrapped around!)

This is like an old car odometer that hits 999999 and rolls back to 000000. The number wraps around.

How to avoid overflow:

int a = 1000000000;    // 1 billion — fits in int
int b = 1000000000;    // 1 billion — fits in int
// int wrong = a * b;  // OVERFLOW! a*b = 10^18, doesn't fit in int

long long correct = (long long)a * b;  // Cast one to long long before multiplying
cout << correct << "\n";  // 1000000000000000000 ✓

// Rule of thumb: if N can be up to 10^9 and you multiply two such values, use long long

⚡ Pro Tip: When in doubt, use long long. It's slightly slower than int but prevents overflow bugs that are very hard to spot.

2.1.4 Input and Output with cin and cout

Printing Output with cout

int score = 95;
string name = "Alice";

cout << "Score: " << score << "\n";     // Score: 95
cout << name << " got " << score << "\n"; // Alice got 95

// "\n" vs endl
cout << "Line 1" << "\n";   // fast — just a newline character
cout << "Line 2" << endl;   // slow — flushes buffer AND adds newline

⚡ Pro Tip: Always use "\n" instead of endl. The endl flushes the output buffer which is much slower. In problems with lots of output, using endl can cause Time Limit Exceeded!

Reading Input with cin

int n;
cin >> n;    // reads one integer from input

string s;
cin >> s;    // reads one word (stops at whitespace — spaces, tabs, newlines)

double x;
cin >> x;    // reads a decimal number

cin >> automatically skips whitespace between values. This means spaces, tabs, and newlines are all treated the same way. So these two inputs are read identically:

Input style 1 (all on one line):   42 hello 3.14
Input style 2 (on separate lines):
42
hello
3.14

Both work with:

int a; string b; double c;
cin >> a >> b >> c;  // reads all three regardless of formatting

Reading Multiple Values — The Most Common USACO Pattern

USACO problems almost always start with: "Read N, then read N values." Here's how:

Typical USACO input:
5          ← first line: N (the number of items)
10 20 30 40 50   ← next line(s): the N items

int n;
cin >> n;              // read N

for (int i = 0; i < n; i++) {
    int x;
    cin >> x;          // read each item
    cout << x * 2 << "\n";  // process it
}

Complexity Analysis:

• Time: O(N) — read N numbers and process each one in O(1)
• Space: O(1) — only one variable x, no storage of all data

For the input 5\n10 20 30 40 50, this would print:

20
40
60
80
100

Reading a Full Line (Including Spaces)

Sometimes input has multiple words on a line. cin >> only reads one word at a time, so use getline:

string fullName;
getline(cin, fullName);  // reads the entire line, including spaces
cout << "Name: " << fullName << "\n";

🐛 Common Bug: Mixing cin >> and getline can cause problems. After cin >> n, there's a leftover \n in the buffer. If you then call getline, it will read that empty newline instead of the next line. Fix: call cin.ignore() after cin >> before using getline.

Controlling Decimal Output

double y = 3.14159;

cout << y << "\n";                            // 3.14159 (default)
cout << fixed << setprecision(2) << y << "\n"; // 3.14 (exactly 2 decimal places)
cout << fixed << setprecision(6) << y << "\n"; // 3.141590 (6 decimal places)

2.1.5 Basic Arithmetic

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a = 17, b = 5;

    cout << a + b << "\n";   // 22  (addition)
    cout << a - b << "\n";   // 12  (subtraction)
    cout << a * b << "\n";   // 85  (multiplication)
    cout << a / b << "\n";   // 3   (INTEGER division — truncates toward zero!)
    cout << a % b << "\n";   // 2   (modulo — the REMAINDER after division)

    // Integer division example:
    // 17 ÷ 5 = 3 remainder 2
    // So: 17 / 5 = 3  and  17 % 5 = 2

    double x = 17.0, y = 5.0;
    cout << x / y << "\n";   // 3.4 (real division when operands are doubles)

    // Shorthand assignment operators:
    int n = 10;
    n += 5;    // same as: n = n + 5   → n is now 15
    n -= 3;    // same as: n = n - 3   → n is now 12
    n *= 2;    // same as: n = n * 2   → n is now 24
    n /= 4;    // same as: n = n / 4   → n is now 6
    n++;       // same as: n = n + 1   → n is now 7
    n--;       // same as: n = n - 1   → n is now 6

    cout << n << "\n";  // 6

    return 0;
}

🤔 Why does integer division truncate?

When both operands are integers, C++ does integer division — it discards the fractional part. 17 / 5 gives 3, not 3.4. This is intentional and very useful (e.g., to find which "group" something falls into).

// How many full hours in 200 minutes?
int minutes = 200;
int hours = minutes / 60;     // 200 / 60 = 3 (not 3.33...)
int remaining = minutes % 60; // 200 % 60 = 20
cout << hours << " hours and " << remaining << " minutes\n";  // 3 hours and 20 minutes

// To get decimal division, at least ONE operand must be a double:
int a = 7, b = 2;
cout << a / b << "\n";           // 3    (integer division)
cout << (double)a / b << "\n";   // 3.5  (cast a to double first)
cout << a / (double)b << "\n";   // 3.5  (cast b to double)
cout << 7.0 / 2 << "\n";        // 3.5  (literal 7.0 is a double)

2.1.6 Your First USACO-Style Program

Let's put everything together and write a complete program that reads input and produces output — just like a real USACO problem.

Problem: Read two integers N and M. Print their sum, difference, product, integer quotient, and remainder.

Thinking through it:

1. We need two variables to store N and M
2. We use cin to read them
3. We use cout to print each result
4. Since N and M could be large, should we use long long? Let's be safe.

💡 Beginner's Problem-Solving Flow:

When facing a problem, don't rush to write code. First think through the steps in plain language:

1. Understand the problem: What is the input? What is the output? What are the constraints?
2. Work through an example by hand: Use the sample input, manually compute the output, confirm you understand the problem
3. Think about data ranges: How large can N and M be? Could there be overflow?
4. Write pseudocode: Read → Compute → Output
5. Translate to C++: Convert pseudocode to real code line by line

This problem: read two numbers → perform five operations → output five results. Very straightforward!

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long n, m;
    cin >> n >> m;  // read both numbers on one line

    cout << n + m << "\n";  // sum
    cout << n - m << "\n";  // difference
    cout << n * m << "\n";  // product
    cout << n / m << "\n";  // integer quotient
    cout << n % m << "\n";  // remainder

    return 0;
}

Complexity Analysis:

• Time: O(1) — only a fixed number of arithmetic operations
• Space: O(1) — only two variables

Sample Input:

17 5

Sample Output:

22
12
85
3
2

⚠️ Common Mistakes in Chapter 2.1

Chapter Summary

📌 Key Takeaways

❓ FAQ

Q1: Does bits/stdc++.h slow down compilation?

A: Yes, compilation time may increase by 1-2 seconds. But in contests, compilation time is not counted toward the time limit, so it doesn't affect results. Don't use it in production projects.

Q2: Which should I default to — int or long long?

A: Rule of thumb — when in doubt, use long long. It's slightly slower than int (nearly imperceptible on modern CPUs), but prevents overflow. Especially note: if two int values are multiplied, the result may need long long.

Q3: Why can't I use scanf/printf in USACO?

A: You actually can! But after adding sync_with_stdio(false), you cannot mix cin/cout with scanf/printf. Beginners are advised to stick with cin/cout — it's safer.

Q4: Can I omit return 0;?

A: In C++11 and later, if main() reaches the end without a return, the compiler automatically returns 0. So technically it can be omitted, but writing it is clearer.

Q5: My code runs correctly locally, but gets Wrong Answer (WA) on the USACO judge. What could be wrong?

A: The three most common reasons: ① Integer overflow (used int when long long was needed); ② Not handling all edge cases; ③ Wrong output format (extra or missing spaces/newlines).

🔗 Connections to Later Chapters

• Chapter 2.2 (Control Flow) builds on this chapter by adding if/else conditionals and for/while loops, enabling you to handle "repeat N times" tasks
• Chapter 2.3 (Functions & Arrays) introduces functions (organizing code into reusable blocks) and arrays (storing a collection of data) — core tools for solving USACO problems
• Chapter 3.1 (STL Essentials) introduces STL tools like vector and sort, greatly simplifying the logic you write manually in this chapter
• The integer overflow prevention techniques learned in this chapter will appear throughout the book, especially in Chapter 3.2 (Prefix Sums) and Chapters 6.1–6.3 (DP)

Practice Problems

Work through all problems in order — they get progressively harder. Each has a complete solution you can reveal after trying it yourself.

🌡️ Warm-Up Problems

These problems only require 1-3 lines of new code each. They're meant to help you practice typing C++ and running programs.

Warm-up 2.1.1 — Personal Greeting Write a program that prints exactly this (with your own name):

Hello, Alice!
My favorite number is 7.
I am learning C++.

(You can hardcode all values — no input needed.)

#include <bits/stdc++.h>
using namespace std;

int main() {
    cout << "Hello, Alice!\n";
    cout << "My favorite number is 7.\n";
    cout << "I am learning C++.\n";
    return 0;
}

Warm-up 2.1.2 — Five Lines Print the numbers 1 through 5, each on its own line. Use exactly 5 separate cout statements (no loops yet — we cover loops in Chapter 2.2).

#include <bits/stdc++.h>
using namespace std;

int main() {
    cout << 1 << "\n";
    cout << 2 << "\n";
    cout << 3 << "\n";
    cout << 4 << "\n";
    cout << 5 << "\n";
    return 0;
}

Warm-up 2.1.3 — Double It Read one integer from input. Print that integer multiplied by 2.

Sample Input: 7 Sample Output: 14

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    cout << n * 2 << "\n";
    return 0;
}

Warm-up 2.1.4 — Sum of Two Read two integers on the same line. Print their sum.

Sample Input: 15 27 Sample Output: 42

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    cout << a + b << "\n";
    return 0;
}

Warm-up 2.1.5 — Say Hi Read a single word (a first name, no spaces). Print Hi, [name]!

Sample Input: Bob Sample Output: Hi, Bob!

#include <bits/stdc++.h>
using namespace std;

int main() {
    string name;
    cin >> name;
    cout << "Hi, " << name << "!\n";
    return 0;
}

🏋️ Core Practice Problems

These problems require combining input, arithmetic, and output. Think through the math before coding.

Problem 2.1.6 — Age in Days Read a person's age in whole years. Print their approximate age in days (use 365 days per year, ignore leap years).

Sample Input: 15 Sample Output: 5475

#include <bits/stdc++.h>
using namespace std;

int main() {
    int years;
    cin >> years;
    cout << years * 365 << "\n";
    return 0;
}

Problem 2.1.7 — Seconds Converter Read a number of seconds S (1 ≤ S ≤ 10^9). Convert it to hours, minutes, and remaining seconds.

Sample Input: 3661 Sample Output:

1 hours
1 minutes
1 seconds

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long s;
    cin >> s;

    long long hours = s / 3600;         // 3600 seconds per hour
    long long remaining = s % 3600;     // seconds left after removing full hours
    long long minutes = remaining / 60; // 60 seconds per minute
    long long seconds = remaining % 60; // seconds left after removing full minutes

    cout << hours << " hours\n";
    cout << minutes << " minutes\n";
    cout << seconds << " seconds\n";

    return 0;
}

Problem 2.1.8 — Rectangle Read the length L and width W of a rectangle. Print its area and perimeter.

Sample Input: 6 4 Sample Output:

Area: 24
Perimeter: 20

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long L, W;
    cin >> L >> W;

    cout << "Area: " << L * W << "\n";
    cout << "Perimeter: " << 2 * (L + W) << "\n";

    return 0;
}

Problem 2.1.9 — Temperature Converter Read a temperature in Celsius. Print the equivalent in Fahrenheit. Formula: F = C × 9/5 + 32

Sample Input: 100 Sample Output: 212.00

#include <bits/stdc++.h>
using namespace std;

int main() {
    double celsius;
    cin >> celsius;

    double fahrenheit = celsius * 9.0 / 5.0 + 32.0;

    cout << fixed << setprecision(2) << fahrenheit << "\n";

    return 0;
}

Problem 2.1.10 — Coin Counter Read four integers: the number of quarters (25¢), dimes (10¢), nickels (5¢), and pennies (1¢). Print the total value in cents.

Sample Input:

3 2 1 4

(3 quarters, 2 dimes, 1 nickel, 4 pennies)

Sample Output: 104

#include <bits/stdc++.h>
using namespace std;

int main() {
    int quarters, dimes, nickels, pennies;
    cin >> quarters >> dimes >> nickels >> pennies;

    int total = quarters * 25 + dimes * 10 + nickels * 5 + pennies * 1;

    cout << total << "\n";

    return 0;
}

🏆 Challenge Problems

These require more thought — especially around data types and problem-solving.

Challenge 2.1.11 — Overflow Detector Read two integers A and B (each up to 10^9). Compute their product TWO ways: as an int and as a long long. Print both results. Observe the difference when overflow occurs.

Sample Input: 1000000000 3 Sample Output:

int product: -1294967296
long long product: 3000000000

(The int result is wrong due to overflow; long long is correct.)

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long a, b;
    cin >> a >> b;

    // Cast to int FIRST to force integer overflow
    int int_product = (int)a * (int)b;

    // Long long multiplication — no overflow for values up to 10^9
    long long ll_product = a * b;

    cout << "int product: " << int_product << "\n";
    cout << "long long product: " << ll_product << "\n";

    return 0;
}

Challenge 2.1.12 — USACO-Style Large Multiply You're given two integers N and M (1 ≤ N, M ≤ 10^9). Print their product. (This seems simple, but requires long long.)

Sample Input: 1000000000 1000000000 Sample Output: 1000000000000000000

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long n, m;
    cin >> n >> m;

    cout << n * m << "\n";

    return 0;
}

Challenge 2.1.13 — Quadrant Problem (USACO 2016 February Bronze) Read two non-zero integers x and y. Determine which quadrant of the coordinate plane the point (x, y) is in:

• Quadrant 1: x > 0 and y > 0
• Quadrant 2: x < 0 and y > 0
• Quadrant 3: x < 0 and y < 0
• Quadrant 4: x > 0 and y < 0

Print just the number: 1, 2, 3, or 4.

Sample Input 1: 3 5 → Output: 1 Sample Input 2: -1 2 → Output: 2 Sample Input 3: -4 -7 → Output: 3 Sample Input 4: 8 -3 → Output: 4

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int x, y;
    cin >> x >> y;

    if (x > 0 && y > 0) {
        cout << 1 << "\n";
    } else if (x < 0 && y > 0) {
        cout << 2 << "\n";
    } else if (x < 0 && y < 0) {
        cout << 3 << "\n";
    } else {  // x > 0 && y < 0
        cout << 4 << "\n";
    }

    return 0;
}

Chapter 2.2: Control Flow

📝 Prerequisites: Chapter 2.1 (variables, cin/cout, basic arithmetic)

2.2.0 What is "Control Flow"?

So far, every program we wrote ran top to bottom — line 1, line 2, line 3, done. Like reading a book straight through.

But real programs need to make decisions and repeat things. That's what "control flow" means — controlling the flow (order) of execution.

Think of it like a "Choose Your Own Adventure" book:

• Sometimes you're told "if you want to fight the dragon, turn to page 47; otherwise turn to page 52"
• Sometimes you're told "repeat this section until you escape the dungeon"

C++ gives us exactly this with:

• if/else — make decisions based on conditions
• for/while loops — repeat a section of code

Here's a visual overview:

In the loop diagram: the program keeps going back to Step 2 until the condition becomes false, then it exits to Step 3.

2.2.1 The if Statement

The if statement lets your program make a decision: "if this condition is true, do this thing."

Basic if

#include <bits/stdc++.h>
using namespace std;

int main() {
    int score;
    cin >> score;

    if (score >= 90) {
        cout << "Excellent!\n";
    }

    cout << "Done.\n";  // always runs regardless of score
    return 0;
}

If score is 95: prints Excellent! then Done. If score is 80: prints only Done. (the if-block is skipped)

if / else

int score;
cin >> score;

if (score >= 60) {
    cout << "Pass\n";
} else {
    cout << "Fail\n";
}

The else block runs only when the if condition is false. Exactly one of the two blocks will run.

if / else if / else Chains

When you have multiple conditions to check:

int score;
cin >> score;

if (score >= 90) {
    cout << "A\n";
} else if (score >= 80) {
    cout << "B\n";
} else if (score >= 70) {
    cout << "C\n";
} else if (score >= 60) {
    cout << "D\n";
} else {
    cout << "F\n";
}

C++ checks these conditions in order, from top to bottom, and runs the first one that's true. Once it runs one block, it skips all the remaining else if/else blocks.

So if score = 85:

1. Is 85 >= 90? No → skip
2. Is 85 >= 80? Yes → print "B", then jump past all the else-ifs

🤔 Why does this work? When we reach else if (score >= 80), we already know score < 90 (because if it were ≥ 90, the first condition would have caught it). Each else if implicitly assumes all the previous conditions were false.

Comparison Operators

Logical Operators (Combining Conditions)

int x, y;
cin >> x >> y;

if (x > 0 && y > 0) {
    cout << "Both positive\n";
}

if (x < 0 || y < 0) {
    cout << "At least one is negative\n";
}

bool done = false;
if (!done) {
    cout << "Still working...\n";
}

🐛 Common Bug: = vs ==

This is one of the most common mistakes for beginners (and even experienced programmers!):

int x = 5;

// DANGEROUS BUG:
if (x = 10) {   // This ASSIGNS 10 to x, doesn't compare!
                 // x becomes 10, and since 10 is nonzero, this is always TRUE
    cout << "x is 10\n";  // This ALWAYS runs, even though x started as 5!
}

// CORRECT:
if (x == 10) {  // This COMPARES x with 10
    cout << "x is 10\n";  // Only runs when x actually equals 10
}

The = operator assigns (stores a value). The == operator compares (checks if two values are equal). They look similar but do completely different things.

⚡ Pro Tip: Some programmers write 10 == x instead of x == 10 — if you accidentally type = instead of ==, it becomes 10 = x which is a compile error (you can't assign to a literal). This is called a "Yoda condition."

Nested if Statements

You can put if statements inside other if statements:

int age, income;
cin >> age >> income;

if (age >= 18) {
    cout << "Adult\n";
    if (income > 50000) {
        cout << "High income adult\n";
    } else {
        cout << "Standard income adult\n";
    }
} else {
    cout << "Minor\n";
}

Be careful: each else matches the nearest preceding if that doesn't already have an else.

2.2.2 The while Loop

A while loop repeats a block of code as long as its condition is true. When the condition becomes false, execution continues after the loop.

while (condition) {
    body (runs over and over)
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    int i = 1;             // 1. Initialize before the loop
    while (i <= 5) {       // 2. Check condition — if false, skip the loop
        cout << i << "\n"; // 3. Run the body
        i++;               // 4. Update — VERY IMPORTANT! Forget this → infinite loop
    }
    // After loop: i = 6, condition 6 <= 5 is false, loop exits
    return 0;
}

Output:

1
2
3
4
5

🐛 Common Bug: Infinite Loop

If you forget to update the variable (step 4 above), the condition never becomes false and the loop runs forever!

int i = 1;
while (i <= 5) {
    cout << i << "\n";
    // BUG: forgot i++ — this prints "1" forever!
}

If your program seems stuck, press Ctrl+C to stop it.

When to use while vs for

• Use while when you don't know in advance how many iterations you need
• Use for when you do know the count (we'll cover for next)

Classic while use case: read until a condition is met.

// Common USACO pattern: read until end of input
int x;
while (cin >> x) {    // cin >> x returns false when input runs out
    cout << x * 2 << "\n";
}

do-while Loop

A do-while loop always runs its body at least once, then checks the condition:

int n;
do {
    cin >> n;
} while (n <= 0);   // keep re-reading until user gives a positive number

This is useful when you want to execute something before checking whether to repeat. It's rare in competitive programming but worth knowing.

2.2.3 The for Loop

The for loop is the most used loop in competitive programming. It packages initialization, condition-check, and update into one clean line:

for (initialization; condition; update) {
    body
}

This is equivalent to:

initialization;
while (condition) {
    body
    update;
}

Visual: For Loop Flowchart

The flowchart above traces the execution: initialization runs once, then the condition is checked before every iteration. When false, the loop exits.

Common for Patterns

// Count from 0 to 9 (standard competitive programming pattern)
for (int i = 0; i < 10; i++) {
    cout << i << " ";
}
// Prints: 0 1 2 3 4 5 6 7 8 9

// Count from 1 to n (inclusive)
int n = 5;
for (int i = 1; i <= n; i++) {
    cout << i << " ";
}
// Prints: 1 2 3 4 5

// Count backwards
for (int i = 10; i >= 1; i--) {
    cout << i << " ";
}
// Prints: 10 9 8 7 6 5 4 3 2 1

// Count by steps of 2
for (int i = 0; i <= 10; i += 2) {
    cout << i << " ";
}
// Prints: 0 2 4 6 8 10

🧠 Loop Tracing: Understanding Exactly What Happens

When learning loops, trace through them manually. Here's how:

Code: for (int i = 0; i < 4; i++) cout << i * i << " ";

Practice tracing loops on paper before running them — it builds intuition and helps spot bugs.

The Most Common USACO Loop Pattern

Read N numbers and process each one:

int n;
cin >> n;

for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    // process x here
    cout << x * 2 << "\n";
}

⚡ Pro Tip: In competitive programming, for (int i = 0; i < n; i++) with 0-based indexing is standard. It matches how arrays are indexed (Chapter 2.3), so everything lines up neatly.

2.2.4 Nested Loops

You can put a loop inside another loop. The inner loop runs completely for each single iteration of the outer loop.

// Print a 4x4 multiplication table
for (int i = 1; i <= 4; i++) {         // outer: rows
    for (int j = 1; j <= 4; j++) {     // inner: columns
        cout << i * j << "\t";          // \t = tab character
    }
    cout << "\n";  // newline after each row
}

Output:

1   2   3   4
2   4   6   8
3   6   9   12
4   8   12  16

Tracing the first two rows:

i=1: j=1→print 1, j=2→print 2, j=3→print 3, j=4→print 4, then newline
i=2: j=1→print 2, j=2→print 4, j=3→print 6, j=4→print 8, then newline
...

⚠️ Nested Loop Time Complexity

💡 Why should you care about loop counts? In competitions, your program typically needs to finish within 1-2 seconds. A modern computer can execute roughly 10^8 to 10^9 simple operations per second. So if you can estimate how many times your loop body executes in total, you can determine whether it will exceed the time limit (TLE). This is the core idea behind "time complexity analysis" — we'll study it in greater depth in later chapters.

A single loop of N iterations does N operations. Two nested loops of N do N × N = N² operations.

If N = 1000 and you have two nested loops, that's 10^6 operations — fine. But if N = 100,000, that's 10^10 — too slow!

🧠 Quick Rule of Thumb: After seeing the range of N, use the table above to work backwards and determine the maximum number of nested loops you can afford. For example, N ≤ 10^5 → you can only use O(N) or O(N log N) algorithms; N ≤ 5000 → O(N²) is acceptable. This technique is extremely useful in USACO!

2.2.5 Switch Statements

When you have a variable and want to check many specific values, switch is cleaner than a long chain of if/else if:

int day;
cin >> day;

switch (day) {
    case 1:
        cout << "Monday\n";
        break;   // IMPORTANT: break exits the switch
    case 2:
        cout << "Tuesday\n";
        break;
    case 3:
        cout << "Wednesday\n";
        break;
    case 4:
        cout << "Thursday\n";
        break;
    case 5:
        cout << "Friday\n";
        break;
    case 6:
    case 7:
        cout << "Weekend!\n";  // cases 6 and 7 share this code
        break;
    default:
        cout << "Invalid day\n";  // runs if no case matches
}

When to use switch vs if-else

🐛 Common Bug: Forgetting break — Without break, execution "falls through" to the next case!

int x = 2;
switch (x) {
    case 1:
        cout << "one\n";
    case 2:
        cout << "two\n";   // this runs
    case 3:
        cout << "three\n"; // ALSO runs (fall-through!) because no break after case 2
}
// Output: two\nthree\n  (surprising!)

2.2.6 break and continue

break — Exit the Loop Immediately

// Find the first number divisible by 7 between 1 and 100
for (int i = 1; i <= 100; i++) {
    if (i % 7 == 0) {
        cout << "First multiple of 7: " << i << "\n";  // prints 7
        break;  // stop searching — we found it
    }
}

continue — Skip to the Next Iteration

// Print all numbers 1 to 10 except multiples of 3
for (int i = 1; i <= 10; i++) {
    if (i % 3 == 0) {
        continue;  // skip the rest of this iteration, go to i++
    }
    cout << i << " ";
}
// Output: 1 2 4 5 7 8 10

break in Nested Loops

break only exits the innermost loop. To exit multiple levels, use a flag variable:

bool found = false;
int target = 25;

for (int i = 0; i < 10 && !found; i++) {    // outer loop also checks !found
    for (int j = 0; j < 10; j++) {
        if (i * j == target) {
            cout << i << " * " << j << " = " << target << "\n";
            found = true;
            break;   // exits inner loop; outer loop exits too because of !found
        }
    }
}

2.2.7 Classic Loop Patterns in Competitive Programming

These patterns appear in nearly every USACO solution. Learn them cold.

Pattern 1: Read N Numbers, Compute Sum

int n;
cin >> n;

long long sum = 0;
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    sum += x;
}
cout << sum << "\n";

Complexity Analysis:

• Time: O(N) — iterate through N numbers, each processed in O(1)
• Space: O(1) — only one accumulator variable sum

Pattern 2: Find Maximum (and Minimum) in a List

int n;
cin >> n;

int maxVal, minVal;
cin >> maxVal;    // read first element
minVal = maxVal;  // initialize both max and min to first element

for (int i = 1; i < n; i++) {   // start from 2nd element (index 1)
    int x;
    cin >> x;
    if (x > maxVal) maxVal = x;
    if (x < minVal) minVal = x;
}

cout << "Max: " << maxVal << "\n";
cout << "Min: " << minVal << "\n";

Complexity Analysis:

• Time: O(N) — iterate through N numbers, each comparison in O(1)
• Space: O(1) — only two variables maxVal and minVal

🤔 Why initialize to the first element? Don't initialize max to 0! What if all numbers are negative? Initializing to the first element guarantees we start with a real value from the input.

Pattern 3: Count How Many Satisfy a Condition

int n;
cin >> n;

int count = 0;
for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    if (x % 2 == 0) {   // condition: even number
        count++;
    }
}
cout << "Even count: " << count << "\n";

Pattern 4: Print a Star Triangle Pattern

int n;
cin >> n;

for (int row = 1; row <= n; row++) {     // row goes from 1 to n
    for (int col = 1; col <= row; col++) { // print `row` stars per row
        cout << "*";
    }
    cout << "\n";  // newline after each row
}

For n=4, output:

*
**
***
****

Pattern 5: Compute Sum of Digits

int n;
cin >> n;

int digitSum = 0;
while (n > 0) {
    digitSum += n % 10;  // last digit
    n /= 10;             // remove last digit
}
cout << digitSum << "\n";

Tracing for n = 12345:

n=12345: digitSum += 5, n becomes 1234
n=1234:  digitSum += 4, n becomes 123
n=123:   digitSum += 3, n becomes 12
n=12:    digitSum += 2, n becomes 1
n=1:     digitSum += 1, n becomes 0
n=0: loop exits. digitSum = 15 ✓

2.2.8 Complete Example: USACO-Style Problem

Problem: You have N cows. Each cow has a milk production rating. Find the highest-rated cow's rating and count how many cows produce above-average milk.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    // We need to store all values to compare against the average
    // (We'll learn arrays/vectors in Chapter 2.3 — for now use two passes)

    // First pass: find sum and max
    long long sum = 0;
    int maxMilk = 0;
    vector<int> milk(n);   // store all values (preview of Chapter 2.3)

    for (int i = 0; i < n; i++) {
        cin >> milk[i];
        sum += milk[i];
        if (milk[i] > maxMilk) maxMilk = milk[i];
    }

    double avg = (double)sum / n;

    // Second pass: count above-average
    int aboveAvg = 0;
    for (int i = 0; i < n; i++) {
        if (milk[i] > avg) aboveAvg++;
    }

    cout << "Maximum: " << maxMilk << "\n";
    cout << "Above average: " << aboveAvg << "\n";

    return 0;
}

Sample Input:

5
10 20 30 40 50

Sample Output:

Maximum: 50
Above average: 2

(Average is 30; cows with 40 and 50 are above average → 2 cows)

Complexity Analysis:

• Time: O(N) — two passes (read + count), each O(N), total O(2N) = O(N)
• Space: O(N) — uses vector<int> milk(n) to store all data

⚠️ Common Mistakes in Chapter 2.2

Chapter Summary

📌 Key Takeaways

🧩 Five Classic Loop Patterns Quick Reference

❓ FAQ (Frequently Asked Questions)

Q1: Can for and while replace each other? When should I use which?

A: Yes, any for loop can be rewritten as a while loop, and vice versa. Rule of thumb: if you know the number of iterations (e.g., "loop N times"), use for; if you don't know the count (e.g., "read until end of input"), use while. In competitions, for is used about 90% of the time.

Q2: How many levels deep can nested loops go? Is there a limit?

A: Syntactically there's no limit, but in practice you should be cautious beyond 3 levels. Two nested loops give O(N²), three give O(N³). When N ≥ 1000, three nested loops can easily time out. If you find yourself needing more than 3 levels of nesting, it usually means you need a more efficient algorithm (covered in later chapters).

Q3: break only exits the innermost loop. How do I break out of multiple nested loops at once?

A: Two common approaches: ① Use a bool found = false flag variable, and have the outer loop also check !found; ② Wrap the nested loops in a function and use return to exit directly. Approach ① is more common — see Section 2.2.6 for a complete example.

Q4: Which is faster, switch or if-else if?

A: For a small number of cases (< 10), performance is virtually identical. The advantage of switch is code readability, not speed. In competitions, you can freely choose either. If conditions involve range comparisons (like x > 10), you must use if-else.

Q5: My program produces correct output, but after submission it shows TLE (Time Limit Exceeded). What should I do?

A: Step one: estimate your algorithm's complexity. Look at the range of N → use the "nested loop complexity table" from this chapter to estimate total operations → if it exceeds 10^8, you need to optimize. Common optimization strategies include: reducing the number of loop levels, replacing brute-force search with sorting + binary search (Chapter 3.3), and replacing repeated summation with prefix sums (Chapter 3.2).

🔗 Connections to Later Chapters

• Chapter 2.3 (Functions & Arrays) will let you encapsulate the loop patterns from this chapter into functions, and use arrays to store collections of data
• Chapter 3.2 (Arrays & Prefix Sums) will teach you how to optimize O(N²) range sum queries to O(N) preprocessing + O(1) per query — one of the solutions for when "nested loops are too slow"
• Chapter 3.3 (Sorting & Searching) will teach you binary search, optimizing the O(N) linear search from this chapter to O(log N)
• The five classic loop patterns learned in this chapter (summation, finding max/min, counting, nested iteration, digit processing) are the foundational building blocks for all algorithms in this book
• Nested loop complexity analysis is the first step toward understanding time complexity (a theme throughout the entire book)

Practice Problems

🌡️ Warm-Up Problems

Warm-up 2.2.1 — Count to Ten Print the numbers 1 through 10, each on its own line. Use a for loop.

#include <bits/stdc++.h>
using namespace std;

int main() {
    for (int i = 1; i <= 10; i++) {
        cout << i << "\n";
    }
    return 0;
}

Warm-up 2.2.2 — Even Numbers Print all even numbers from 2 to 20, each on its own line.

#include <bits/stdc++.h>
using namespace std;

int main() {
    // Option 1: step by 2
    for (int i = 2; i <= 20; i += 2) {
        cout << i << "\n";
    }
    return 0;
}

Warm-up 2.2.3 — Sign Check Read one integer. Print Positive if it's > 0, Negative if it's < 0, Zero if it's 0.

Sample Input: -5 → Output: Negative

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;

    if (n > 0) {
        cout << "Positive\n";
    } else if (n < 0) {
        cout << "Negative\n";
    } else {
        cout << "Zero\n";
    }

    return 0;
}

Warm-up 2.2.4 — Multiplication Table of 3 Print the first 10 multiples of 3 (i.e., 3, 6, 9, ..., 30), each on its own line.

#include <bits/stdc++.h>
using namespace std;

int main() {
    for (int i = 1; i <= 10; i++) {
        cout << i * 3 << "\n";
    }
    return 0;
}

Warm-up 2.2.5 — Sum of Five Read exactly 5 integers (on separate lines or the same line). Print their sum.

Sample Input: 3 7 2 8 5 → Output: 25

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long sum = 0;
    for (int i = 0; i < 5; i++) {
        int x;
        cin >> x;
        sum += x;
    }
    cout << sum << "\n";
    return 0;
}

🏋️ Core Practice Problems

Problem 2.2.6 — FizzBuzz The classic programming challenge: print numbers from 1 to 100. But:

• If the number is divisible by 3, print Fizz instead
• If divisible by 5, print Buzz instead
• If divisible by both 3 and 5, print FizzBuzz instead

First few lines of output:

1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz

#include <bits/stdc++.h>
using namespace std;

int main() {
    for (int i = 1; i <= 100; i++) {
        if (i % 3 == 0 && i % 5 == 0) {
            cout << "FizzBuzz\n";
        } else if (i % 3 == 0) {
            cout << "Fizz\n";
        } else if (i % 5 == 0) {
            cout << "Buzz\n";
        } else {
            cout << i << "\n";
        }
    }
    return 0;
}

Problem 2.2.7 — Minimum of N Read N (1 ≤ N ≤ 1000), then read N integers. Print the minimum value.

Sample Input:

5
8 3 7 1 9

Sample Output: 1

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    int first;
    cin >> first;
    int minVal = first;  // initialize to first element

    for (int i = 1; i < n; i++) {   // read remaining n-1 elements
        int x;
        cin >> x;
        if (x < minVal) {
            minVal = x;
        }
    }

    cout << minVal << "\n";
    return 0;
}

Problem 2.2.8 — Count Positives Read N (1 ≤ N ≤ 1000), then read N integers. Print how many of them are strictly positive (> 0).

Sample Input:

6
3 -1 0 5 -2 7

Sample Output: 3

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    int count = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (x > 0) {
            count++;
        }
    }

    cout << count << "\n";
    return 0;
}

Problem 2.2.9 — Star Triangle Read N. Print a right triangle of * characters with N rows, where row i has i stars.

Sample Input: 4

Sample Output:

*
**
***
****

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;

    for (int row = 1; row <= n; row++) {
        for (int star = 1; star <= row; star++) {
            cout << "*";
        }
        cout << "\n";
    }

    return 0;
}

Problem 2.2.10 — Sum of Digits Read a positive integer N (1 ≤ N ≤ 10^9). Print the sum of its digits.

Sample Input: 12345 → Sample Output: 15 Sample Input: 9999 → Sample Output: 36

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;

    int digitSum = 0;
    while (n > 0) {
        digitSum += n % 10;  // add last digit
        n /= 10;             // remove last digit
    }

    cout << digitSum << "\n";
    return 0;
}

🏆 Challenge Problems

Challenge 2.2.11 — Collatz Sequence The Collatz sequence starting from N works as follows:

• If N is even: next = N / 2
• If N is odd: next = N * 3 + 1
• Stop when N = 1

Read N. Print the entire sequence (including N and 1). Also print how many steps it takes to reach 1.

Sample Input: 6 Sample Output:

6 3 10 5 16 8 4 2 1
Steps: 8

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long n;
    cin >> n;

    int steps = 0;
    cout << n;         // print starting number

    while (n != 1) {
        if (n % 2 == 0) {
            n = n / 2;
        } else {
            n = n * 3 + 1;
        }
        cout << " " << n;  // print each next number
        steps++;
    }
    cout << "\n";
    cout << "Steps: " << steps << "\n";

    return 0;
}

Challenge 2.2.12 — Prime Check Read N (2 ≤ N ≤ 10^6). Print prime if N is prime, composite otherwise.

A number is prime if it has no divisors other than 1 and itself.

Sample Input: 17 → Output: prime Sample Input: 100 → Output: composite

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;

    bool isPrime = true;

    if (n < 2) {
        isPrime = false;
    } else {
        // Check divisors from 2 to sqrt(n)
        for (int i = 2; (long long)i * i <= n; i++) {
            if (n % i == 0) {
                isPrime = false;
                break;  // found a divisor, no need to continue
            }
        }
    }

    cout << (isPrime ? "prime" : "composite") << "\n";
    return 0;
}

Challenge 2.2.13 — Highest Rated Cow Read N (1 ≤ N ≤ 1000), then read N pairs of (cow name, rating). Find and print the name of the cow with the highest rating.

Sample Input:

4
Bessie 95
Elsie 82
Moo 95
Daisy 88

Sample Output: Bessie (If there's a tie, print the name of the first one that appeared.)

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    string bestName;
    int bestRating = -1;  // initialize to -1 so any real rating beats it

    for (int i = 0; i < n; i++) {
        string name;
        int rating;
        cin >> name >> rating;

        if (rating > bestRating) {
            bestRating = rating;
            bestName = name;
        }
    }

    cout << bestName << "\n";
    return 0;
}

Chapter 2.3: Functions & Arrays

📝 Prerequisites: Chapters 2.1 & 2.2 (variables, loops, if/else)

As your programs grow larger, you need ways to organize code (functions) and store collections of data (arrays and vectors). This chapter introduces both — two of the most important tools in competitive programming.

2.3.1 Functions — What and Why

🍕 The Recipe Analogy

A function is like a pizza recipe:

- Input (parameters):   ingredients — flour, cheese, tomatoes
- Process (body):       the cooking steps
- Output (return value): the finished pizza

Just like you can make many pizzas using one recipe,
you can call a function many times with different inputs.

pizza("thin crust", "pepperoni")  → one pizza
pizza("thick crust", "mushroom")  → another pizza

Without functions, if you need to compute "is this number prime?" in five different places, you'd copy-paste the same 10 lines of code five times. Then if you find a bug, you have to fix it in all five places!

When to Write a Function

Use a function when:

1. You repeat the same logic 3+ times in your program
2. A block of code does one clear, named thing (e.g., "check if prime", "compute distance")
3. Your main is getting too long to read comfortably

Basic Function Syntax

returnType functionName(parameter1Type param1, parameter2Type param2, ...) {
    // function body
    return value;  // must match returnType; omit for void functions
}

Your First Functions

#include <bits/stdc++.h>
using namespace std;

// ---- FUNCTION DEFINITIONS (must come BEFORE they are used, or use prototypes) ----

// Takes one integer, returns its square
int square(int x) {
    return x * x;
}

// Takes two integers, returns the larger one
int maxOf(int a, int b) {
    if (a > b) return a;
    else return b;
}

// void function: does something but doesn't return a value
void printSeparator() {
    cout << "====================\n";
}

// ---- MAIN ----
int main() {
    cout << square(5) << "\n";       // calls square with x=5, prints 25
    cout << square(12) << "\n";      // calls square with x=12, prints 144

    cout << maxOf(7, 3) << "\n";     // prints 7
    cout << maxOf(-5, -2) << "\n";   // prints -2

    printSeparator();                // prints the divider line
    cout << "Done!\n";
    printSeparator();

    return 0;
}

🤔 Why do functions come before main?

C++ reads your file top-to-bottom. When it sees a call like square(5), it needs to already know what square means. If square is defined after main, the compiler will say "I've never heard of square!"

Solution 1: Define all functions above main (simplest approach).

Solution 2: Use a function prototype — a forward declaration telling the compiler "this function exists, I'll define it later":

#include <bits/stdc++.h>
using namespace std;

int square(int x);       // prototype — just the signature, no body
int maxOf(int a, int b); // prototype

int main() {
    cout << square(5) << "\n";   // OK! compiler knows square exists
    return 0;
}

// Full definitions can come after main
int square(int x) {
    return x * x;
}

int maxOf(int a, int b) {
    return (a > b) ? a : b;
}

2.3.2 Void Functions vs Return Functions

void functions: Do something, return nothing

// void functions perform an action
void printLine(int n) {
    for (int i = 0; i < n; i++) {
        cout << "-";
    }
    cout << "\n";
}

// Calling a void function — just call it, don't try to capture a value
printLine(10);    // prints: ----------
printLine(20);    // prints: --------------------

Return functions: Compute and give back a value

// Returns the absolute value of x
int absoluteValue(int x) {
    if (x < 0) return -x;
    return x;
}

// Calling a return function — capture the result in a variable or use it directly
int result = absoluteValue(-7);
cout << result << "\n";           // 7
cout << absoluteValue(-3) << "\n"; // 3 (used directly)

Multiple return statements

A function can have multiple return statements — execution stops at the first one reached:

string classify(int n) {
    if (n < 0) return "negative";   // exits here if n < 0
    if (n == 0) return "zero";      // exits here if n == 0
    return "positive";              // exits here otherwise
}

cout << classify(-5) << "\n";   // negative
cout << classify(0) << "\n";    // zero
cout << classify(3) << "\n";    // positive

2.3.3 Pass by Value vs Pass by Reference

When you pass a variable to a function, there are two ways it can happen. Understanding this is crucial.

Pass by Value (default): Function gets a COPY

void addOne_byValue(int x) {
    x++;  // modifies the LOCAL COPY — original is unchanged
    cout << "Inside function: " << x << "\n";  // 6
}

int main() {
    int n = 5;
    addOne_byValue(n);
    cout << "After function: " << n << "\n";   // still 5! original unchanged
    return 0;
}

Think of it like a photocopy: the function works on a photocopy of the paper. Changes to the photocopy don't affect the original.

Pass by Reference (&): Function works on the ORIGINAL

void addOne_byRef(int& x) {  // & means "reference to the original"
    x++;  // modifies the ORIGINAL variable directly
    cout << "Inside function: " << x << "\n";  // 6
}

int main() {
    int n = 5;
    addOne_byRef(n);
    cout << "After function: " << n << "\n";   // now 6! original was changed
    return 0;
}

When to use each

Multiple Return Values via References

A C++ function can only return one value. But you can "return" multiple values through reference parameters:

// Computes both quotient AND remainder simultaneously
void divmod(int a, int b, int& quotient, int& remainder) {
    quotient = a / b;
    remainder = a % b;
}

int main() {
    int q, r;
    divmod(17, 5, q, r);  // q and r are modified by the function
    cout << "17 / 5 = " << q << " remainder " << r << "\n";
    // prints: 17 / 5 = 3 remainder 2
    return 0;
}

2.3.4 Recursion

A recursive function is one that calls itself. It's perfect for problems that break down into smaller versions of the same problem.

Classic Example: Factorial

5! = 5 × 4 × 3 × 2 × 1 = 120
   = 5 × (4!)              ← same problem, smaller input!

💡 Three-Step Recursive Thinking:

1. Find "self-similarity": Can the original problem be broken into smaller problems of the same type? 5! = 5 × 4!, and 4! and 5! are the same type ✓
2. Identify the base case: What is the smallest case? 0! = 1, cannot be broken down further
3. Write the inductive step: n! = n × (n-1)!, call yourself with smaller input

This thinking process will be used repeatedly in Graph Algorithms (Chapter 5.1) and Dynamic Programming (Chapters 6.1–6.3).

int factorial(int n) {
    if (n == 0) return 1;            // BASE CASE: stop recursing
    return n * factorial(n - 1);    // RECURSIVE CASE: reduce to smaller problem
}

Tracing factorial(4):

factorial(4)
= 4 * factorial(3)
= 4 * (3 * factorial(2))
= 4 * (3 * (2 * factorial(1)))
= 4 * (3 * (2 * (1 * factorial(0))))
= 4 * (3 * (2 * (1 * 1)))   ← base case!
= 4 * (3 * (2 * 1))
= 4 * (3 * 2)
= 4 * 6
= 24  ✓

Every recursive function needs:

1. A base case — stops the recursion (prevents infinite recursion)
2. A recursive case — calls itself with a smaller input

🐛 Common Bug: Forgetting the base case → infinite recursion → "Stack Overflow" crash!

2.3.5 Arrays — Fixed Collections

🏠 The Mailbox Analogy

An array is like a row of mailboxes on a street:
- All mailboxes are the same size (same type)
- Each has a number on the door (the index, starting from 0)
- You can go directly to any mailbox by its number

Visual: Array Memory Layout

Arrays are stored as consecutive blocks of memory. Each element sits right next to the previous one, allowing O(1) random access.

Array Basics

#include <bits/stdc++.h>
using namespace std;

int main() {
    // Declare an array of 5 integers (elements are uninitialized — garbage values!)
    int arr[5];

    // Assign values one by one
    arr[0] = 10;
    arr[1] = 20;
    arr[2] = 30;
    arr[3] = 40;
    arr[4] = 50;

    // Declare AND initialize at the same time
    int nums[5] = {1, 2, 3, 4, 5};

    // Initialize all elements to zero
    int zeros[100] = {};          // all 100 elements = 0
    int zeros2[100];
    fill(zeros2, zeros2 + 100, 0); // another way

    // Access and print
    cout << arr[2] << "\n";       // 30

    // Loop through the array
    for (int i = 0; i < 5; i++) {
        cout << nums[i] << " ";   // 1 2 3 4 5
    }
    cout << "\n";

    return 0;
}

🐛 The Off-By-One Error — The #1 Array Bug

Arrays are 0-indexed: if you declare int arr[5], valid indices are 0, 1, 2, 3, 4. There is NO arr[5]!

int arr[5] = {10, 20, 30, 40, 50};

// WRONG: loop goes from i=0 to i=5 inclusive — index 5 doesn't exist!
for (int i = 0; i <= 5; i++) {   // BUG: <= 5 should be < 5
    cout << arr[i];               // CRASH or garbage value when i=5
}

// CORRECT: loop from i=0 to i=4 (i < 5 ensures i never reaches 5)
for (int i = 0; i < 5; i++) {    // i goes: 0, 1, 2, 3, 4 ✓
    cout << arr[i];               // always valid
}

This is called an "off-by-one error" — going one element past the end. It's the single most common array bug in competitive programming.

🤔 Why start at 0? C++ inherited this from C, which was designed close to hardware. The index is actually an offset from the start of the array. The first element is at offset 0 (no offset from the beginning).

Global Arrays for Large Sizes

The local variables inside main live on the "stack," which has limited space (~1-8 MB). For competitive programming with N up to 10^6, you need global arrays (live in a different memory area, much larger):

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000001;  // max size + 1 (common convention)
int arr[MAXN];              // declared globally — safe for large sizes
// Global arrays are automatically initialized to 0!

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    return 0;
}

⚡ Pro Tip: Global arrays are initialized to 0 automatically. Local arrays are NOT — they contain garbage values until you assign them!

2.3.6 Common Array Algorithms

Find Sum, Max, Min

int n;
cin >> n;

vector<int> arr(n);    // we'll learn vectors soon; this works like an array
for (int i = 0; i < n; i++) cin >> arr[i];

// Sum
long long sum = 0;
for (int i = 0; i < n; i++) sum += arr[i];
cout << "Sum: " << sum << "\n";

// Max (initialize to first element!)
int maxVal = arr[0];
for (int i = 1; i < n; i++) {
    if (arr[i] > maxVal) maxVal = arr[i];
}
cout << "Max: " << maxVal << "\n";

// Min (same idea)
int minVal = arr[0];
for (int i = 1; i < n; i++) {
    minVal = min(minVal, arr[i]);  // min() is a built-in function
}
cout << "Min: " << minVal << "\n";

Complexity Analysis:

• Time: O(N) — each algorithm only needs one pass through the array
• Space: O(1) — only a few extra variables (not counting the input array itself)

Reverse an Array

int arr[] = {1, 2, 3, 4, 5};
int n = 5;

// Swap elements from both ends, moving toward the middle
for (int i = 0, j = n - 1; i < j; i++, j--) {
    swap(arr[i], arr[j]);  // swap() is a built-in function
}
// arr is now {5, 4, 3, 2, 1}

Complexity Analysis:

• Time: O(N) — each pair of elements is swapped once, N/2 swaps total
• Space: O(1) — in-place swap, no extra array needed

Two-Dimensional Arrays

A 2D array is like a table or grid. Perfect for maps, grids, matrices:

int grid[3][4];  // 3 rows, 4 columns

// Fill with i * 10 + j
for (int r = 0; r < 3; r++) {
    for (int c = 0; c < 4; c++) {
        grid[r][c] = r * 10 + c;
    }
}

// Print
for (int r = 0; r < 3; r++) {
    for (int c = 0; c < 4; c++) {
        cout << grid[r][c] << "\t";
    }
    cout << "\n";
}

Output:

0   1   2   3
10  11  12  13
20  21  22  23

2.3.7 Vectors — Dynamic Arrays

Arrays have a major limitation: their size must be known at compile time (or must be declared large enough in advance). Vectors solve this — they can grow and shrink as needed while your program is running.

Array vs Vector Comparison

Vector Basics

#include <bits/stdc++.h>
using namespace std;

int main() {
    // Create an empty vector
    vector<int> v;

    // Add elements to the back with push_back
    v.push_back(10);    // v = [10]
    v.push_back(20);    // v = [10, 20]
    v.push_back(30);    // v = [10, 20, 30]

    // Access by index (same as arrays, 0-indexed)
    cout << v[0] << "\n";     // 10
    cout << v[1] << "\n";     // 20

    // Useful functions
    cout << v.size() << "\n"; // 3 (number of elements)
    cout << v.front() << "\n"; // 10 (first element)
    cout << v.back() << "\n";  // 30 (last element)
    cout << v.empty() << "\n"; // 0 (false — not empty)

    // Remove last element
    v.pop_back();   // v = [10, 20]

    // Clear all elements
    v.clear();      // v = []
    cout << v.empty() << "\n"; // 1 (true — now empty)

    return 0;
}

Creating Vectors With Initial Values

vector<int> zeros(10, 0);       // ten 0s: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
vector<int> ones(5, 1);         // five 1s: [1, 1, 1, 1, 1]
vector<int> primes = {2, 3, 5, 7, 11};  // initialized from list
vector<int> empty;              // empty vector

Iterating Over a Vector

vector<int> v = {10, 20, 30, 40, 50};

// Method 1: index-based (like arrays)
for (int i = 0; i < (int)v.size(); i++) {
    cout << v[i] << " ";
}
cout << "\n";

// Method 2: range-based for loop (cleaner, preferred)
for (int x : v) {
    cout << x << " ";
}
cout << "\n";

// Method 3: range-based with reference (use when modifying)
for (int& x : v) {
    x *= 2;  // doubles each element in-place
}

🤔 Why (int)v.size() in the index-based loop? v.size() returns an unsigned integer. If you compare int i with an unsigned value, C++ can behave unexpectedly (especially if i goes negative). Casting to (int) is the safe habit.

The Standard USACO Pattern with Vectors

int n;
cin >> n;

vector<int> arr(n);         // create vector of size n
for (int i = 0; i < n; i++) {
    cin >> arr[i];          // read into each position
}

// Now process arr...
sort(arr.begin(), arr.end());  // sort ascending

2D Vectors

int rows = 3, cols = 4;
vector<vector<int>> grid(rows, vector<int>(cols, 0));  // 3×4 grid of 0s

// Access: grid[r][c]
grid[1][2] = 42;
cout << grid[1][2] << "\n";  // 42

2.3.8 Passing Arrays and Vectors to Functions

Arrays

When you pass an array to a function, the function receives a pointer to the first element. Changes inside the function affect the original:

void fillSquares(int arr[], int n) {  // arr[] syntax for array parameter
    for (int i = 0; i < n; i++) {
        arr[i] = i * i;   // modifies the original!
    }
}

int main() {
    int arr[5] = {0};
    fillSquares(arr, 5);
    // arr is now {0, 1, 4, 9, 16}
    for (int i = 0; i < 5; i++) cout << arr[i] << " ";
    cout << "\n";
    return 0;
}

Vectors

Vectors by default are copied when passed to functions (expensive for large vectors!). Use & to pass by reference:

// Pass by value — makes a copy (SLOW for large vectors)
void printVec(vector<int> v) {
    for (int x : v) cout << x << " ";
}

// Pass by reference — no copy, CAN modify original (use for output params)
void sortVec(vector<int>& v) {
    sort(v.begin(), v.end());
}

// Pass by const reference — no copy, CANNOT modify (best for read-only)
void printVecFast(const vector<int>& v) {
    for (int x : v) cout << x << " ";
}

⚡ Pro Tip: For any vector parameter that you're only reading (not modifying), always write const vector<int>&. It avoids the copy and also signals to readers that the function won't change the vector.

⚠️ Common Mistakes in Chapter 2.3

Chapter Summary

📌 Key Takeaways

❓ FAQ

Q1: Which is better, arrays or vectors?

A: Both are common in competitive programming. Rule of thumb: if the size is fixed and known, global arrays are simplest; if the size changes dynamically or needs to be passed to functions, use vector. Many contestants default to vector because it is more flexible and less error-prone.

Q2: Is there a limit to recursion depth? Can it crash?

A: Yes. Each function call allocates space on the stack, and the default stack size is about 1-8 MB. In practice, about 10^4 ~ 10^5 levels of recursion are supported. If exceeded, the program crashes with a "stack overflow". In contests, if recursion depth may exceed 10^4, consider switching to an iterative (loop) approach.

Q3: When should I use pass by reference (&)?

A: Two cases: ① You need to modify the original variable inside the function; ② The parameter is a large object (like vector or string) and you want to avoid copy overhead. For small types like int and double, copy overhead is negligible, so pass by value is fine.

Q4: Can a function return an array or vector?

A: Arrays cannot be returned directly, but vector can! vector<int> solve() { ... return result; } is perfectly valid. Modern C++ compilers optimize the return process (called RVO), so the entire vector is not actually copied.

Q5: Why does the prefix sum array have one extra index? prefix[n+1] instead of prefix[n]?

A: prefix[0] = 0 is a "sentinel value" that makes the formula prefix[R+1] - prefix[L] work in all cases. Without this sentinel, querying [0, R] would require special handling when L=0. This is a very common programming trick: use an extra sentinel value to simplify boundary handling.

🔗 Connections to Later Chapters

• Chapter 3.1 (STL Essentials) will introduce tools like sort, binary_search, and pair, letting you accomplish in one line what this chapter implements by hand
• Chapter 3.2 (Prefix Sums) will dive deeper into the prefix sum technique introduced in Problem 3.10, including 2D prefix sums and difference arrays
• Chapter 5.1 (Introduction to Graphs) will build on the recursion foundation in Section 2.3.4 to teach graph traversals like DFS and BFS
• Chapters 6.1–6.3 (Dynamic Programming): the core idea of "breaking large problems into smaller ones" is closely related to recursion; this chapter's recursive thinking is important groundwork
• The function encapsulation and array/vector operations learned in this chapter will be used continuously in every subsequent chapter

Practice Problems

🌡️ Warm-Up Problems

Warm-up 2.3.1 — Square Function Write a function int square(int x) that returns x². In main, read one integer and print its square.

Sample Input: 7 → Sample Output: 49

#include <bits/stdc++.h>
using namespace std;

int square(int x) {
    return x * x;
}

int main() {
    int n;
    cin >> n;
    cout << square(n) << "\n";
    return 0;
}

Warm-up 2.3.2 — Max of Two Write a function int myMax(int a, int b) that returns the larger of two integers. In main, read two integers and print the larger.

Sample Input: 13 7 → Sample Output: 13

#include <bits/stdc++.h>
using namespace std;

int myMax(int a, int b) {
    if (a > b) return a;
    return b;
}

int main() {
    int a, b;
    cin >> a >> b;
    cout << myMax(a, b) << "\n";
    return 0;
}

Warm-up 2.3.3 — Reverse Array Declare an array of exactly 5 integers: {1, 2, 3, 4, 5}. Print them in reverse order (no input needed).

Expected Output:

5 4 3 2 1

#include <bits/stdc++.h>
using namespace std;

int main() {
    int arr[5] = {1, 2, 3, 4, 5};

    for (int i = 4; i >= 0; i--) {
        cout << arr[i];
        if (i > 0) cout << " ";
    }
    cout << "\n";

    return 0;
}

Warm-up 2.3.4 — Vector Sum Create a vector, push the values 10, 20, 30, 40, 50 into it using push_back, then print their sum.

Expected Output: 150

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v;
    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);
    v.push_back(50);

    long long sum = 0;
    for (int x : v) {
        sum += x;
    }

    cout << sum << "\n";
    return 0;
}

Warm-up 2.3.5 — Hello N Times Write a void function sayHello(int n) that prints "Hello!" exactly n times. Call it from main after reading n.

Sample Input: 3 Sample Output:

Hello!
Hello!
Hello!

#include <bits/stdc++.h>
using namespace std;

void sayHello(int n) {
    for (int i = 0; i < n; i++) {
        cout << "Hello!\n";
    }
}

int main() {
    int n;
    cin >> n;
    sayHello(n);
    return 0;
}

🏋️ Core Practice Problems

Problem 2.3.6 — Array Reverse Read N (1 ≤ N ≤ 100), then read N integers. Print them in reverse order.

Sample Input:

5
1 2 3 4 5

Sample Output: 5 4 3 2 1

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    for (int i = n - 1; i >= 0; i--) {
        cout << arr[i];
        if (i > 0) cout << " ";
    }
    cout << "\n";

    return 0;
}

Problem 2.3.7 — Running Average Read N (1 ≤ N ≤ 100), then read N integers one at a time. After reading each integer, print the average of all integers read so far (as a decimal with 2 decimal places).

Sample Input:

4
10 20 30 40

Sample Output:

10.00
15.00
20.00
25.00

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    long long sum = 0;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        sum += x;
        double avg = (double)sum / i;
        cout << fixed << setprecision(2) << avg << "\n";
    }

    return 0;
}

Problem 2.3.8 — Frequency Count Read N (1 ≤ N ≤ 100) integers. Each integer is between 1 and 10 inclusive. Print how many times each value from 1 to 10 appears.

Sample Input:

7
3 1 2 3 3 1 7

Sample Output:

1 appears 2 times
2 appears 1 times
3 appears 3 times
4 appears 0 times
5 appears 0 times
6 appears 0 times
7 appears 1 times
8 appears 0 times
9 appears 0 times
10 appears 0 times

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    int freq[11] = {};  // indices 0-10; we'll use 1-10. Initialize all to 0.

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        freq[x]++;    // increment the count for value x
    }

    for (int v = 1; v <= 10; v++) {
        cout << v << " appears " << freq[v] << " times\n";
    }

    return 0;
}

Problem 2.3.9 — Two Sum Read N (1 ≤ N ≤ 100) integers and a target value T. Print YES if any two different elements in the array sum to T, NO otherwise.

Sample Input:

5 9
1 4 5 6 3

(N=5, T=9, then the array) Sample Output: YES (because 4+5=9 or 3+6=9)

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, t;
    cin >> n >> t;

    vector<int> arr(n);
    for (int i = 0; i < n; i++) cin >> arr[i];

    bool found = false;
    for (int i = 0; i < n && !found; i++) {
        for (int j = i + 1; j < n; j++) {
            if (arr[i] + arr[j] == t) {
                found = true;
                break;
            }
        }
    }

    cout << (found ? "YES" : "NO") << "\n";

    return 0;
}

Problem 2.3.10 — Prefix Sums Read N (1 ≤ N ≤ 1000), then N integers. Then read Q queries (1 ≤ Q ≤ 1000), each with two integers L and R (0-indexed, inclusive). For each query, print the sum of elements from index L to R.

Sample Input:

5
1 2 3 4 5
3
0 2
1 3
2 4

Sample Output:

6
9
12

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<long long> arr(n), prefix(n + 1, 0);

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        prefix[i + 1] = prefix[i] + arr[i];  // build prefix sum
    }
    // prefix[0] = 0
    // prefix[1] = arr[0]
    // prefix[2] = arr[0] + arr[1]
    // prefix[i] = arr[0] + arr[1] + ... + arr[i-1]

    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r;
        // sum from l to r (inclusive) = prefix[r+1] - prefix[l]
        cout << prefix[r + 1] - prefix[l] << "\n";
    }

    return 0;
}

🏆 Challenge Problems

Challenge 2.3.11 — Rotate Array Read N (1 ≤ N ≤ 1000) and K (0 ≤ K < N). Read N integers. Print the array rotated right by K positions (the last K elements wrap to the front).

Sample Input:

5 2
1 2 3 4 5

Sample Output: 4 5 1 2 3

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k;
    cin >> n >> k;

    vector<int> arr(n);
    for (int i = 0; i < n; i++) cin >> arr[i];

    // Print n elements starting from index (n - k) % n, wrapping around
    for (int i = 0; i < n; i++) {
        int idx = (n - k + i) % n;
        cout << arr[idx];
        if (i < n - 1) cout << " ";
    }
    cout << "\n";

    return 0;
}

Challenge 2.3.12 — Merge Sorted Arrays Read N₁, then N₁ sorted integers. Read N₂, then N₂ sorted integers. Print the merged sorted array.

Sample Input:

3
1 3 5
4
2 4 6 8

Sample Output: 1 2 3 4 5 6 8

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n1;
    cin >> n1;
    vector<int> a(n1);
    for (int i = 0; i < n1; i++) cin >> a[i];

    int n2;
    cin >> n2;
    vector<int> b(n2);
    for (int i = 0; i < n2; i++) cin >> b[i];

    // Two-pointer merge
    int i = 0, j = 0;
    vector<int> result;

    while (i < n1 && j < n2) {
        if (a[i] <= b[j]) {
            result.push_back(a[i++]);  // take from a, advance i
        } else {
            result.push_back(b[j++]);  // take from b, advance j
        }
    }
    // One array may have leftover elements
    while (i < n1) result.push_back(a[i++]);
    while (j < n2) result.push_back(b[j++]);

    for (int idx = 0; idx < (int)result.size(); idx++) {
        cout << result[idx];
        if (idx < (int)result.size() - 1) cout << " ";
    }
    cout << "\n";

    return 0;
}

Challenge 2.3.13 — Smell Distance (Inspired by USACO Bronze)

N cows are standing in a line. Each cow has a position p[i] and a smell radius s[i]. A cow can smell another if the distance between them is at most the sum of their radii. Read N, then N pairs (position, radius). Print the number of pairs of cows that can smell each other.

Sample Input:

4
1 2
5 1
8 3
15 1

Sample Output: 1

(Pair (0,1): dist=|1-5|=4, radii sum=2+1=3. 4>3, NO. Pair (0,2): dist=|1-8|=7, sum=2+3=5. 7>5, NO. Pair (1,2): dist=|5-8|=3, sum=1+3=4. 3≤4, YES. Pair (0,3): 14>3 NO. Pair (1,3): 10>2 NO. Pair (2,3): 7>4 NO. Total: 1.)

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    vector<long long> pos(n), rad(n);
    for (int i = 0; i < n; i++) {
        cin >> pos[i] >> rad[i];
    }

    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            long long dist = abs(pos[i] - pos[j]);
            long long sumRad = rad[i] + rad[j];
            if (dist <= sumRad) {
                count++;
            }
        }
    }

    cout << count << "\n";
    return 0;
}

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

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

Prerequisites

Before starting Part 3, make sure you can:

• Write and compile a C++ program from scratch (Chapter 2.1)
• Use for loops 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

1. Chapter 3.2 (Prefix Sums) is the most frequently tested technique in Bronze. Make sure you can implement it from scratch in 5 minutes.
2. Chapter 3.3 (Binary Search) introduces "binary search on the answer" — this is a Silver-level technique that separates good solutions from great ones.
3. Don't skip the practice problems. Each chapter's problems are specifically chosen to build the intuition you need.
4. 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!

STL Essentials

Chapter 3.2: Arrays & Prefix Sums

📝 Before You Continue: Make sure you're comfortable with arrays, vectors, and basic loops (Chapters 2.2–2.3). You'll also want to understand long long overflow (Chapter 2.1).

Imagine you have an array of N numbers, and someone asks you 100,000 times: "What is the sum of elements from index L to index R?" A naive approach recomputes the sum from scratch each time — that's O(N) per query, or O(N × Q) total. With N = Q = 10^5, that's 10^10 operations. Way too slow.

Prefix sums solve this in O(N) preprocessing and O(1) per query. This is one of the most elegant and useful techniques in all of competitive programming.

💡 Key Insight: Prefix sums transform a "range query" problem into a subtraction. Instead of summing L to R every time, you precompute cumulative sums and subtract two of them. This trades O(Q) repeated work for one-time O(N) preprocessing.

3.2.1 The Prefix Sum Idea

The prefix sum of an array is a new array where each element stores the cumulative sum up to that index.

Visual: Prefix Sum Array

The diagram above shows how the prefix sum array is constructed from the original array, and how a range query sum(L, R) = P[R] - P[L-1] is computed in O(1) time. The blue cells highlight a query range while the red and green cells show the two prefix values being subtracted.

Given array: A = [3, 1, 4, 1, 5, 9, 2, 6] (1-indexed for clarity)

Index:  1  2  3  4  5  6  7  8
A:      3  1  4  1  5  9  2  6
P:      3  4  8  9  14 23 25 31

Where P[i] = A[1] + A[2] + ... + A[i].

Why 1-Indexing?

Using 1-indexed arrays lets us define P[0] = 0 (the "empty prefix" sums to zero). This makes the query formula P[R] - P[L-1] work even when L = 1 — we'd compute P[R] - P[0] = P[R], which is correct.

Building the Prefix Sum Array

// Solution: Build Prefix Sum Array — O(N)
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    // Step 1: Read input (1-indexed)
    vector<int> A(n + 1);
    for (int i = 1; i <= n; i++) cin >> A[i];

    // Step 2: Build prefix sums
    vector<long long> P(n + 1, 0);  // P[0] = 0 (base case)
    for (int i = 1; i <= n; i++) {
        P[i] = P[i - 1] + A[i];   // ← KEY LINE: each P[i] = all elements up to i
    }

    return 0;
}

Complexity Analysis:

• Time: O(N) — one pass through the array
• Space: O(N) — stores the prefix array

Step-by-step trace for A = [3, 1, 4, 1, 5]:

i=1: P[1] = P[0] + A[1] = 0 + 3 = 3
i=2: P[2] = P[1] + A[2] = 3 + 1 = 4
i=3: P[3] = P[2] + A[3] = 4 + 4 = 8
i=4: P[4] = P[3] + A[4] = 8 + 1 = 9
i=5: P[5] = P[4] + A[5] = 9 + 5 = 14

3.2.2 Range Sum Queries in O(1)

Once you have the prefix sum array, the sum from index L to R is:

sum(L, R) = P[R] - P[L-1]

Why? P[R] = sum of elements 1..R. P[L-1] = sum of elements 1..(L-1). Their difference = sum of elements L..R.

💡 Key Insight: Think of P[i] as "the total sum of the first i elements." To get the sum of a window [L, R], you subtract the "prefix before L" from the "prefix through R." It's like: big triangle minus smaller triangle = trapezoid.

// Solution: Range Sum Queries — Preprocessing O(N), Each Query O(1)
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100001;
long long A[MAXN];
long long P[MAXN];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q;
    cin >> n >> q;

    // Step 1: Read array
    for (int i = 1; i <= n; i++) cin >> A[i];

    // Step 2: Build prefix sum — O(n)
    P[0] = 0;
    for (int i = 1; i <= n; i++) {
        P[i] = P[i - 1] + A[i];
    }

    // Step 3: Answer q range sum queries — O(1) each
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        cout << P[r] - P[l - 1] << "\n";  // ← KEY LINE: range sum formula
    }

    return 0;
}

Sample Input:

8 3
3 1 4 1 5 9 2 6
1 4
3 7
2 6

Sample Output:

9
21
20

Verification:

• sum(1,4) = P[4] - P[0] = 9 - 0 = 9 → A[1]+A[2]+A[3]+A[4] = 3+1+4+1 = 9 ✓
• sum(3,7) = P[7] - P[2] = 25 - 4 = 21 → A[3]+...+A[7] = 4+1+5+9+2 = 21 ✓
• sum(2,6) = P[6] - P[1] = 23 - 3 = 20 → A[2]+...+A[6] = 1+4+1+5+9 = 20 ✓

⚠️ Common Mistake: Writing P[R] - P[L] instead of P[R] - P[L-1]. The formula includes both endpoints L and R — you want to subtract the sum before L, not the sum at L.

Total Complexity: O(N + Q) — perfect for N, Q up to 10^5.

3.2.3 USACO Example: Breed Counting

This is a classic USACO Bronze problem (2015 December).

Problem: N cows in a line. Each cow is breed 1, 2, or 3. Answer Q queries: how many cows of breed B are in positions L to R?

Solution: Maintain one prefix sum array per breed.

// Solution: Multi-Breed Prefix Sums — O(N + Q)
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q;
    cin >> n >> q;

    vector<int> breed(n + 1);
    vector<vector<long long>> P(4, vector<long long>(n + 1, 0));
    // P[b][i] = number of cows of breed b in positions 1..i

    // Step 1: Build prefix sums for each breed
    for (int i = 1; i <= n; i++) {
        cin >> breed[i];
        for (int b = 1; b <= 3; b++) {
            P[b][i] = P[b][i - 1] + (breed[i] == b ? 1 : 0);  // ← KEY LINE
        }
    }

    // Step 2: Answer each query in O(1)
    for (int i = 0; i < q; i++) {
        int l, r, b;
        cin >> l >> r >> b;
        cout << P[b][r] - P[b][l - 1] << "\n";
    }

    return 0;
}

🏆 USACO Tip: Many USACO Bronze problems involve "count elements satisfying property X in a range." If Q is large, always consider prefix sums.

3.2.4 USACO-Style Problem Walkthrough: Farmer John's Grass Fields

🔗 Related Problem: This is a fictional USACO-style problem inspired by "Breed Counting" and "Tallest Cow" — both classic Bronze problems.

Problem Statement: Farmer John has N fields in a row. Field i has grass[i] units of grass. He needs to answer Q queries: "What is the total grass in fields L through R (inclusive)?" With N, Q up to 10^5, he needs each query answered in O(1).

Sample Input:

6 4
4 2 7 1 8 3
1 3
2 5
4 6
1 6

Sample Output:

13
18
12
25

Step-by-Step Solution:

Step 1: Understand the problem. We have an array [4, 2, 7, 1, 8, 3] and need range sums.

Step 2: Build the prefix sum array.

Index:  0  1  2  3  4  5  6
grass:  -  4  2  7  1  8  3
P:      0  4  6  13 14 22 25

Step 3: Answer queries using P[R] - P[L-1]:

• Query (1,3): P[3] - P[0] = 13 - 0 = 13 ✓
• Query (2,5): P[5] - P[1] = 22 - 4 = 18 ✓
• Query (4,6): P[6] - P[3] = 25 - 13 = 12 ✓
• Query (1,6): P[6] - P[0] = 25 - 0 = 25 ✓

Complete C++ Solution:

// Farmer John's Grass Fields — Prefix Sum Solution O(N + Q)
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q;
    cin >> n >> q;

    // Step 1: Read grass values and build prefix sum simultaneously
    vector<long long> P(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        long long g;
        cin >> g;
        P[i] = P[i - 1] + g;   // ← KEY LINE: incremental prefix sum
    }

    // Step 2: Answer each query in O(1)
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << P[r] - P[l - 1] << "\n";
    }

    return 0;
}

Why is this O(N + Q)?

• Building prefix sums: one loop, N iterations → O(N)
• Each query: one subtraction → O(1) per query, O(Q) total
• Total: O(N + Q) — much better than the O(NQ) brute force

⚠️ Common Mistake: Using int instead of long long for the prefix sum. If grass values are up to 10^9 and N = 10^5, the total could be up to 10^14 — way beyond int's range of ~2×10^9.

3.2.5 Difference Arrays

The difference array is the inverse of prefix sums. It's useful when you need to add a value to a range of positions, then query final values.

Problem: Start with all zeros. Apply M updates: "add V to all positions from L to R." Then print the final array.

Naively, each update is O(R-L+1). With a difference array, each update is O(1), and reconstruction is O(N).

💡 Key Insight: Instead of adding V to every position in [L, R] (slow), we record "+V at position L" and "-V at position R+1" (fast). When we later do a prefix sum of these markers, the +V and -V "cancel out" outside [L,R], so the net effect is exactly adding V to [L,R].

// Solution: Difference Array for Range Updates — O(N + M)
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    vector<long long> diff(n + 2, 0);  // difference array (extra space for R+1 case)

    // Step 1: Process all range updates in O(1) each
    for (int i = 0; i < m; i++) {
        int l, r, v;
        cin >> l >> r >> v;
        diff[l] += v;      // ← KEY LINE: mark start of range
        diff[r + 1] -= v;  // ← KEY LINE: mark end+1 to undo the addition
    }

    // Step 2: Reconstruct the final array by taking prefix sums of diff
    long long running = 0;
    for (int i = 1; i <= n; i++) {
        running += diff[i];
        cout << running;
        if (i < n) cout << " ";
    }
    cout << "\n";

    return 0;
}

Sample Input:

5 3
1 3 2
2 5 3
3 4 -1

Step-by-step trace:

📝 索引说明： 以下追踪中 diff 数组使用 1-indexed（即 diff[1]..diff[n+1]），与代码 vector<long long> diff(n + 2, 0) 一致。方括号内的数字表示 diff[1], diff[2], ..., diff[6]（n=5 时，数组共 7 个位置，有效使用 diff[1..6]）。

初始状态:           diff[1..6] = [0,  0,  0,  0,  0,  0]

After update(1,3,+2): diff[1]+=2, diff[4]-=2
                      diff[1..6] = [2,  0,  0, -2,  0,  0]

After update(2,5,+3): diff[2]+=3, diff[6]-=3
                      diff[1..6] = [2,  3,  0, -2,  0, -3]

After update(3,4,-1): diff[3]+=-1 即 diff[3]-=1, diff[5]-=(-1) 即 diff[5]+=1
                      diff[1..6] = [2,  3, -1, -2,  1, -3]

Prefix sum reconstruction: i=1: running = 0+2 = 2 → result[1] = 2 i=2: running = 2+3 = 5 → result[2] = 5 i=3: running = 5-1 = 4 → result[3] = 4 i=4: running = 4-2 = 2 → result[4] = 2 i=5: running = 2+1 = 3 → result[5] = 3

**Sample Output:**

2 5 4 2 3

**Complexity Analysis:**
- **Time:** `O(N + M)` — `O(1)` per update, `O(N)` reconstruction
- **Space:** `O(N)` — just the difference array

> ⚠️ **Common Mistake:** Declaring `diff` with size N+1 instead of N+2. When R=N, you write to `diff[R+1] = diff[N+1]`, which needs to exist!

---

## 3.2.6 2D Prefix Sums

For 2D grids, you can extend prefix sums to answer rectangular range queries in `O(1)`.

Given an R×C grid, define `P[r][c]` = sum of all elements in the rectangle from (1,1) to (r,c).

### Building the 2D Prefix Sum

P[r][c] = A[r][c] + P[r-1][c] + P[r][c-1] - P[r-1][c-1]

The subtraction removes the overlap (otherwise the top-left rectangle is counted twice).

> 💡 **Key Insight (Inclusion-Exclusion):** Visualize the four rectangles:
> - `P[r-1][c]` = the "top" rectangle
> - `P[r][c-1]` = the "left" rectangle
> - `P[r-1][c-1]` = the "top-left corner" (counted in BOTH above — so subtract once)
> - `A[r][c]` = the single new cell

### Step-by-Step 2D Prefix Sum Worked Example

Let's trace through a 4×4 grid:

**Original Grid A:**

 c=1  c=2  c=3  c=4

r=1: 1 2 3 4 r=2: 5 6 7 8 r=3: 9 10 11 12 r=4: 13 14 15 16

**Building P step by step (left-to-right, top-to-bottom):**

P[1][1] = A[1][1] = 1

P[1][2] = A[1][2] + P[0][2] + P[1][1] - P[0][1] = 2 + 0 + 1 - 0 = 3 P[1][3] = A[1][3] + P[0][3] + P[1][2] - P[0][2] = 3 + 0 + 3 - 0 = 6 P[1][4] = 4 + 0 + 6 - 0 = 10

P[2][1] = A[2][1] + P[1][1] + P[2][0] - P[1][0] = 5 + 1 + 0 - 0 = 6 P[2][2] = A[2][2] + P[1][2] + P[2][1] - P[1][1] = 6 + 3 + 6 - 1 = 14 P[2][3] = 7 + 6 + 14 - 3 = 24 P[2][4] = 8 + 10 + 24 - 6 = 36

P[3][1] = 9 + 6 + 0 - 0 = 15 P[3][2] = 10 + 14 + 15 - 6 = 33 P[3][3] = 11 + 24 + 33 - 14 = 54 P[3][4] = 12 + 36 + 54 - 24 = 78

P[4][1] = 13 + 15 + 0 - 0 = 28 P[4][2] = 14 + 33 + 28 - 15 = 60 P[4][3] = 15 + 54 + 60 - 33 = 96 P[4][4] = 16 + 78 + 96 - 54 = 136

**Resulting prefix sum grid P:**

 c=1  c=2  c=3  c=4

r=1: 1 3 6 10 r=2: 6 14 24 36 r=3: 15 33 54 78 r=4: 28 60 96 136

**Query: Sum of subgrid (r1=2, c1=2) to (r2=3, c2=3):**

ans = P[3][3] - P[1][3] - P[3][1] + P[1][1] = 54 - 6 - 15 + 1 = 34

Verify: A[2][2]+A[2][3]+A[3][2]+A[3][3] = 6+7+10+11 = 34 ✓

**Visualization of the inclusion-exclusion:**

![2D Prefix Sum Inclusion-Exclusion](../images/prefix_sum_2d_inclusion_exclusion.svg)

```cpp
// Solution: 2D Prefix Sums — Build O(R×C), Query O(1)
#include <bits/stdc++.h>
using namespace std;

const int MAXR = 1001, MAXC = 1001;
int A[MAXR][MAXC];
long long P[MAXR][MAXC];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int R, C;
    cin >> R >> C;

    for (int r = 1; r <= R; r++)
        for (int c = 1; c <= C; c++)
            cin >> A[r][c];

    // Step 1: Build 2D prefix sum — O(R × C)
    for (int r = 1; r <= R; r++) {
        for (int c = 1; c <= C; c++) {
            P[r][c] = A[r][c]
                    + P[r-1][c]    // rectangle above
                    + P[r][c-1]    // rectangle to the left
                    - P[r-1][c-1]; // ← KEY LINE: remove overlap (counted twice)
        }
    }

    // Step 2: Answer each query in O(1)
    int q;
    cin >> q;
    while (q--) {
        int r1, c1, r2, c2;
        cin >> r1 >> c1 >> r2 >> c2;
        long long ans = P[r2][c2]
                      - P[r1-1][c2]    // subtract top strip
                      - P[r2][c1-1]    // subtract left strip
                      + P[r1-1][c1-1]; // add back top-left corner
        cout << ans << "\n";
    }

    return 0;
}

Complexity Analysis:

• Build time: O(R × C)
• Query time: O(1) per query
• Space: O(R × C)

⚠️ Common Mistake: Forgetting to add P[r1-1][c1-1] back in the query formula. The top strip and left strip both include the top-left corner, so it gets subtracted twice — you need to add it back once!

3.2.7 USACO Example: Max Subarray Sum

Problem (variation of Kadane's algorithm): Find the contiguous subarray with the maximum sum.

// Solution: Kadane's Algorithm — O(N) Time, O(1) Space
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<int> A(n);
    for (int &x : A) cin >> x;

    // Kadane's Algorithm: O(n)
    long long maxSum = LLONG_MIN;  // LLONG_MIN = smallest long long
    long long current = 0;

    for (int i = 0; i < n; i++) {
        current += A[i];
        maxSum = max(maxSum, current);
        if (current < 0) current = 0;  // ← KEY LINE: restart if sum goes negative
    }

    cout << maxSum << "\n";

    return 0;
}

💡 Key Insight: Why reset current to 0 when it goes negative? Because a negative prefix sum hurts any future subarray. If the running sum so far is -5, any future subarray starting fresh (sum 0) will always beat continuing from -5.

Alternative with prefix sums: The max subarray sum equals max over all pairs (i,j) of P[j] - P[i-1]. For each j, this is maximized when P[i-1] is minimized. Track the running minimum of prefix sums!

// Alternative: Min Prefix Trick — also O(N)
long long maxSum = LLONG_MIN, minPrefix = 0, prefix = 0;
for (int x : A) {
    prefix += x;
    maxSum = max(maxSum, prefix - minPrefix);  // best sum ending here
    minPrefix = min(minPrefix, prefix);         // track minimum prefix seen so far
    // ⚠️ 注意：minPrefix 的更新必须在 maxSum 之后。
    // 若提前更新 minPrefix，相当于允许空子数组（长度为0，和为0）参与比较，
    // 会导致结果在全负数组时错误地返回 0 而非最大负数。
}

⚠️ Common Mistakes in Chapter 3.2

1. Off-by-one in range queries: P[R] - P[L] instead of P[R] - P[L-1]. Always verify on a small example.
2. Overflow: Prefix sums of large values can exceed int range (2×10^9). Use long long for the prefix array even if elements are int.
3. 2D query formula: Forgetting the +P[r1-1][c1-1] term in the 2D query — a very easy slip.
4. Difference array size: Declaring diff[n+1] when you need diff[n+2] (because you write to index r+1 which could be n+1).
5. 1-indexing vs 0-indexing: If you use 0-indexed prefix sums, the query formula changes to P[R+1] - P[L]. Pick one convention and stick to it within a problem.

Chapter Summary

📌 Key Takeaways

*After O(N) reconstruction pass to read all values.

🧩 Core Formula Quick Reference

❓ FAQ

Q1: What is the relationship between prefix sums and difference arrays?

A: They are inverse operations. Taking the prefix sum of an array gives the prefix sum array; taking the difference (adjacent element differences) of the prefix sum array restores the original. Conversely, taking the prefix sum of a difference array also restores the original. This is analogous to integration and differentiation in mathematics.

Q2: When to use prefix sums vs. difference arrays?

A: Rule of thumb — look at the operation type:

• Multiple range sum queries → prefix sum (preprocess O(N), query O(1))
• Multiple range add/subtract operations → difference array (update O(1), restore O(N) at the end)
• If both operations alternate, you need a more advanced data structure (like Segment Tree in Chapter 3.9)

Q3: Can prefix sums handle dynamic modifications? (array elements change)

A: No. Prefix sums are a one-time preprocessing; the array cannot change afterward. If elements are modified, use Fenwick Tree (BIT) or Segment Tree, which support point updates and range queries in O(log N) time.

Q4: Why are there two versions of Kadane's algorithm (current=0 vs minPrefix)?

A: Both are essentially the same, both O(N). The first (classic Kadane) is more intuitive: restart when the current subarray sum goes negative. The second (min-prefix method) uses prefix sum thinking: max subarray = max(P[j] - P[i-1]) = max(P[j]) - min(P[i]). Choose based on personal preference.

Q5: What are the space constraints for 2D prefix sums?

A: If R, C are both up to 10^4, the P array needs 10^8 long long values (about 800MB) — exceeding memory limits. Generally R×C ≤ 10^6~10^7 is safe. For larger grids, consider compression or offline processing.

🔗 Connections to Later Chapters

• Chapter 3.4 (Two Pointers): sliding window can also do range queries, but only for fixed-size or monotonically moving windows; prefix sums are more general
• Chapter 3.3 (Sorting & Searching): binary search can combine with prefix sums — e.g., binary search on the prefix sum array for the first position ≥ target
• Chapter 3.9 (Segment Trees): solves "dynamic update + range query" problems that prefix sums cannot handle
• Chapters 6.1–6.3 (DP): many state transitions involve range sums; prefix sums are an important tool for optimizing DP
• The difference array idea ("+V at start, -V after end") recurs in sweep line algorithms, event sorting, and other advanced techniques

Practice Problems

Problem 3.2.1 — Range Sum 🟢 Easy Read N integers and Q queries. Each query gives L and R. Print the sum of elements from index L to R (1-indexed).

Problem 3.2.2 — Range Add, Point Query 🟢 Easy Start with N zeros. Process M operations: each operation adds V to all positions from L to R. After all operations, print the value at each position. (Use difference array)

Problem 3.2.3 — Rectangular Sum 🟡 Medium Read an N×M grid of integers and Q queries. Each query gives (r1,c1,r2,c2). Print the sum of the subgrid.

Problem 3.2.4 — USACO 2016 January Bronze: Mowing the Field 🔴 Hard (Challenge) Farmer John mows grass along a path. Cells visited more than once contribute to "double-mowed" area. Use a 2D array and count cells visited at least twice.

Problem 3.2.5 — Maximum Subarray (Negative numbers allowed) 🟡 Medium Read N integers (possibly negative). Find the maximum possible sum of a contiguous subarray. What if all numbers are negative?

🏆 Challenge Problem: Cows and Paint Buckets An N×M grid contains paint buckets, each with a positive value. You can select any rectangular subgrid. Your score is the maximum value in your subgrid minus the sum of all border cells of your subgrid. Find the optimal rectangle. (N, M ≤ 500)

Solution approach: 2D prefix sums for sums + careful enumeration of all rectangles.

Chapter 3.3: Sorting & Searching

📝 Before You Continue: You should be comfortable with arrays, vectors, and basic loops (Chapters 2.2–2.3). Familiarity with std::sort from Chapter 3.1 helps, but this chapter covers it in depth.

Sorting and searching are two of the most fundamental operations in computer science. In USACO, a huge fraction of problems become easy once you sort the data correctly. And binary search — the ability to search a sorted array in O(log n) — is a technique you'll reach for again and again.

3.3.1 Why Sorting Matters

Consider this problem: "Given N cow heights, find the two cows whose heights are closest together."

• Unsorted approach: Compare every pair → O(N²). For N = 10^5, that's 10^10 operations. TLE.
• Sorted approach: Sort the heights → O(N log N). Then the closest pair must be adjacent! Check N-1 pairs → O(N). Total: O(N log N). ✓

💡 Key Insight: Sorting transforms many O(N²) brute-force solutions into O(N log N) or O(N) solutions. When you see "find the pair with property X" or "find the minimum/maximum of something involving two elements," always consider sorting first.

Complexity Analysis:

• Sorting: O(N log N) time, O(log N) space (for the recursion stack in Introsort / quicksort)
• After sorting: adjacent comparisons or two-pointer techniques are O(N)

3.3.2 How Sorting Works (Conceptual)

You don't need to implement sorting algorithms yourself — std::sort does it for you. But understanding the ideas helps you reason about time complexity and choose the right approach.

Here are four classic sorting algorithms, each with an interactive visualization to help you understand how they work.

🫧 Bubble Sort — O(N²)

Repeatedly scan the array, swapping adjacent elements that are out of order. Each pass "bubbles" the current maximum to the end:

Pass 1: [64,34,25,12,22,11,90] → 90 bubbles to end
Pass 2: [34,25,12,22,11,64,90] → 64 bubbles to second-to-last
...

Bubble sort is O(N²). Never use it on large inputs in competitive programming. We cover it only because it's conceptually the simplest.

🃏 Insertion Sort — O(N²) / O(N) best case

Divide the array into a left "sorted region" and a right "unsorted region." Each step takes the first element of the unsorted region and inserts it into the correct position in the sorted region:

Start: [64 | 34, 25, 12, 22, 11, 90]   ← | sorted on left
i=1:   [34, 64 | 25, 12, 22, 11, 90]   ← 34 inserted before 64
i=2:   [25, 34, 64 | 12, 22, 11, 90]   ← 25 inserted at front
i=3:   [12, 25, 34, 64 | 22, 11, 90]   ← 12 inserted at front
...

💡 Insertion sort's strength: Very fast on nearly-sorted arrays (approaches O(N)). std::sort switches to insertion sort for small subarrays.

void insertionSort(vector<int>& a) {
    int n = a.size();
    for (int i = 1; i < n; i++) {
        int key = a[i];   // element to insert
        int j = i - 1;
        // shift elements greater than key one position to the right
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;  // place key in its correct position
    }
}

🔀 Merge Sort — O(N log N) always

Divide and conquer: recursively split the array in half, then merge the two sorted halves back together:

[38, 27, 43, 3, 9, 82, 10]
        ↓ split recursively
[38,27,43,3]    [9,82,10]
[38,27] [43,3]  [9,82] [10]
[38][27][43][3] [9][82][10]
        ↓ merge bottom-up
[27,38] [3,43]  [9,82] [10]
  [3,27,38,43]    [9,10,82]
      [3,9,10,27,38,43,82] ✓

Merge sort is O(N log N) in all cases and is a stable sort.

void merge(vector<int>& a, int lo, int mid, int hi) {
    vector<int> tmp(a.begin() + lo, a.begin() + hi + 1);
    int i = lo, j = mid + 1, k = lo;
    while (i <= mid && j <= hi) {
        if (tmp[i - lo] <= tmp[j - lo])
            a[k++] = tmp[i++ - lo];  // take smaller from left half
        else
            a[k++] = tmp[j++ - lo];  // take smaller from right half
    }
    while (i <= mid) a[k++] = tmp[i++ - lo];  // append remaining left
    while (j <= hi)  a[k++] = tmp[j++ - lo];  // append remaining right
}

void mergeSort(vector<int>& a, int lo, int hi) {
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;
    mergeSort(a, lo, mid);       // sort left half
    mergeSort(a, mid + 1, hi);   // sort right half
    merge(a, lo, mid, hi);       // merge two sorted halves
}

⚡ Quicksort — O(N log N) average

Quicksort is one of the core algorithms underlying std::sort. Its key idea is divide and conquer:

1. Pick a pivot element (typically the last element)
2. Partition: move all elements ≤ pivot to the left, all > pivot to the right; pivot lands in its final position
3. Recurse on the left and right subarrays

[8, 3, 6, 1, 9, 2, 7, 4]   ← pivot = 4
         ↓ partition
[3, 1, 2, 4, 9, 6, 7, 8]   ← 4 in final position; left ≤ 4, right > 4
 ↑_______↑  ↑  ↑__________↑
 left subarray  right subarray

Recurse on [3,1,2] → [1,2,3]
Recurse on [9,6,7,8] → [6,7,8,9]

Final: [1, 2, 3, 4, 6, 7, 8, 9] ✓

// Partition arr[lo..hi] using last element as pivot.
// Returns the final index of the pivot.
int partition(vector<int>& arr, int lo, int hi) {
    int pivot = arr[hi];   // choose last element as pivot
    int i = lo - 1;        // i points to end of "≤ pivot" region

    for (int j = lo; j < hi; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);  // bring arr[j] into ≤ pivot region
        }
    }
    swap(arr[i + 1], arr[hi]);  // place pivot in its final position
    return i + 1;               // return pivot's index
}

void quickSort(vector<int>& arr, int lo, int hi) {
    if (lo >= hi) return;           // base case: subarray length ≤ 1
    int p = partition(arr, lo, hi); // p is pivot's final position
    quickSort(arr, lo, p - 1);      // sort left subarray
    quickSort(arr, p + 1, hi);      // sort right subarray
}

Visual: Quicksort Partition

The diagram above illustrates how the partition operation rearranges elements around the pivot. Elements ≤ pivot move to the left; elements > pivot move to the right. The pivot then lands in its final sorted position.

⚠️ Worst case: If the pivot is always the max or min (e.g., already-sorted input), recursion depth degrades to O(N) and total time becomes O(N²). std::sort avoids this via random pivot selection or median-of-three, guaranteeing O(N log N) worst case.

3.3.3 std::sort in Practice

⚠️ Stability Note: std::sort is NOT stable — it uses Introsort (Quicksort + Heapsort + Insertion sort hybrid), which does not preserve the relative order of equal elements. If you need stable sorting, use std::stable_sort instead (see the comparison table in this section).

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<int> v(n);
    for (int &x : v) cin >> x;

    // Sort ascending
    sort(v.begin(), v.end());

    // Sort descending
    sort(v.begin(), v.end(), greater<int>());

    // Sort only part of a vector (indices 2 through 5 inclusive)
    sort(v.begin() + 2, v.begin() + 6);

    for (int x : v) cout << x << " ";
    cout << "\n";

    return 0;
}

Sorting by Multiple Criteria

Often you want to sort by one field, and break ties with another. With pair, this is automatic (sorts by .first, then .second):

vector<pair<int, string>> students;
students.push_back({85, "Alice"});
students.push_back({92, "Bob"});
students.push_back({85, "Charlie"});

sort(students.begin(), students.end());
// Result: {85, "Alice"}, {85, "Charlie"}, {92, "Bob"}
// Sorted by score first, then alphabetically by name

Custom Comparators

A comparator is a function that returns true if the first argument should come before the second in the sorted order.

The clearest way to write a comparator is as a standalone function:

struct Cow {
    string name;
    int weight;
    int height;
};

// Sort by weight ascending; break ties by height descending
bool cmpCow(const Cow &a, const Cow &b) {
    if (a.weight != b.weight) return a.weight < b.weight;  // lighter first
    return a.height > b.height;                             // taller first (tie-break)
}

int main() {
    vector<Cow> cows = {{"Bessie", 500, 140}, {"Elsie", 480, 135}, {"Moo", 500, 138}};

    sort(cows.begin(), cows.end(), cmpCow);

    for (auto &c : cows) {
        cout << c.name << " " << c.weight << " " << c.height << "\n";
    }
    // Output:
    // Elsie 480 135
    // Bessie 500 140
    // Moo 500 138
    return 0;
}

💡 Style Note: Defining cmp as a standalone function (rather than an inline lambda) makes the sorting logic easier to read, test, and reuse — especially when the comparison involves multiple fields.

Sorting Algorithm Stability

⚠️ Important: std::sort is NOT stable — equal elements may appear in any order after sorting. Use std::stable_sort if relative order of equal elements must be preserved.

Sorting Algorithm Stability Comparison

📝 Note: std::sort uses Introsort (a hybrid of Quicksort + Heapsort + Insertion sort). Because Quicksort is not stable, std::sort makes no guarantee on the relative order of equal elements. When you sort students by score and need students with the same score to remain in their original order, use std::stable_sort.

Visual: Sorting Algorithm Comparison

This chart compares the time complexity, space usage, and stability of common sorting algorithms, helping you choose the right one for each situation.

Counting Sort — O(N+K) for Small Value Ranges

When values are bounded integers in a small range [0, MAXVAL], counting sort beats std::sort by a wide margin:

// Counting sort: for integers in range [0, MAXVAL]
// Time O(N+MAXVAL), stable sort
void countingSort(vector<int>& arr, int maxVal) {
    vector<int> cnt(maxVal + 1, 0);
    for (int x : arr) cnt[x]++;
    int idx = 0;
    for (int v = 0; v <= maxVal; v++)
        while (cnt[v]--) arr[idx++] = v;
}
// USACO use case: faster than std::sort when value range is small (e.g., cow IDs 1-1000)

When to use counting sort in USACO:

• Cow IDs in range [1, 1000], N = 10^6 → counting sort is O(N + 1000) vs O(N log N)
• Grade values [0, 100] → trivially fast
• Color categories [0, 3] → instant

Caution: If MAXVAL is large (e.g., 10^9), counting sort requires O(MAXVAL) memory — don't use it. Coordinate compress first (Section 3.3.6), then count.

3.3.4 Binary Search

Binary search finds a target in a sorted array in O(log n) — instead of O(n) for linear search.

Analogy: Searching for a word in a dictionary. You don't start from A and read every entry — you open to the middle, check if your word is before or after, then repeat. Each step cuts the search space in half: after k steps, you've gone from N candidates to N/2^k. When N/2^k < 1, you're done — that takes k = log₂(N) steps.

💡 Key Insight: Binary search works whenever you have a monotone predicate — a condition that is false false false ... true true true (or the reverse). You can binary search for the boundary between false and true in O(log N).

Visual: Binary Search in Action

The diagram above shows a single-step binary search finding 7 in [1,3,5,7,9,11,13]. The left (L), right (R), and mid (M) pointers are shown. The key insight: computing mid = left + (right - left) / 2 avoids integer overflow compared to (left + right) / 2.

Manual Binary Search

// Solution: Binary Search — O(log N)
#include <bits/stdc++.h>
using namespace std;

// Returns index of target in sorted arr, or -1 if not found
int binarySearch(const vector<int> &arr, int target) {
    int lo = 0, hi = (int)arr.size() - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;  // ← KEY LINE: avoid overflow (don't use (lo+hi)/2)

        if (arr[mid] == target) {
            return mid;         // found!
        } else if (arr[mid] < target) {
            lo = mid + 1;       // target is in the right half
        } else {
            hi = mid - 1;       // target is in the left half
        }
    }

    return -1;  // not found
}

int main() {
    vector<int> v = {1, 3, 5, 7, 9, 11, 13, 15};
    cout << binarySearch(v, 7) << "\n";   // 3 (index)
    cout << binarySearch(v, 6) << "\n";   // -1 (not found)
    return 0;
}

Step-by-step trace for searching 7 in [1, 3, 5, 7, 9, 11, 13, 15]:

lo=0, hi=7: mid=3, arr[3]=7 → FOUND at index 3 ✓

Searching for 6:
lo=0, hi=7: mid=3, arr[3]=7 > 6 → hi=2
lo=0, hi=2: mid=1, arr[1]=3 < 6 → lo=2
lo=2, hi=2: mid=2, arr[2]=5 < 6 → lo=3
lo=3 > hi=2: loop ends → return -1 ✓

Why lo + (hi - lo) / 2? If lo and hi are both large (close to INT_MAX), then lo + hi overflows! This formula is equivalent but safe.

The STL Way: lower_bound and upper_bound

These are almost always what you actually want in competitive programming:

// STL Binary Search Operations — all O(log N)
#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> v = {1, 3, 3, 5, 7, 9, 9, 11};

    // lower_bound: iterator to first element >= target
    auto lb = lower_bound(v.begin(), v.end(), 3);
    cout << *lb << "\n";                    // 3 (first 3)
    cout << lb - v.begin() << "\n";         // 1 (index)

    // upper_bound: iterator to first element > target
    auto ub = upper_bound(v.begin(), v.end(), 3);
    cout << *ub << "\n";                    // 5 (first element after all 3s)
    cout << ub - v.begin() << "\n";         // 3 (index)

    // Count occurrences: upper_bound - lower_bound
    int count_of_3 = upper_bound(v.begin(), v.end(), 3)
                   - lower_bound(v.begin(), v.end(), 3);
    cout << count_of_3 << "\n";   // 2

    // Check if value exists
    bool exists = binary_search(v.begin(), v.end(), 7);
    cout << exists << "\n";  // 1

    // Find largest value <= target (floor)
    auto it = upper_bound(v.begin(), v.end(), 6);
    if (it != v.begin()) {
        --it;
        cout << *it << "\n";  // 5 (largest value <= 6)
    }

    return 0;
}

⚠️ Common Mistake: Using lower_bound/upper_bound on an unsorted container. These functions assume sorted order — on unsorted data, they give wrong results with no error!

3.3.5 Binary Search on the Answer

This is one of the most powerful and commonly-tested techniques in USACO Silver. The idea:

Instead of searching for a value in an array, binary search over the answer space itself.

When does this apply? When:

1. The answer is a number in some range [lo, hi]
2. There's a function canAchieve(X) that checks if X is feasible
3. The function is monotone: if X works, all values ≤ X also work (or all ≥ X work)

💡 Key Insight: Monotonicity means there's a "threshold" separating feasible from infeasible answers. Binary search finds this threshold in O(log(hi-lo)) calls to canAchieve. If each call takes O(f(N)), total time is O(f(N) × log(answer_range)).

Classic Example: Aggressive Cows (USACO 2011 March Silver)

Problem: N stalls at positions p[1..N], place C cows to maximize the minimum distance between any two cows.

Why binary search? If we can place cows with minimum gap D, we can also place them with gap D-1. So feasibility is monotone: there's a threshold D* where ≥ D* is infeasible and < D* is feasible. We binary search for D*.

The canPlace(minDist) function: Place the first cow at the leftmost stall, then greedily pick the next stall that is at least minDist away. Count how many cows we can place this way — if ≥ C, return true.

// Solution: Binary Search on Answer — O(N log N log(max_distance))
#include <bits/stdc++.h>
using namespace std;

int n, c;
vector<int> stalls;

// Can we place c cows such that the minimum gap between any two cows is >= minDist?
bool canPlace(int minDist) {
    int placed = 1;           // place first cow at stall 0
    int lastPos = stalls[0];  // position of last placed cow

    for (int i = 1; i < n; i++) {
        if (stalls[i] - lastPos >= minDist) {  // this stall is far enough
            placed++;
            lastPos = stalls[i];
        }
    }
    return placed >= c;  // did we place all c cows?
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> c;
    stalls.resize(n);
    for (int &x : stalls) cin >> x;
    sort(stalls.begin(), stalls.end());  // must sort first!

    // Binary search on the answer: what's the maximum possible minimum distance?
    int lo = 1, hi = stalls.back() - stalls.front();
    int answer = 0;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (canPlace(mid)) {
            answer = mid;    // mid works, try larger
            lo = mid + 1;
        } else {
            hi = mid - 1;    // mid doesn't work, try smaller
        }
    }

    cout << answer << "\n";
    return 0;
}

Trace for stalls = [1, 2, 4, 8, 9], C = 3:

Sorted: [1, 2, 4, 8, 9]
lo=1, hi=8

mid=4: canPlace(4)?
  Place cow at 1. Next stall ≥ 1+4=5: that's 8. Place at 8.
  Next stall ≥ 8+4=12: none. Total placed=2 < 3. Return false.
  → hi = 3

mid=2: canPlace(2)?
  Place cow at 1. Next stall ≥ 3: that's 4. Place at 4.
  Next stall ≥ 6: that's 8. Place at 8. Total placed=3 ≥ 3. Return true.
  → answer=2, lo=3

mid=3: canPlace(3)?
  Place cow at 1. Next ≥ 4: that's 4. Place at 4.
  Next ≥ 7: that's 8. Place at 8. Total placed=3 ≥ 3. Return true.
  → answer=3, lo=4

lo=4 > hi=3: done. Answer = 3

Another Classic: Minimum Time to Complete Tasks (Rope Cutting)

Problem: Given N ropes of lengths L[i], cut K ropes of equal length. What's the maximum length you can cut each piece to?

// Can we get K pieces of length >= len from the ropes?
bool canCut(vector<int> &ropes, long long len, int K) {
    long long count = 0;
    for (int r : ropes) count += r / len;  // pieces from each rope
    return count >= K;
}

// Binary search: maximize len such that canCut(len) is true
long long lo = 1, hi = *max_element(ropes.begin(), ropes.end());
long long answer = 0;
while (lo <= hi) {
    long long mid = lo + (hi - lo) / 2;
    if (canCut(ropes, mid, K)) {
        answer = mid;
        lo = mid + 1;
    } else {
        hi = mid - 1;
    }
}

Template for Binary Search on Answer:

// Generic template — adapt lo, hi, and check() for your problem
long long lo = min_possible_answer;
long long hi = max_possible_answer;
long long answer = lo;  // or -1 if no valid answer exists

while (lo <= hi) {
    long long mid = lo + (hi - lo) / 2;
    if (check(mid)) {       // mid is feasible
        answer = mid;       // save it
        lo = mid + 1;       // try to do better (or worse, depending on problem)
    } else {
        hi = mid - 1;       // mid not feasible, go lower
    }
}

🏆 USACO Tip: Whenever a USACO problem asks "find the maximum X such that [some condition]" or "find the minimum X such that [some condition]," consider binary search on the answer. This technique solves USACO Silver problems frequently.

3.3.6 Coordinate Compression

Sometimes values are large (up to 10^9), but there are few distinct values. Coordinate compression maps them to small indices (0, 1, 2, ...).

// Solution: Coordinate Compression — O(N log N)
#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> A = {100, 500, 200, 100, 700, 200};

    // Step 1: Get sorted unique values
    vector<int> sorted_unique = A;
    sort(sorted_unique.begin(), sorted_unique.end());
    sorted_unique.erase(unique(sorted_unique.begin(), sorted_unique.end()),
                        sorted_unique.end());
    // sorted_unique = {100, 200, 500, 700}

    // Step 2: Map each original value to its compressed index
    vector<int> compressed(A.size());
    for (int i = 0; i < (int)A.size(); i++) {
        compressed[i] = lower_bound(sorted_unique.begin(), sorted_unique.end(), A[i])
                        - sorted_unique.begin();
        // 100→0, 200→1, 500→2, 700→3
    }

    for (int x : compressed) cout << x << " ";
    cout << "\n";  // 0 2 1 0 3 1

    return 0;
}

⚠️ Common Mistakes in Chapter 3.3

1. Sorting with wrong comparator: Your lambda must return true if a should come BEFORE b. If it returns true for a == b, you get undefined behavior (strict weak ordering violation).
2. Binary search on unsorted array: lower_bound and upper_bound assume sorted order. On unsorted data, results are meaningless.
3. Off-by-one in binary search: lo <= hi vs lo < hi matters. When in doubt, test your binary search on a 1-element and 2-element array.
4. Wrong answer range in "binary search on answer": If the answer could be 0, set lo = 0, not lo = 1. If it could be very large, make sure hi is large enough (use long long if necessary).
5. Integer overflow in mid computation: Always write mid = lo + (hi - lo) / 2, never (lo + hi) / 2.

Chapter Summary

📌 Key Takeaways

🧩 Binary Search Template Quick Reference

❓ FAQ

Q1: Is sort's time complexity O(N log N) or O(N²)?

A: C++'s std::sort uses Introsort (a hybrid of Quicksort + Heapsort + Insertion sort), guaranteeing O(N log N) worst case. No need to worry about degrading to O(N²). But note: if your custom comparator doesn't satisfy strict weak ordering, behavior is undefined (may infinite loop or crash).

Q2: What's the difference between lo <= hi and lo < hi in binary search?

A: The two styles correspond to different templates:

• while (lo <= hi): when search ends, lo > hi, answer is stored in answer variable. Good for "find target value" or "maximize value satisfying condition".
• while (lo < hi): when search ends, lo == hi, answer is lo. Good for "minimize value satisfying condition". Both can solve all problems; the key is pairing with the correct update rule. Beginners should pick one style and stick with it.

Q3: What problems is "binary search on answer" applicable to? How to identify them?

A: Three signals: ① The problem asks "the maximum/minimum X such that..."; ② There exists a decision function check(X) that can determine feasibility in polynomial time; ③ The decision function is monotone (X feasible → X-1 also feasible, or vice versa). If all three hold, binary search on answer applies.

Q4: What is coordinate compression actually useful for?

A: When the value range is large (e.g., 10^9) but the number of distinct values is small (e.g., 10^5), coordinate compression maps large values to small indices 0~N-1. This lets you use arrays instead of maps (faster), or perform prefix sums/BIT operations over the value domain. Frequently needed in USACO Silver.

Q5: Why can't the sort comparator use <=?

A: C++ sorting requires the comparator to satisfy strict weak ordering: when a == b, comp(a,b) must return false. <= returns true when a==b, violating this rule. The result is undefined behavior — may infinite loop, crash, or produce incorrect ordering.

🔗 Connections to Later Chapters

• Chapter 3.4 (Two Pointers): two-pointer techniques are often used after sorting — sort first O(N log N), then two pointers O(N)
• Chapter 3.2 (Prefix Sums): prefix sum arrays are naturally ordered, enabling binary search on them (e.g., find first prefix sum ≥ target)
• Chapters 4.1 & 5.4 (Greedy + Shortest Paths): Dijkstra internally uses a priority queue + greedy strategy, fundamentally related to sorting
• Chapter 6.2 (DP): LIS (Longest Increasing Subsequence) can be optimized to O(N log N) using binary search
• "Binary search on answer" is one of the most core techniques in USACO Silver, also frequently combined in Chapter 4.1 (Greedy)

Practice Problems

Problem 3.3.1 — Closest Pair 🟢 Easy Read N integers. Find the pair with the minimum difference. Print that difference.

Problem 3.3.2 — Room Allocation 🟡 Medium Read N events, each with start and end time. What is the maximum number of events that overlap at any single moment? (Hint: sort start/end times together and sweep)

Problem 3.3.3 — Kth Smallest 🟡 Medium Read N integers. Find the K-th smallest element (1-indexed).

Solution sketch: Binary search on the answer X. Count how many elements ≤ X using a scan — this is O(N). Total: O(N log(max_value)).

Problem 3.3.4 — Aggressive Cows (USACO 2011 March Silver) 🔴 Hard N stalls at positions p[1..N], place C cows to maximize the minimum distance between any two cows. (Full implementation of the example above.)

Solution sketch: Sort stalls. Binary search on minimum distance D. For each D, greedily place cows: always place next cow at the earliest stall that is ≥ D away from the last cow.

Problem 3.3.5 — Binary Search on Answer: Painter's Partition 🔴 Hard N boards with widths w[1..N]. K painters, each takes 1 unit time per unit width. Assign contiguous boards to painters to minimize total time (the maximum any single painter works).

Solution sketch: Binary search on the answer T (max time any painter works). Check: greedily assign boards to painters, starting a new painter whenever the current one would exceed T. If ≤ K painters suffice, T is feasible.

🏆 Challenge Problem: USACO 2016 February Silver: Fencing the Cows Fence all N points in a convex region using minimum fencing. This is the Convex Hull problem — look up the Graham scan or Jarvis march algorithms. While this is a Gold-level topic, thinking about it now will prime your intuition.

3.3.7 Advanced Binary Search on Answer — Three Examples

Example 1: Minimum Time to Finish Tasks (Parametric Search)

Problem: N workers, M tasks with effort[i]. Assign tasks to workers (each worker gets contiguous tasks). Minimize the maximum time any worker spends (minimize the bottleneck).

This is the "Painter's Partition" problem. Binary search on the answer (max time T), check if T is achievable.

// Check: can we distribute tasks among K workers so max work <= T?
bool canFinish(vector<int>& tasks, int K, long long T) {
    int workers = 1;
    long long current = 0;
    for (int t : tasks) {
        if (t > T) return false;  // single task exceeds T — impossible
        if (current + t > T) {
            workers++;             // start new worker
            current = t;
            if (workers > K) return false;
        } else {
            current += t;
        }
    }
    return true;
}

// Binary search on T
long long lo = *max_element(tasks.begin(), tasks.end());  // minimum possible T
long long hi = accumulate(tasks.begin(), tasks.end(), 0LL);  // maximum T (1 worker)

while (lo < hi) {
    long long mid = lo + (hi - lo) / 2;
    if (canFinish(tasks, K, mid)) hi = mid;  // mid works, try smaller
    else lo = mid + 1;                        // mid doesn't work, need larger
}
cout << lo << "\n";  // minimum possible maximum time

📝 Note: Here we binary search for the minimum feasible T, so we use hi = mid when feasible (not answer = mid; lo = mid+1). The two templates are mirror images.

Example 2: Kth Smallest in Multiplication Table

Problem: N×M multiplication table. Find the Kth smallest value.

The table has values i*j for 1≤i≤N, 1≤j≤M. Binary search on the answer X: count how many values are ≤ X.

// Count values <= X in N×M multiplication table
long long countLE(long long X, int N, int M) {
    long long count = 0;
    for (int i = 1; i <= N; i++) {
        count += min((long long)M, X / i);
        // Row i has values i, 2i, ..., Mi
        // Count of values <= X in row i: min(M, floor(X/i))
    }
    return count;
}

// Binary search for Kth smallest
long long lo = 1, hi = (long long)N * M;
while (lo < hi) {
    long long mid = lo + (hi - lo) / 2;
    if (countLE(mid, N, M) >= K) hi = mid;
    else lo = mid + 1;
}
cout << lo << "\n";

Complexity: O(N log(NM)) — O(N) per check, O(log(NM)) iterations.

Example 3: USACO-Style Cable Length (Agri-Net inspired)

Problem: Given N farm locations, connect them all with cables. The cables must be at most length L. Find the maximum L such that you can form a spanning tree with all edges ≤ L.

// Binary search on maximum cable length L
// Check: does a spanning tree exist using only edges of length <= L?
// (This reduces to: is the graph connected when restricted to edges <= L?)
bool canConnect(vector<tuple<int,int,int>>& edges, int n, int L) {
    DSU dsu(n);
    for (auto [w, u, v] : edges) {
        if (w <= L) dsu.unite(u, v);
    }
    return dsu.components == 1;  // all nodes connected
}

3.3.8 lower_bound / upper_bound Complete Cheat Sheet

vector<int> v = {1, 3, 3, 5, 7, 9, 9, 11};
//                0  1  2  3  4  5  6   7

// ── lower_bound: first position >= x ──
lower_bound(all, 3)  → index 1  (first 3)
lower_bound(all, 4)  → index 3  (first element >= 4, which is 5)
lower_bound(all, 12) → index 8  (past-end: no element ≥ 12 exists in the array)

// ── upper_bound: first position > x ──
upper_bound(all, 3)  → index 3  (first element after all 3s)
upper_bound(all, 4)  → index 3  (same as above: no 4s)
upper_bound(all, 11) → index 8  (past-end)

// ── Derived operations ──
// Count occurrences of x:
ub(x) - lb(x) = upper_bound(all,3) - lower_bound(all,3) = 3-1 = 2 ✓

// Does x exist?
binary_search(all, x)  // O(log N), returns bool

// Largest value <= x (floor):
auto it = upper_bound(all, x);
if (it != v.begin()) cout << *prev(it);  // *--it

// Smallest value >= x (ceil):
auto it = lower_bound(all, x);
if (it != v.end()) cout << *it;

// Largest value < x (strict floor):
auto it = lower_bound(all, x);
if (it != v.begin()) cout << *prev(it);

// Count elements < x:
lower_bound(all, x) - v.begin()

// Count elements <= x:
upper_bound(all, x) - v.begin()

// Count elements in range [a, b]:
upper_bound(all, b) - lower_bound(all, a)

3.3.9 Custom Predicate Binary Search

For non-standard sorted structures or custom criteria:

// Binary search with custom predicate
// Find first index i where pred(i) is true, in range [lo, hi]
// Assumption: pred is monotone: false...false, true...true

int lo = 0, hi = n - 1, answer = -1;
while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if (/* some condition on mid */) {
        answer = mid;
        hi = mid - 1;  // look for smaller index
    } else {
        lo = mid + 1;
    }
}

// Example: first index where arr[i] >= arr[i-1] + 10 (gap >= 10)
int lo = 1, hi = n - 1, firstLargeGap = -1;
while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if (arr[mid] - arr[mid-1] >= 10) {
        firstLargeGap = mid;
        hi = mid - 1;
    } else {
        lo = mid + 1;
    }
}

// Floating point binary search (epsilon-based)
double lo_f = 0.0, hi_f = 1e9;
for (int iter = 0; iter < 100; iter++) {  // 100 iterations → error < 1e-30
    double mid = (lo_f + hi_f) / 2;
    if (check(mid)) hi_f = mid;
    else lo_f = mid;
}
// Answer: lo_f (or hi_f, they converge to same value)

🏆 USACO Pro Tip: "Binary search on answer" is one of the most common Silver techniques. When you see "maximize/minimize X subject to [constraint]," ask yourself: Is the feasibility function monotone? If yes, binary search.

3.3.10 Ternary Search — Finding the Peak of a Unimodal Function

Binary search requires a monotone predicate (false→true boundary). For unimodal functions (increases then decreases), use ternary search to find the maximum.

💡 When to use: A function f is unimodal on [lo, hi] if it first strictly increases then strictly decreases (or is always one direction). Ternary search finds the maximum point in O(log((hi-lo)/eps)) evaluations.

USACO appearances: Problems where the answer depends on a continuous parameter (e.g., "find the optimal point on a line to minimize the sum of distances to a set of points") sometimes require ternary search.

// Ternary search: find maximum of unimodal function f on [lo, hi]
// Prerequisite: f increases then decreases (unimodal)
// Time: O(log((hi-lo)/eps)) for continuous, or O(log N) for integers

// f must be declared/defined before calling this
double ternarySearch(double lo, double hi) {
    for (int iter = 0; iter < 200; iter++) {
        double m1 = lo + (hi - lo) / 3;
        double m2 = hi - (hi - lo) / 3;
        if (f(m1) < f(m2)) lo = m1;  // maximum is in [m1, hi]
        else hi = m2;                 // maximum is in [lo, m2]
    }
    return (lo + hi) / 2;  // Maximum point (lo ≈ hi after convergence)
}

// Integer ternary search (when f is defined on integers):
int ternarySearchInt(int lo, int hi) {
    // 使用 > 2 而非 >= 2：保留至少 3 个候选值再暴力枚举。
    // 当范围缩至 2 个元素时，m1 == m2（因为 (hi-lo)/3 == 0），
    // 会导致死循环。用 > 2 可确保安全退出并正确处理边界。
    while (hi - lo > 2) {
        int m1 = lo + (hi - lo) / 3;
        int m2 = hi - (hi - lo) / 3;
        if (f(m1) < f(m2)) lo = m1 + 1;
        else hi = m2 - 1;
    }
    // Check remaining candidates [lo, hi] (at most 3 elements)
    int best = lo;
    for (int x = lo + 1; x <= hi; x++)
        if (f(x) > f(best)) best = x;
    return best;
}

Contrast with binary search:

⚠️ Note: Ternary search on integers requires care — use while (hi - lo > 2) to avoid infinite loops when the range shrinks to 2 or 3 elements, then brute-force the remaining candidates.

Chapter 3.4: Two Pointers & Sliding Window

📝 Before You Continue: You should be comfortable with arrays, vectors, and std::sort (Chapters 2.3–3.3). This technique requires a sorted array for the classic two-pointer approach.

Two pointers and sliding window are among the most elegant tricks in competitive programming. They transform naive O(N²) solutions into O(N) by exploiting monotonicity: as one pointer moves forward, the other never needs to go backward.

3.4.1 The Two Pointer Technique

The idea: maintain two indices, left and right, into a sorted array. Move them toward each other (or in the same direction) based on the current sum/window.

When to use:

• Finding a pair/triplet with a given sum in a sorted array
• Checking if a sorted array contains two elements with a specific relationship
• Problems where "if we can do X with window size k, we can do X with window size k-1"

The diagram shows how two pointers converge toward the center, each step eliminating an entire row/column of pairs from consideration.

Problem: Find All Pairs with Sum = Target

Naïve O(N²) approach:

// O(N²): check every pair
for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        if (arr[i] + arr[j] == target) {
            cout << arr[i] << " + " << arr[j] << "\n";
        }
    }
}

Two Pointer O(N) approach (requires sorted array):

// Solution: Two Pointer — O(N log N) for sort + O(N) for search
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, target;
    cin >> n >> target;
    vector<int> arr(n);
    for (int &x : arr) cin >> x;

    sort(arr.begin(), arr.end());  // MUST sort first

    int left = 0, right = n - 1;
    while (left < right) {
        int sum = arr[left] + arr[right];
        if (sum == target) {
            cout << arr[left] << " + " << arr[right] << " = " << target << "\n";
            left++;
            right--;  // advance both pointers
        } else if (sum < target) {
            left++;   // sum too small: move left pointer right (increase sum)
        } else {
            right--;  // sum too large: move right pointer left (decrease sum)
        }
    }

    return 0;
}

Why Does This Work?

Key insight: After sorting, if arr[left] + arr[right] < target, then no element smaller than arr[right] can pair with arr[left] to reach target. So we safely advance left.

Similarly, if the sum is too large, no element larger than arr[left] can pair with arr[right] to reach target. So we safely decrease right.

Each step eliminates at least one element from consideration → O(N) total steps.

Complete Trace

Array = [1, 2, 3, 4, 5, 6, 7, 8], target = 9:

State: left=0(1), right=7(8)
  sum = 1+8 = 9 ✓ → print (1,8), left++, right--

State: left=1(2), right=6(7)
  sum = 2+7 = 9 ✓ → print (2,7), left++, right--

State: left=2(3), right=5(6)
  sum = 3+6 = 9 ✓ → print (3,6), left++, right--

State: left=3(4), right=4(5)
  sum = 4+5 = 9 ✓ → print (4,5), left++, right--

State: left=4, right=3 → left >= right, STOP

All pairs: (1,8), (2,7), (3,6), (4,5)

3-Sum Extension

Finding a triplet that sums to target: fix one element, use two pointers for the remaining pair.

// O(N²) — much better than O(N³) brute force
sort(arr.begin(), arr.end());
for (int i = 0; i < n - 2; i++) {
    int left = i + 1, right = n - 1;
    while (left < right) {
        int sum = arr[i] + arr[left] + arr[right];
        if (sum == target) {
            cout << arr[i] << " " << arr[left] << " " << arr[right] << "\n";
            left++; right--;
        } else if (sum < target) left++;
        else right--;
    }
}

3.4.2 Sliding Window — Fixed Size

A sliding window of fixed size K moves across an array, maintaining a running aggregate (sum, max, count of distinct, etc.).

Problem: Find the maximum sum of any contiguous subarray of size K.

Array: [2, 1, 5, 1, 3, 2], K=3
Windows: [2,1,5]=8, [1,5,1]=7, [5,1,3]=9, [1,3,2]=6
Answer: 9

Naïve O(NK): Compute sum from scratch for each window.

Sliding window O(N): Add the new element entering the window, subtract the element leaving.

// Solution: Sliding Window Fixed Size — O(N)
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k;
    cin >> n >> k;
    vector<int> arr(n);
    for (int &x : arr) cin >> x;

    // Compute sum of first window
    long long windowSum = 0;
    for (int i = 0; i < k; i++) windowSum += arr[i];

    long long maxSum = windowSum;

    // Slide the window: add arr[i], remove arr[i-k]
    for (int i = k; i < n; i++) {
        windowSum += arr[i];        // new element enters window
        windowSum -= arr[i - k];   // old element leaves window
        maxSum = max(maxSum, windowSum);
    }

    cout << maxSum << "\n";
    return 0;
}

Trace for [2, 1, 5, 1, 3, 2], K=3:

Initial window [2,1,5]: sum=8, max=8
i=3: add 1, remove 2 → sum=7, max=8
i=4: add 3, remove 1 → sum=9, max=9
i=5: add 2, remove 5 → sum=6, max=9
Answer: 9 ✓

3.4.3 Sliding Window — Variable Size

The most powerful variant: the window expands when we need more, and shrinks when a constraint is violated.

Problem: Find the smallest contiguous subarray with sum ≥ target.

// Solution: Variable Window — O(N)
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, target;
    cin >> n >> target;
    vector<int> arr(n);
    for (int &x : arr) cin >> x;

    int left = 0;
    long long windowSum = 0;
    int minLen = INT_MAX;

    for (int right = 0; right < n; right++) {
        windowSum += arr[right];   // expand: add right element

        // Shrink window from left while constraint satisfied
        while (windowSum >= target) {
            minLen = min(minLen, right - left + 1);
            windowSum -= arr[left];
            left++;                // shrink: remove left element
        }
    }

    if (minLen == INT_MAX) cout << 0 << "\n";  // no such subarray
    else cout << minLen << "\n";

    return 0;
}

Why O(N)? Each element is added once (when right passes it) and removed at most once (when left passes it). Total operations: O(2N) = O(N).

Problem: Longest Subarray with At Most K Distinct Values

// Variable window: longest subarray with at most K distinct values
int left = 0, maxLen = 0;
map<int, int> freq;  // frequency of each value in window

for (int right = 0; right < n; right++) {
    freq[arr[right]]++;

    // Shrink while we have > k distinct values
    while ((int)freq.size() > k) {
        freq[arr[left]]--;
        if (freq[arr[left]] == 0) freq.erase(arr[left]);
        left++;
    }

    maxLen = max(maxLen, right - left + 1);
}
cout << maxLen << "\n";

3.4.4 USACO Example: Haybale Stacking

Problem (USACO 2012 November Bronze): N haybales in a line. M operations, each adds 1 to all bales in range [a, b]. How many bales have an odd number of additions at the end?

This is actually best solved with a difference array (Chapter 3.2), but a simpler version:

Problem: Given array of integers, find the longest subarray where all elements are ≥ K.

// Two pointer: longest contiguous subarray where all elements >= K
int left = 0, maxLen = 0;
for (int right = 0; right < n; right++) {
    if (arr[right] < K) {
        left = right + 1;  // reset window: current element violates constraint
    } else {
        maxLen = max(maxLen, right - left + 1);
    }
}

⚠️ Common Mistakes

1. Not sorting before two-pointer: The two-pointer technique for pair sum only works on sorted arrays. Without sorting, you'll miss pairs or get wrong answers.
2. Moving both pointers when a pair is found: When you find a matching pair, you must move BOTH left++ AND right--. Moving only one misses some pairs (unless duplicates aren't relevant).
3. Off-by-one in window size: The window [left, right] has size right - left + 1, not right - left.
4. Forgetting to handle empty answer: For the "minimum subarray" problem, initialize minLen = INT_MAX and check if it changed before outputting.

Chapter Summary

📌 Key Takeaways

❓ FAQ

Q1: Does two-pointer always require sorting?

A: Not necessarily. "Opposite-direction two pointers" (like pair sum) require sorting; "same-direction two pointers" (like sliding window) do not. The key is monotonicity — pointers only move in one direction.

Q2: Both sliding window and prefix sum can compute range sums — which to use?

A: For fixed-size window sum/max, sliding window is more intuitive. For arbitrary range queries, prefix sum is more general. Sliding window can only handle "continuously moving windows"; prefix sum can answer any [L,R] query.

Q3: Can sliding window handle both "longest subarray satisfying condition" and "shortest subarray satisfying condition"?

A: Both, but with slightly different logic. "Longest": expand right until condition fails, then shrink left until condition holds again. "Shortest": expand right until condition holds, then shrink left until it no longer holds, recording the minimum length throughout.

Q4: How does two-pointer handle duplicate elements?

A: Depends on the problem. If you want "all distinct pair values", after finding a pair do left++; right-- and skip duplicate values. If you want "count of all pairs", you need to carefully count duplicates (may require extra counting logic).

🔗 Connections to Later Chapters

• Chapter 3.2 (Prefix Sums): prefix sums and sliding window are complementary — prefix sums suit offline queries, sliding window suits online processing
• Chapter 3.3 (Sorting): sorting is a prerequisite for two pointers — opposite-direction two pointers require a sorted array
• Chapter 3.5 (Monotonic): monotonic deque can enhance sliding window — maintaining window min/max in O(N)
• Chapters 6.1–6.3 (DP): some problems (like LIS variants) can be optimized with two pointers

Practice Problems

Problem 3.4.1 — Pair Sum Count 🟢 Easy Given N integers and a target T, count the number of pairs (i < j) with arr[i] + arr[j] = T.

Problem 3.4.2 — Maximum Average Subarray 🟡 Medium Find the contiguous subarray of length exactly K with the maximum average. Print the average as a fraction or decimal.

Problem 3.4.3 — Minimum Window Covering 🔴 Hard Given string S and string T, find the shortest substring of S that contains all characters of T.

🏆 Challenge: USACO 2017 February Bronze — Why Did the Cow Cross the Road Given a grid with cows and their destinations, find which cow can reach its destination fastest. Use two-pointer / greedy on sorted intervals.

Chapter 3.5: Monotonic Stack & Monotonic Queue

📝 Before You Continue: Make sure you're comfortable with two pointers / sliding window (Chapter 3.4) and basic stack/queue operations (Chapter 3.1). This chapter builds directly on those techniques.

Monotonic stacks and queues are elegant tools that solve "nearest greater/smaller element" and "sliding window extremum" problems in O(N) time — problems that would naively require O(N²).

3.5.1 Monotonic Stack: Next Greater Element

Problem: Given an array A of N integers, for each element A[i], find the next greater element (NGE): the index of the first element to the right of i that is greater than A[i]. If none exists, output -1.

Naive approach: O(N²) — for each i, scan right until finding a greater element.

Monotonic stack approach: O(N) — maintain a stack that is always decreasing from bottom to top. When we push a new element, pop all smaller elements first (they just found their NGE!).

💡 Key Insight: The stack contains indices of elements that haven't found their NGE yet. When A[i] arrives, every element in the stack that is smaller than A[i] has found its NGE (it's i!). We pop them and record the answer.

单调栈状态变化示意（A=[2,1,5,6,2,3]）：

flowchart LR
    subgraph i0["i=0, A[0]=2"]
        direction TB
        ST0["Stack: [0]↓\n底→顶: [2]"]
    end
    subgraph i1["i=1, A[1]=1"]
        direction TB
        ST1["1<2, 直接入栈\nStack: [0,1]↓\n底→顶: [2,1]"]
    end
    subgraph i2["i=2, A[2]=5"]
        direction TB
        ST2["5>1: pop 1, NGE[1]=2\n5>2: pop 0, NGE[0]=2\nStack: [2]↓\n底→顶: [5]"]
    end
    subgraph i3["i=3, A[3]=6"]
        direction TB
        ST3["6>5: pop 2, NGE[2]=3\nStack: [3]↓\n底→顶: [6]"]
    end
    subgraph i5["i=5, A[5]=3"]
        direction TB
        ST5["3>2: pop 4, NGE[4]=5\n3<6, 入栈\nStack: [3,5]↓\n幕尾无 NGE"]
    end
    i0 --> i1 --> i2 --> i3 --> i5
    style ST2 fill:#dcfce7,stroke:#16a34a
    style ST3 fill:#dcfce7,stroke:#16a34a
    style ST5 fill:#dcfce7,stroke:#16a34a

💡 摘要： 栈始终保持单调递减（底大顶小）。每个元素至多入栈一次、出栈一次，总操作次数 O(2N) = O(N)。

Array A: [2, 1, 5, 6, 2, 3]
         idx: 0  1  2  3  4  5

Processing i=0 (A[0]=2): stack empty → push 0
Stack: [0]          // stack holds indices of unresolved elements

Processing i=1 (A[1]=1): A[1]=1 < A[0]=2 → just push
Stack: [0, 1]

Processing i=2 (A[2]=5): 
  A[2]=5 > A[1]=1 → pop 1, NGE[1] = 2  (A[2]=5 is next greater for A[1])
  A[2]=5 > A[0]=2 → pop 0, NGE[0] = 2  (A[2]=5 is next greater for A[0])
  Stack empty → push 2
Stack: [2]

Processing i=3 (A[3]=6): 
  A[3]=6 > A[2]=5 → pop 2, NGE[2] = 3
  Push 3
Stack: [3]

Processing i=4 (A[4]=2): A[4]=2 < A[3]=6 → just push
Stack: [3, 4]

Processing i=5 (A[5]=3): 
  A[5]=3 > A[4]=2 → pop 4, NGE[4] = 5
  A[5]=3 < A[3]=6 → stop, push 5
Stack: [3, 5]

End: remaining stack [3, 5] → NGE[3] = NGE[5] = -1 (no greater element to the right)

Result: NGE = [2, 2, 3, -1, 5, -1]
Verify: 
  A[0]=2, next greater is A[2]=5 ✓
  A[1]=1, next greater is A[2]=5 ✓
  A[2]=5, next greater is A[3]=6 ✓
  A[3]=6, no greater → -1 ✓

Complete Implementation

// Solution: Next Greater Element using Monotonic Stack — O(N)
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<int> A(n);
    for (int& x : A) cin >> x;

    vector<int> nge(n, -1);   // nge[i] = index of next greater element, -1 if none
    stack<int> st;             // monotonic decreasing stack (stores indices)

    for (int i = 0; i < n; i++) {
        // While the top of stack has a smaller value than A[i]
        // → the current element A[i] is the NGE of all those elements
        while (!st.empty() && A[st.top()] < A[i]) {
            nge[st.top()] = i;  // ← KEY: record NGE for stack top
            st.pop();
        }
        st.push(i);  // push current index (not yet resolved)
    }
    // Remaining elements in stack have no NGE → already initialized to -1

    for (int i = 0; i < n; i++) {
        cout << nge[i];
        if (i < n - 1) cout << " ";
    }
    cout << "\n";

    return 0;
}

Complexity Analysis:

• Each element is pushed exactly once and popped at most once
• Total operations: O(2N) = O(N)
• Space: O(N) for the stack

⚠️ Common Mistake: Storing values instead of indices in the stack. Always store indices — you need to know where in the array to record the answer.

3.5.2 Variations: Previous Smaller, Previous Greater

By changing the comparison direction and the traversal direction, you get four related problems:

Template for Previous Smaller Element:

// Previous Smaller Element: for each i, find the nearest j < i where A[j] < A[i]
vector<int> pse(n, -1);  // pse[i] = index of previous smaller, -1 if none
stack<int> st;

for (int i = 0; i < n; i++) {
    while (!st.empty() && A[st.top()] >= A[i]) {
        st.pop();  // pop elements that are >= A[i] (not the "previous smaller")
    }
    pse[i] = st.empty() ? -1 : st.top();  // stack top is the previous smaller
    st.push(i);
}

3.5.3 USACO Application: Largest Rectangle in Histogram

Problem: Given an array of heights H[0..N-1], find the area of the largest rectangle that fits under the histogram.

Key insight: For each bar i, the largest rectangle with height H[i] extends left and right until it hits a shorter bar. Use monotonic stack to find, for each i:

• left[i] = previous smaller element index
• right[i] = next smaller element index

直方图最大矩形边界计算示意（H=[2,1,5,6,2,3]）：

flowchart LR
    subgraph bars["每个柱子的左右边界"]
        direction TB
        B0["i=0, H=2\nleft=-1, right=1\nwidth=1, area=2"]
        B1["i=1, H=1\nleft=-1, right=6\nwidth=6, area=6"]
        B2["i=2, H=5\nleft=1, right=4\nwidth=2, area=10 ⭐"]
        B3["i=3, H=6\nleft=2, right=4\nwidth=1, area=6"]
        B4["i=4, H=2\nleft=1, right=6\nwidth=4, area=8"]
        B5["i=5, H=3\nleft=4, right=6\nwidth=1, area=3"]
    end
    note["最大面积 = 10\n（i=2, 高度=5, 宽度=2）"]
    style B2 fill:#dcfce7,stroke:#16a34a
    style note fill:#f0fdf4,stroke:#16a34a

💡 公式： width = right[i] - left[i] - 1，area = H[i] × width。左边界用"左侧第一个更小元素的下标"，右边界用"右侧第一个更小元素的下标"。

// Solution: Largest Rectangle in Histogram — O(N)
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<int> H(n);
    for (int& h : H) cin >> h;

    // Find previous smaller for each position
    vector<int> left(n), right(n);
    stack<int> st;

    // Previous smaller (left boundary)
    for (int i = 0; i < n; i++) {
        while (!st.empty() && H[st.top()] >= H[i]) st.pop();
        left[i] = st.empty() ? -1 : st.top();  // index before rectangle starts
        st.push(i);
    }

    while (!st.empty()) st.pop();

    // Next smaller (right boundary)
    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty() && H[st.top()] >= H[i]) st.pop();
        right[i] = st.empty() ? n : st.top();  // index after rectangle ends
        st.push(i);
    }

    // Compute maximum area
    long long maxArea = 0;
    for (int i = 0; i < n; i++) {
        long long width = right[i] - left[i] - 1;  // width of rectangle
        long long area = (long long)H[i] * width;
        maxArea = max(maxArea, area);
    }

    cout << maxArea << "\n";
    return 0;
}

Trace for H = [2, 1, 5, 6, 2, 3]:

left  = [-1, -1, 1, 2, 1, 4]   (index of previous smaller, -1 = none)
right = [1, 6, 4, 4, 6, 6]     (index of next smaller, n=6 = none)

Widths:  1-(-1)-1=1, 6-(-1)-1=6, 4-1-1=2, 4-2-1=1, 6-1-1=4, 6-4-1=1
Areas:   2×1=2, 1×6=6, 5×2=10, 6×1=6, 2×4=8, 3×1=3

Maximum area = 10
  i=2: H[2]=5, left[2]=1, right[2]=4, width=4-1-1=2, area=5×2=10 ✓
  (bars at indices 2 and 3 both have height ≥ 5, so the rectangle of height 5 spans width 2)

📌 Note for Students: Always trace through your algorithm on the sample input before submitting. Small off-by-one errors in index boundary calculations are the #1 source of bugs in monotonic stack problems.

3.5.4 Monotonic Deque: Sliding Window Maximum

Problem: Given array A of N integers and window size K, find the maximum value in each window of size K as it slides from left to right. Output N-K+1 values.

Naive approach: O(NK) — scan each window for its maximum.

Monotonic deque approach: O(N) — maintain a decreasing deque (front = maximum of current window).

💡 Key Insight: We want the maximum in a sliding window. We maintain a deque of indices such that:

1. The deque is decreasing in value (front is always the maximum)
2. The deque only contains indices within the current window

When a new element arrives:

• Remove all smaller elements from the back (they can never be the maximum while this new element is in the window)
• Remove the front if it's outside the current window

Step-by-Step Trace

Array A: [1, 3, -1, -3, 5, 3, 6, 7], K = 3

Window [1,3,-1]: max = 3
Window [3,-1,-3]: max = 3
Window [-1,-3,5]: max = 5
Window [-3,5,3]: max = 5
Window [5,3,6]: max = 6
Window [3,6,7]: max = 7

i=0, A[0]=1: deque=[0]
i=1, A[1]=3: 3>1 → pop 0; deque=[1]
i=2, A[2]=-1: -1<3 → push; deque=[1,2]; window [0..2]: max=A[1]=3 ✓
i=3, A[3]=-3: -3<-1 → push; deque=[1,2,3]; window [1..3]: front=1 still in window, max=A[1]=3 ✓
i=4, A[4]=5: 5>-3→pop 3; 5>-1→pop 2; 5>3→pop 1; deque=[4]; window [2..4]: max=A[4]=5 ✓
i=5, A[5]=3: 3<5→push; deque=[4,5]; window [3..5]: front=4 in window, max=A[4]=5 ✓
i=6, A[6]=6: 6>3→pop 5; 6>5→pop 4; deque=[6]; window [4..6]: max=A[6]=6 ✓
i=7, A[7]=7: 7>6→pop 6; deque=[7]; window [5..7]: max=A[7]=7 ✓

Complete Implementation

// Solution: Sliding Window Maximum using Monotonic Deque — O(N)
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k;
    cin >> n >> k;
    vector<int> A(n);
    for (int& x : A) cin >> x;

    deque<int> dq;   // monotonic decreasing deque, stores indices
    vector<int> result;

    for (int i = 0; i < n; i++) {
        // 1. Remove elements outside the current window
        while (!dq.empty() && dq.front() <= i - k) {
            dq.pop_front();   // ← KEY: expired window front
        }

        // 2. Maintain decreasing property
        //    Remove from back all elements smaller than A[i]
        //    (they'll never be the max while A[i] is in the window)
        while (!dq.empty() && A[dq.back()] <= A[i]) {
            dq.pop_back();    // ← KEY: pop smaller elements from back
        }

        dq.push_back(i);   // add current element

        // 3. Record maximum once first full window is formed
        if (i >= k - 1) {
            result.push_back(A[dq.front()]);  // front = maximum of current window
        }
    }

    for (int i = 0; i < (int)result.size(); i++) {
        cout << result[i];
        if (i + 1 < (int)result.size()) cout << "\n";
    }
    cout << "\n";

    return 0;
}

Complexity:

• Each element is pushed/popped from the deque at most once → O(N) total
• Space: O(K) for the deque

⚠️ Common Mistake #1: Forgetting to check dq.front() <= i - k for window expiration. The deque must only contain indices in [i-k+1, i].

⚠️ Common Mistake #2: Using < instead of <= when popping from the back. With <, equal elements are preserved, but duplicates can cause issues. Use <= to maintain strict decreasing deque.

3.5.5 USACO Problem: Haybale Stacking (Monotonic Stack)

🔗 Inspiration: This problem type appears in USACO Bronze/Silver ("Haybale Stacking" style).

Problem: There are N positions on a number line. You have K operations: each operation sets all positions in [L, R] to 1. After all operations, output 1 for each position that was set, 0 otherwise.

Solution: Difference array (Chapter 3.2). But let's see a harder variant:

Harder Variant: Given an array H of N "heights," find for each position i the leftmost j such that H[j] < H[i] for all k in [j+1, i-1]. (Find the span of each bar in a histogram.)

This is exactly the "stock span problem" and solves using a monotonic stack — identical to the previous smaller element pattern.

// Stock Span Problem: for each day i, find how many consecutive days
// before i had price <= price[i]
// (the "span" of day i)
vector<int> stockSpan(vector<int>& prices) {
    int n = prices.size();
    vector<int> span(n, 1);
    stack<int> st;  // monotonic decreasing stack of indices

    for (int i = 0; i < n; i++) {
        while (!st.empty() && prices[st.top()] <= prices[i]) {
            st.pop();
        }
        span[i] = st.empty() ? (i + 1) : (i - st.top());
        st.push(i);
    }
    return span;
}
// span[i] = number of consecutive days up to and including i with price <= prices[i]

3.5.6 USACO-Style Problem: Barn Painting Temperatures

Problem: N readings, find the maximum value in each window of size K.

(This is the sliding window maximum — solution already shown in 3.5.4.)

A trickier USACO variant: Given N cows in a line, each with temperature T[i]. A "fever cluster" is a maximal contiguous subarray where all temperatures are above threshold X. Find the maximum cluster size for each of Q threshold queries.

Offline approach: Sort queries by X, process with monotonic deque.

⚠️ Common Mistakes in Chapter 3.5

1. Storing values instead of indices — Always store indices. You need them to check window bounds and to record answers.

2. Wrong comparison in deque (< vs <=) — For sliding window MAXIMUM, pop when A[dq.back()] <= A[i] (strict non-increase). For MINIMUM, pop when A[dq.back()] >= A[i].

3. Forgetting window expiration — In sliding window deque, always check dq.front() < i - k + 1 (or <= i - k) before recording the maximum.

4. Stack bottom-top direction confusion — The "monotonic" property means: bottom-to-top, the stack is increasing (for NGE) or decreasing (for NSE). Draw it out if confused.

5. Processing order for NGE vs PSE:

   • Next Greater Element: left-to-right traversal
   • Previous Greater Element: right-to-left traversal (OR: left-to-right, record stack.top() before pushing)

Chapter Summary

📌 Key Summary

🧩 Template Quick Reference

// Monotone decreasing stack (for NGE / Next Greater Element)
stack<int> st;
for (int i = 0; i < n; i++) {
    while (!st.empty() && A[st.top()] < A[i]) {
        answer[st.top()] = i;  // i is the NGE of st.top()
        st.pop();
    }
    st.push(i);
}

// Monotone decreasing deque (sliding window maximum)
deque<int> dq;
for (int i = 0; i < n; i++) {
    while (!dq.empty() && dq.front() <= i - k) dq.pop_front();  // remove expired
    while (!dq.empty() && A[dq.back()] <= A[i]) dq.pop_back();  // maintain monotone
    dq.push_back(i);
    if (i >= k - 1) ans.push_back(A[dq.front()]);
}

❓ FAQ

Q1: Should the monotone stack store values or indices?

A: Always store indices. Even if you only need values, storing indices is more flexible — you can get the value via A[idx], but not vice versa. Especially when computing widths (e.g., histogram problems), indices are required.

Q2: How do I decide between monotone stack and two pointers?

A: Look at the problem structure — if you need "for each element, find the first greater/smaller element to its left/right", use monotone stack. If you need "maintain the maximum of a sliding window", use monotone deque. If "two pointers moving toward each other from both ends", use two pointers.

Q3: Why is the time complexity of monotone stack O(N) and not O(N²)?

A: Amortized analysis. Each element is pushed at most once and popped at most once, totaling 2N operations, so O(N). Although a single while loop may pop multiple times, the total number of pops across all while loops never exceeds N.

Practice Problems

Problem 3.5.1 — Next Greater Element 🟢 Easy For each element in an array, find the first element to its right that is greater. Print -1 if none exists.

Problem 3.5.2 — Daily Temperatures 🟢 Easy For each day, find how many days you have to wait until a warmer temperature. (LeetCode 739 style)

Problem 3.5.3 — Sliding Window Maximum 🟡 Medium Find the maximum in each sliding window of size K.

Problem 3.5.4 — Largest Rectangle in Histogram 🟡 Medium Find the largest rectangle that fits in a histogram.

Problem 3.5.5 — Trapping Rain Water 🔴 Hard Given an elevation map, compute how much water can be trapped after raining. (Classic problem)

🏆 Challenge: USACO 2016 February Silver: Fencing the Cows Given a polygon, find if a point is inside. Use ray casting — involves careful implementation with edge cases.

Chapter 3.6: Stacks, Queues & Deques

These three data structures control the order in which elements are processed. Each has a unique "personality" that makes it perfect for specific types of problems.

• Stack: Last In, First Out (like a stack of plates)
• Queue: First In, First Out (like a line at a store)
• Deque: Double-ended — insert/remove from both ends

3.6.1 Stack Deep Dive

We introduced stack in Chapter 3.1. Let's use it to solve real problems.

Visual: Stack Operations

The diagram above illustrates the LIFO (Last In, First Out) property with step-by-step push and pop operations. Note how pop() always removes the most-recently-pushed element — this is what makes stacks ideal for matching brackets, DFS, and undo operations.

The Balanced Brackets Problem

Problem: Given a string of brackets ()[]{}, determine if they're properly nested.

#include <bits/stdc++.h>
using namespace std;

bool isBalanced(const string &s) {
    stack<char> st;

    for (char ch : s) {
        if (ch == '(' || ch == '[' || ch == '{') {
            st.push(ch);   // opening bracket: push onto stack
        } else {
            // closing bracket: must match the most recent opening
            if (st.empty()) return false;   // no matching opening bracket

            char top = st.top();
            st.pop();

            // Check if it matches
            if (ch == ')' && top != '(') return false;
            if (ch == ']' && top != '[') return false;
            if (ch == '}' && top != '{') return false;
        }
    }

    return st.empty();  // all brackets matched if stack is empty
}

int main() {
    cout << isBalanced("()[]{}") << "\n";    // 1 (true)
    cout << isBalanced("([]){}") << "\n";    // 1 (true)
    cout << isBalanced("([)]")   << "\n";    // 0 (false)
    cout << isBalanced("(()")    << "\n";    // 0 (false — unmatched '(')
    return 0;
}

The "Next Greater Element" Problem

Problem: For each element in an array, find the next element to its right that is strictly greater. If none exists, output -1.

This is a classic monotonic stack problem.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<int> A(n);
    for (int &x : A) cin >> x;

    vector<int> answer(n, -1);  // default: -1 (no greater element)
    stack<int> st;              // stores indices of elements awaiting their answer

    for (int i = 0; i < n; i++) {
        // While stack is non-empty and current element > element at stack's top index
        while (!st.empty() && A[i] > A[st.top()]) {
            answer[st.top()] = A[i];  // A[i] is the next greater element for st.top()
            st.pop();
        }
        st.push(i);  // push current index (waiting for a larger element later)
    }

    for (int x : answer) cout << x << " ";
    cout << "\n";

    return 0;
}

Trace for [3, 1, 4, 1, 5, 9, 2, 6]:

• i=0: push 0. Stack: [0]
• i=1: A[1]=1 ≤ A[0]=3, push 1. Stack: [0,1]
• i=2: A[2]=4 > A[1]=1 → answer[1]=4, pop. A[2]=4 > A[0]=3 → answer[0]=4, pop. Push 2.
• i=3: push 3. Stack: [2,3]
• i=4: A[4]=5 > A[3]=1 → answer[3]=5. A[4]=5 > A[2]=4 → answer[2]=5. Push 4.
• i=5: A[5]=9 > A[4]=5 → answer[4]=9. Push 5. Stack: [5]
• i=6: push 6. Stack: [5,6]
• i=7: A[7]=6 > A[6]=2 → answer[6]=6. Push 7.
• Remaining on stack (5, 7): answer stays -1.

Output: 4 4 5 5 9 -1 6 -1

Key insight: A monotonic stack maintains elements in a strictly increasing or decreasing order. When a new element breaks that order, it "solves" all the elements it's greater than. This is O(n) because each element is pushed and popped at most once.

3.6.2 Queue and BFS Preparation

The queue's FIFO property makes it perfect for Breadth-First Search (BFS), which we cover in Chapter 5.2. Here we focus on the queue itself and related patterns.

Visual: Queue Operations

The queue processes elements in order of arrival: the front element is always dequeued next, while new elements join at the back. This FIFO property ensures BFS visits nodes level-by-level, guaranteeing shortest-path distances.

Simulation with a Queue

Problem: A theme park ride has N groups of people. Each group has size[i]. The ride holds at most M people per run. Simulate how many runs are needed to take everyone.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    queue<int> groups;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        groups.push(x);
    }

    int runs = 0;
    while (!groups.empty()) {
        int capacity = m;   // remaining capacity for this run
        runs++;

        while (!groups.empty() && groups.front() <= capacity) {
            capacity -= groups.front();  // fit this group
            groups.pop();
        }
    }

    cout << runs << "\n";
    return 0;
}

3.6.3 Deque — Double-Ended Queue

A deque (pronounced "deck") supports O(1) insertion and removal at both the front and back.

#include <bits/stdc++.h>
using namespace std;

int main() {
    deque<int> dq;

    dq.push_back(1);    // [1]
    dq.push_back(2);    // [1, 2]
    dq.push_front(0);   // [0, 1, 2]
    dq.push_front(-1);  // [-1, 0, 1, 2]

    cout << dq.front() << "\n";  // -1
    cout << dq.back() << "\n";   // 2

    dq.pop_front();  // [-1 removed] → [0, 1, 2]
    dq.pop_back();   // [2 removed]  → [0, 1]

    cout << dq.front() << "\n";  // 0
    cout << dq.size() << "\n";   // 2

    // Random access (like a vector)
    cout << dq[0] << "\n";  // 0
    cout << dq[1] << "\n";  // 1

    return 0;
}

3.6.4 Monotonic Deque — Sliding Window Maximum

Problem: Given an array A of N integers and a window of size K, find the maximum value in each window as it slides from left to right.

Naive approach: for each window, scan all K elements → O(N×K). Too slow for large K.

Monotonic deque approach: O(N).

The deque stores indices of elements in decreasing order of their values. The front is always the maximum.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k;
    cin >> n >> k;
    vector<int> A(n);
    for (int &x : A) cin >> x;

    deque<int> dq;  // stores indices; values A[dq[i]] are decreasing
    vector<int> maxInWindow;

    for (int i = 0; i < n; i++) {
        // Remove elements outside the window (front is too old)
        while (!dq.empty() && dq.front() <= i - k) {
            dq.pop_front();
        }

        // Remove elements from back that are smaller than A[i]
        // (they can never be the maximum for future windows)
        while (!dq.empty() && A[dq.back()] <= A[i]) {
            dq.pop_back();
        }

        dq.push_back(i);  // add current index

        // Window is full starting at i = k-1
        if (i >= k - 1) {
            maxInWindow.push_back(A[dq.front()]);  // front is always the max
        }
    }

    for (int x : maxInWindow) cout << x << " ";
    cout << "\n";

    return 0;
}

Sample Input:

8 3
1 3 -1 -3 5 3 6 7

Sample Output:

3 3 5 5 6 7

Windows: [1,3,-1]=3, [3,-1,-3]=3, [-1,-3,5]=5, [-3,5,3]=5, [5,3,6]=6, [3,6,7]=7.

3.6.5 Stack-Based: Largest Rectangle in Histogram

A classic competitive programming problem: given N bars of heights h[0..N-1], find the largest rectangle that fits within the histogram.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<int> h(n);
    for (int &x : h) cin >> x;

    stack<int> st;   // stores indices of bars in increasing height order
    long long maxArea = 0;

    for (int i = 0; i <= n; i++) {
        int currentH = (i == n) ? 0 : h[i];  // sentinel 0 at the end

        while (!st.empty() && h[st.top()] > currentH) {
            int height = h[st.top()];   // height of the rectangle
            st.pop();
            int width = st.empty() ? i : i - st.top() - 1;  // width
            maxArea = max(maxArea, (long long)height * width);
        }

        st.push(i);
    }

    cout << maxArea << "\n";
    return 0;
}

⚠️ Common Mistakes in Chapter 3.6

Chapter Summary

📌 Key Takeaways

❓ FAQ

Q1: Why is the monotonic stack O(N) and not O(N²)? It looks like there's a nested loop.

A: Key observation — each element is pushed at most once and popped at most once. Although the inner while loop may pop multiple elements at once, the total number of pops globally is ≤ N. So total operations ≤ 2N = O(N). This analysis method is called amortized analysis.

Q2: When to use stack vs deque?

A: If you only need LIFO (one-end access), use stack; if you need two-end operations (e.g., sliding window needs front removal + back addition), use deque. stack is actually backed by deque internally, but restricts the interface to only expose the top.

Q3: Must BFS use queue? Can I use vector?

A: Technically you can simulate with vector + index, but queue is clearer and less error-prone. In contests, use queue directly. The only exception is 0-1 BFS (shortest path with only 0 and 1 weights), which requires deque.

Q4: Why can the "largest rectangle" problem be solved with a stack?

A: The stack maintains an increasing sequence of bars. When a shorter bar is encountered, it means the top bar's "rightward extension" ends here. At that point, we can compute the rectangle area with the top bar's height. Each bar is pushed/popped once, total complexity O(N).

🔗 Connections to Later Chapters

• Chapter 5.2 (Graph BFS/DFS): queue is the core container for BFS, stack can be used for iterative DFS
• Chapter 3.4 (Two Pointers): the sliding window technique combines well with the monotonic deque from this chapter
• Chapters 6.1–6.3 (DP): certain optimization techniques (e.g., DP-optimized sliding window extremes) directly use the monotonic deque from this chapter
• The monotonic stack also appears as an alternative to Chapter 3.9 (Segment Trees) — many problems solvable by segment trees can also be solved in O(N) with a monotonic stack

Practice Problems

Problem 3.6.1 — Stock Span Read N daily stock prices. For each day, find the number of consecutive days up to that day where the price was ≤ today's price (including today). (Classic monotonic stack problem)

Problem 3.6.2 — Circular Queue Implement a circular queue of size K. Process operations: PUSH x (add x to back), POP (remove from front). Print "OVERFLOW" if push on full queue, "UNDERFLOW" if pop on empty.

Problem 3.6.3 — Sliding Window Minimum Same as the sliding window maximum example, but find the minimum.

Problem 3.6.4 — Expression Evaluation Read a simple expression with integers and +, - operators (no parentheses). Evaluate it using a stack.

Problem 3.6.5 — USACO 2020 January Bronze: Loan Repayment (Simplified) You have N stacks of hay. Each day, you can take one bale from any non-empty stack. Model this with a priority_queue: always take from the tallest stack. Simulate for D days and print the remaining bales.

Chapter 3.7: Hashing Techniques

📝 Before You Continue: You should know STL containers (Chapter 3.1) and string basics (Chapter 2.3). This chapter covers hashing principles and advanced competitive programming usage.

Hashing is one of the most important "tools" in competitive programming: it turns complex comparison problems into O(1) numeric comparisons. But hashing is also the easiest technique to get "hacked"—this chapter teaches both how to use it well and how to prevent being hacked.

3.7.1 unordered_map vs map: Internals & Performance

Internal Implementation Comparison

#include <bits/stdc++.h>
using namespace std;

int main() {
    // map: ordered, O(log N)
    map<int, int> m;
    m[3] = 30; m[1] = 10; m[2] = 20;
    for (auto [k, v] : m) cout << k << ":" << v << " ";
    // output: 1:10 2:20 3:30  ← ordered!

    // unordered_map: unordered, O(1) average
    unordered_map<int, int> um;
    um[3] = 30; um[1] = 10; um[2] = 20;
    // iteration order undefined, but lookup is very fast

    // performance difference: N=10^6 operations
    // map: ~300ms; unordered_map: ~80ms (roughly)
}

When to Choose Which?

• Use map: need ordered iteration, need lower_bound/upper_bound, extreme key range (high hash collision risk)
• Use unordered_map: pure lookup/insert, key is integer or string, large N (> 10^5)

3.7.2 Anti-Hack: Custom Hash

Problem: unordered_map's default integer hash is essentially hash(x) = x, allowing attackers to construct many hash collisions, degrading operations to O(N) and causing TLE.

On platforms like Codeforces, this is a common hack technique.

Solution: splitmix64 Hash

// Anti-hack custom hasher — uses splitmix64
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM =
            chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

// Usage:
unordered_map<int, int, custom_hash> safe_map;
unordered_set<int, custom_hash> safe_set;

⚠️ Contest tip: When using unordered_map on Codeforces, always add custom_hash. USACO test data won't deliberately construct hacks, but it's a good habit.

3.7.3 String Hashing (Polynomial Hash)

String hashing maps a string to an integer, turning string comparison into numeric comparison (O(1)).

Core Formula

For string s[0..n-1], define the hash value as:

hash(s) = s[0]·B^(n-1) + s[1]·B^(n-2) + ... + s[n-1]·B^0  (mod M)

where B is the base (typically 131 or 131117) and M is a large prime (typically 10⁹+7 or 10⁹+9).

Prefix Hash + Substring Hash O(1)

// String hashing: O(N) preprocessing, O(1) substring hash
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;

const ull BASE = 131;
// Use unsigned long long natural overflow (equivalent to mod 2^64)
// Or specify MOD manually:
// const ull MOD = 1e9 + 7;

struct StringHash {
    int n;
    vector<ull> h, pw;

    StringHash(const string& s) : n(s.size()), h(n + 1, 0), pw(n + 1, 1) {
        for (int i = 0; i < n; i++) {
            h[i + 1] = h[i] * BASE + (s[i] - 'a' + 1);  // 1-indexed prefix hash
            pw[i + 1] = pw[i] * BASE;                      // BASE^(i+1)
        }
    }

    // Get hash of substring s[l..r] (0-indexed)
    ull get(int l, int r) {
        return h[r + 1] - h[l] * pw[r - l + 1];  // ← KEY formula
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string s = "abcabc";
    StringHash sh(s);

    // Compare if two substrings are equal
    // s[0..2] = "abc", s[3..5] = "abc"
    cout << (sh.get(0, 2) == sh.get(3, 5) ? "Equal" : "Not Equal") << "\n";  // Equal

    // Compare s[0..1] = "ab" vs s[3..4] = "ab"
    cout << (sh.get(0, 1) == sh.get(3, 4) ? "Equal" : "Not Equal") << "\n";  // Equal
}

Hash Formula Derivation:

h[r+1] = s[0]*B^r + s[1]*B^(r-1) + ... + s[r]*B^0
h[l]   = s[0]*B^(l-1) + ... + s[l-1]*B^0

h[r+1] - h[l] * B^(r-l+1)
= (s[0]*B^r + ... + s[r]*B^0)
  - (s[0]*B^r + ... + s[l-1]*B^(r-l+1))
= s[l]*B^(r-l) + s[l+1]*B^(r-l-1) + ... + s[r]*B^0
= hash(s[l..r]) ✓

下图直观展示了前缀哈希数组的构建过程，以及如何用 get(l, r) 公式在 O(1) 内提取任意子串的哈希值：

3.7.4 Double Hashing (Avoiding Collisions)

Single hash (mod M) has collision probability ≈ 1/M. For N substring comparisons, expected collisions ≈ N²/(2M).

• If M = 10⁹+7, N = 10⁶: collision probability ≈ 10¹²/(2×10⁹) = 500 times! Not safe.
• Solution: double hashing, using two different (B, M) pairs simultaneously, collision probability drops to 1/(M₁×M₂) ≈ 10⁻¹⁸.

// Double hashing: two (BASE, MOD) pairs used simultaneously, extremely low collision probability
struct DoubleHash {
    static const ull B1 = 131, M1 = 1e9 + 7;
    static const ull B2 = 137, M2 = 1e9 + 9;

    int n;
    vector<ull> h1, h2, pw1, pw2;

    DoubleHash(const string& s) : n(s.size()),
        h1(n+1,0), h2(n+1,0), pw1(n+1,1), pw2(n+1,1) {
        for (int i = 0; i < n; i++) {
            ull c = s[i] - 'a' + 1;
            h1[i+1] = (h1[i] * B1 + c) % M1;
            h2[i+1] = (h2[i] * B2 + c) % M2;
            pw1[i+1] = pw1[i] * B1 % M1;
            pw2[i+1] = pw2[i] * B2 % M2;
        }
    }

    // Return pair<ull,ull> as the hash "fingerprint" of substring s[l..r]
    pair<ull,ull> get(int l, int r) {
        ull v1 = (h1[r+1] - h1[l] * pw1[r-l+1] % M1 + M1) % M1;
        ull v2 = (h2[r+1] - h2[l] * pw2[r-l+1] % M2 + M2) % M2;
        return {v1, v2};
    }
};

3.7.5 Application: String Matching (Rabin-Karp)

// Rabin-Karp string matching: find all occurrences of pattern P in text T
// Time: O(N+M) average, O(NM) worst case (but extremely fast in practice)
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;

vector<int> rabinKarp(const string& T, const string& P) {
    int n = T.size(), m = P.size();
    if (m > n) return {};

    const ull BASE = 131;
    ull patHash = 0, textHash = 0, pow_m = 1;

    // Compute BASE^m (natural overflow)
    for (int i = 0; i < m - 1; i++) pow_m *= BASE;

    // Initial hash
    for (int i = 0; i < m; i++) {
        patHash = patHash * BASE + P[i];
        textHash = textHash * BASE + T[i];
    }

    vector<int> result;
    for (int i = 0; i + m <= n; i++) {
        if (textHash == patHash) {
            // Verify when hashes match (avoid false positives from collision)
            if (T.substr(i, m) == P) result.push_back(i);
        }
        if (i + m < n) {
            // Rolling hash: remove leftmost char, add rightmost char
            textHash = textHash - T[i] * pow_m;   // remove leftmost
            textHash = textHash * BASE + T[i + m]; // add rightmost
        }
    }
    return result;
}

3.7.6 Application: Longest Common Substring

Problem: Given strings S and T, find the length of their longest common substring.

Approach: Binary search on the answer (length L of longest common substring), then use a hash set to check if any substring of length L appears in both strings.

// Longest common substring: O(N log N) — binary search + hashing
int longestCommonSubstring(const string& S, const string& T) {
    StringHash hs(S), ht(T);
    int ns = S.size(), nt = T.size();

    auto check = [&](int len) -> bool {
        unordered_set<ull> setS;
        for (int i = 0; i + len <= ns; i++)
            setS.insert(hs.get(i, i + len - 1));
        for (int j = 0; j + len <= nt; j++)
            if (setS.count(ht.get(j, j + len - 1)))
                return true;
        return false;
    };

    int lo = 0, hi = min(ns, nt);
    while (lo < hi) {
        int mid = (lo + hi + 1) / 2;
        if (check(mid)) lo = mid;
        else hi = mid - 1;
    }
    return lo;
}

⚠️ Common Mistakes

1. Bad modulus choice: Don't use numbers other than 10⁹+7; especially avoid non-prime moduli (high collision rate). Recommended: 10⁹+7 and 10⁹+9 as a double hash pair.

2. unordered_map hacked: On platforms like Codeforces, the default hash can be attacked. Always use custom_hash.

3. Substring hash subtraction underflow: h[r+1] - h[l] * pw[r-l+1] may be negative (with signed integers). Use unsigned long long natural overflow, or (... % M + M) % M to ensure non-negative.

4. BASE doesn't match character set: For lowercase letters (26 types), BASE must be > 26 (typically 31 or 131). For all ASCII characters (128 types), BASE must be > 128 (use 131 or 137).

5. Hash collision causing WA: Even with double hashing, collisions are theoretically possible. If uncertain, add direct string comparison when hashes match.

Chapter Summary

📌 Core Comparison Table

❓ FAQ

Q1: Which is better — unsigned long long natural overflow double hash or manual mod hash?

A: ull natural overflow (equivalent to mod 2⁶⁴) is simpler to code, and 2⁶⁴ is large enough that single-hash collision probability is already very low (≈ 10⁻¹⁸). But crafted data can deliberately cause collisions — double hashing is safer then. Both work in contests; ull is more common.

Q2: What can string hashing do that KMP cannot?

A: String hashing excels at multi-string comparison (e.g., finding longest common substring, palindromic substrings), while KMP only excels at single-pattern matching. Hash + binary search can solve many string problems in O(N log N) that would require more complex KMP implementations.

Q3: Should I use BASE 31 or 131?

A: Use 31 for lowercase letters only (a prime less than 37, avoids too-small hash space). Use 131 for mixed case or digits (a prime greater than 128, covers full ASCII). The key is: BASE must be larger than the character set size and ideally a prime.

Practice Problems

Problem 3.7.1 — Two Sum with Hash 🟢 Easy Given array A, find if any two distinct elements sum to target X. Use unordered_set.

Problem 3.7.2 — Substring Check 🟢 Easy Given string T and pattern P, check if P appears in T. Print all starting indices.

Problem 3.7.3 — Longest Palindromic Substring 🟡 Medium Find the length of the longest palindromic substring.

Problem 3.7.4 — Count Distinct Substrings 🟡 Medium Given string S of length N (N ≤ 5000), count the number of distinct substrings.

Problem 3.7.5 — String Periods 🔴 Hard Find the smallest period of a string S (smallest k such that S is a repetition of S[0..k-1]).

Chapter 3.8: Maps & Sets

Maps and sets are the workhorses of frequency counting, lookup, and tracking unique elements. In this chapter, we go deep into their practical use in USACO problems.

3.8.1 map vs unordered_map — Choosing Wisely

Visual: Map Internal Structure (BST)

std::map stores key-value pairs in a balanced BST (Red-Black tree). This gives O(log N) for all operations and keeps keys sorted automatically — great when you need lower_bound/upper_bound queries. Use unordered_map when you only need O(1) lookups and don't care about order.

For most USACO problems, either works fine. Use unordered_map for speed when keys are integers or strings, map when you need ordered iteration.

Example: Frequency Map

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    unordered_map<int, int> freq;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        freq[x]++;   // increment count; creates with 0 if not present
    }

    // Find the element with highest frequency
    int maxFreq = 0, maxVal = INT_MIN;
    for (auto &[val, count] : freq) {   // structured binding (C++17)
        if (count > maxFreq || (count == maxFreq && val < maxVal)) {
            maxFreq = count;
            maxVal = val;
        }
    }

    cout << "Most frequent: " << maxVal << " (" << maxFreq << " times)\n";

    return 0;
}

3.8.2 Map Operations — Complete Reference

#include <bits/stdc++.h>
using namespace std;

int main() {
    map<string, int> scores;

    // Insert
    scores["Alice"] = 95;
    scores["Bob"] = 87;
    scores["Charlie"] = 92;
    scores.insert({"Dave", 78});    // another way
    scores.emplace("Eve", 88);      // most efficient way

    // Lookup
    cout << scores["Alice"] << "\n";  // 95
    // WARNING: scores["Unknown"] creates it with value 0!

    // Safe lookup
    if (scores.count("Frank")) {
        cout << scores["Frank"] << "\n";
    } else {
        cout << "Frank not found\n";
    }

    // Using find() — returns iterator
    auto it = scores.find("Bob");
    if (it != scores.end()) {
        cout << it->first << ": " << it->second << "\n";  // Bob: 87
    }

    // Update
    scores["Alice"] += 5;    // Alice now has 100

    // Erase
    scores.erase("Charlie");

    // Iterate in sorted key order (map always gives sorted order)
    for (const auto &[name, score] : scores) {
        cout << name << ": " << score << "\n";
    }
    // Alice: 100
    // Bob: 87
    // Dave: 78
    // Eve: 88

    // Size and empty check
    cout << scores.size() << "\n";   // 4
    cout << scores.empty() << "\n";  // 0 (false)

    // Clear all entries
    scores.clear();

    return 0;
}

3.8.3 Set Operations — Complete Reference

#include <bits/stdc++.h>
using namespace std;

int main() {
    set<int> s = {5, 3, 8, 1, 9, 2};
    // s = {1, 2, 3, 5, 8, 9} (always sorted!)

    // Insert
    s.insert(4);   // s = {1, 2, 3, 4, 5, 8, 9}
    s.insert(3);   // already there, no change

    // Erase
    s.erase(8);    // s = {1, 2, 3, 4, 5, 9}

    // Lookup
    cout << s.count(3) << "\n";  // 1 (exists)
    cout << s.count(7) << "\n";  // 0 (not found)

    // Iterator-based queries
    auto it = s.lower_bound(4);  // first element >= 4
    cout << *it << "\n";         // 4

    auto it2 = s.upper_bound(4); // first element > 4
    cout << *it2 << "\n";        // 5

    // Min and Max
    cout << *s.begin() << "\n";   // 1 (min)
    cout << *s.rbegin() << "\n";  // 9 (max)

    // Remove minimum
    s.erase(s.begin());   // removes 1
    cout << *s.begin() << "\n";  // 2

    // Iterate
    for (int x : s) cout << x << " ";
    cout << "\n";  // 2 3 4 5 9

    return 0;
}

3.8.4 USACO Problem: Cow IDs

Problem (USACO 2017 February Bronze): Bessie wants to find the N-th smallest number that doesn't appear in a set of "taken" IDs. Given a set of taken IDs and N, find the N-th available ID.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q;
    cin >> n >> q;

    set<int> taken;
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        taken.insert(x);
    }

    // For each query q, find the q-th positive integer NOT in taken
    while (q--) {
        int k; cin >> k;

        // Binary search: find smallest x such that x - (# taken values <= x) >= k
        int lo = 1, hi = 2e9;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            // count of available numbers in [1, mid] = mid - (# taken values <= mid)
            int taken_count = (int)(taken.lower_bound(mid + 1) - taken.begin());
            int available = mid - taken_count;
            if (available >= k) hi = mid;
            else lo = mid + 1;
        }

        cout << lo << "\n";
    }

    return 0;
}

3.8.5 Multiset — Sorted Bag with Duplicates

A multiset is like a set, but allows duplicate values:

#include <bits/stdc++.h>
using namespace std;

int main() {
    multiset<int> ms;
    ms.insert(3);
    ms.insert(1);
    ms.insert(3);   // duplicate allowed
    ms.insert(5);
    ms.insert(1);

    // ms = {1, 1, 3, 3, 5}

    cout << ms.count(3) << "\n";  // 2 (how many 3s)
    cout << ms.count(2) << "\n";  // 0

    // Remove ONE occurrence of 3
    ms.erase(ms.find(3));  // removes only one 3
    // ms = {1, 1, 3, 5}

    // Remove ALL occurrences of 1
    ms.erase(1);  // removes all 1s
    // ms = {3, 5}

    cout << *ms.begin() << "\n";   // 3 (min)
    cout << *ms.rbegin() << "\n";  // 5 (max)

    return 0;
}

Running Median with Two Multisets

Keep track of the median of a stream of numbers using a max-multiset (lower half) and a min-multiset (upper half):

#include <bits/stdc++.h>
using namespace std;

int main() {
    multiset<int> lo;  // max-heap: lower half (use negation or reverse iterator)
    multiset<int> hi;  // min-heap: upper half

    // For simplicity, use two multisets where lo stores values in reverse
    // lo's maximum = lo.rbegin(); hi's minimum = hi.begin()

    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;

        // Add to appropriate half
        if (lo.empty() || x <= *lo.rbegin()) {
            lo.insert(x);
        } else {
            hi.insert(x);
        }

        // Rebalance: sizes should differ by at most 1
        while (lo.size() > hi.size() + 1) {
            hi.insert(*lo.rbegin());
            lo.erase(lo.find(*lo.rbegin()));
        }
        while (hi.size() > lo.size()) {
            lo.insert(*hi.begin());
            hi.erase(hi.begin());
        }

        // Print median
        if (lo.size() == hi.size()) {
            // Even count: average of two middle values
            double median = (*lo.rbegin() + *hi.begin()) / 2.0;
            cout << fixed << setprecision(1) << median << "\n";
        } else {
            // Odd count: middle value is in lo
            cout << *lo.rbegin() << "\n";
        }
    }

    return 0;
}

3.8.6 Practical Patterns

Pattern 1: Counting Distinct Elements

vector<int> data = {1, 5, 3, 1, 2, 5, 5, 3};
set<int> distinct(data.begin(), data.end());
cout << "Distinct count: " << distinct.size() << "\n";  // 4

Pattern 2: Group by Frequency, Sort by Value

vector<int> nums = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
map<int, int> freq;
for (int x : nums) freq[x]++;

// Group values by their frequency
map<int, vector<int>> byFreq;
for (auto &[val, cnt] : freq) {
    byFreq[cnt].push_back(val);
}

// Print in order of frequency
for (auto &[cnt, vals] : byFreq) {
    for (int v : vals) cout << v << " (×" << cnt << ")\n";
}

Pattern 3: Offline Queries with Sorting

Sort queries along with events to process them together in O((N+Q) log N):

// Example: for each query point, count how many events have value <= query point
// Sort both arrays, sweep through with two pointers

⚠️ Common Mistakes in Chapter 3.8

Chapter Summary

📌 Key Takeaways

🧩 "Which Container to Use" Quick Reference

❓ FAQ

Q1: What's the difference between map's [] operator and find?

A: m[key] auto-creates a default value (0 for int) when key doesn't exist; m.find(key) only searches, doesn't create. If you just want to check if a key exists, use m.count(key) or m.find(key) != m.end().

Q2: Both multiset and priority_queue can get extremes — which to use?

A: priority_queue can only get the max (or min) and delete it, doesn't support deletion by value. multiset supports finding and deleting any value, more flexible. If you only need to repeatedly get the extreme, priority_queue is simpler; if you need to delete specific elements (e.g., removing elements leaving a sliding window), use multiset.

Q3: When can unordered_map be slower than map?

A: Two situations: ① When hash collisions are severe (many keys hash to the same bucket), degrades to O(N); ② In contests, adversaries deliberately construct data to hack unordered_map. Solution: use a custom hash function, or switch to map.

Q4: Is C++17 structured binding auto &[key, val] safe? Can I use it in contests?

A: USACO and most contest platforms support C++17, so for (auto &[key, val] : m) is safe to use. It's cleaner than entry.first/entry.second.

🔗 Connections to Later Chapters

• Chapter 3.3 (Sorting & Searching): coordinate compression often combines with map (value → compressed index)
• Chapter 3.9 (Segment Trees): ordered set's lower_bound can replace simple segment tree queries
• Chapters 5.1–5.2 (Graphs): map is commonly used to store adjacency lists for sparse graphs
• Chapter 4.1 (Greedy): multiset combined with greedy strategies can efficiently maintain dynamic optimal choices
• The map frequency counting pattern appears throughout the book and is one of the most fundamental tools in competitive programming

Practice Problems

Problem 3.8.1 — Two Sum Read N integers and a target T. Find two values in the array that sum to T. Print their indices (1-indexed). (Hint: use a map to store value → index)

Problem 3.8.2 — Anagram Groups Read N words. Group them by their sorted-letter form. Print each group on one line, sorted alphabetically.

• Example: "eat tea tan ate nat bat" → groups: {ate, eat, tea}, {bat}, {nat, tan}

Problem 3.8.3 — Interval Overlap Count Read N intervals [L_i, R_i]. For each integer point from 1 to M, count how many intervals contain it. Output the maximum overlap count. (Hint: use difference array, or sort events and sweep with a set)

Problem 3.8.4 — Cow Photography (USACO Bronze Inspired) N cows each have a unique ID. Read N lists (each a permutation of IDs). Find the ordering that's consistent with all lists (the "true" order). (Hint: use maps to count pairwise orderings)

Problem 3.8.5 — Running Distinct Count Read N integers one by one. After each new integer, print the count of distinct values seen so far. (Hint: maintain an unordered_set; its size is the answer)

Chapter 3.9: Introduction to Segment Trees

📝 Before You Continue: You should understand prefix sums (Chapter 3.2), arrays, and recursion (Chapter 2.3). Segment trees are a more advanced data structure — make sure you're comfortable with recursion before diving in.

Segment trees are one of the most powerful data structures in competitive programming. They solve a fundamental problem that prefix sums cannot: range queries with updates.

3.9.1 The Problem: Why We Need Segment Trees

Consider this challenge:

• Array A of N integers
• Q1: What is the sum of A[l..r]? (Range sum query)
• Q2: Update A[i] = x (Point update)

Prefix sum solution: Range query in O(1), but update requires O(N) to recompute all prefix sums. For M mixed queries, total: O(NM) — too slow for N,M = 10^5.

Segment tree solution: Both query and update in O(log N). For M mixed queries: O(M log N) ✓

The diagram shows a segment tree built on array [1, 3, 5, 7, 9, 11]. Each internal node stores the sum of its range. A query for range [2,4] (sum=21) is answered by combining just 2 nodes — O(log N) instead of O(N).

3.9.2 Structure: What Is a Segment Tree?

A segment tree is a complete binary tree where:

• Each leaf corresponds to a single array element
• Each internal node stores the aggregate (sum, min, max, etc.) of its range
• The root covers the entire array [0..N-1]
• A node covering [l..r] has two children: [l..mid] and [mid+1..r]

For an array of N elements, the tree has at most 4N nodes (we use a 1-indexed tree array of size 4N as a safe upper bound).

Array: [1, 3, 5, 7, 9, 11]  (indices 0..5)

Tree (1-indexed, node i has children 2i and 2i+1):
         [0..5]=36
        /          \
  [0..2]=9       [3..5]=27
   /     \        /      \
[0..1]=4 [2]=5  [3..4]=16  [5]=11
  /   \          /    \
[0]=1 [1]=3   [3]=7  [4]=9

下图展示了线段树的完整结构，以及查询 sum([2,4]) 时蓝色高亮的访问路径：

3.9.3 Building the Segment Tree

// Solution: Segment Tree Build — O(N)
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
int tree[4 * MAXN];  // segment tree array (4x array size for safety)
int arr[MAXN];       // original array

// Build: recursively fill tree[]
// node = current tree node index (start with 1)
// start, end = range this node covers
void build(int node, int start, int end) {
    if (start == end) {
        // Leaf node: stores the array element
        tree[node] = arr[start];
    } else {
        int mid = (start + end) / 2;
        // Build left and right children first
        build(2 * node, start, mid);        // left child
        build(2 * node + 1, mid + 1, end);  // right child
        // Internal node: sum of children
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> arr[i];

    build(1, 0, n - 1);  // build from node 1, covering [0..n-1]

    return 0;
}

Build trace for [1, 3, 5, 7, 9, 11]:

build(1, 0, 5):
  build(2, 0, 2):
    build(4, 0, 1):
      build(8, 0, 0): tree[8] = arr[0] = 1
      build(9, 1, 1): tree[9] = arr[1] = 3
      tree[4] = tree[8] + tree[9] = 4
    build(5, 2, 2): tree[5] = arr[2] = 5
    tree[2] = tree[4] + tree[5] = 9
  build(3, 3, 5):
    build(6, 3, 4):
      ...
    tree[3] = 27
  tree[1] = 9 + 27 = 36

3.9.4 Range Query

Query sum of arr[l..r]:

Key idea: Recursively descend the tree. At each node covering [start..end]:

• If [start..end] is completely inside [l..r]: return this node's value (done!)
• If [start..end] is completely outside [l..r]: return 0 (no contribution)
• Otherwise: recurse into both children, sum the results

// Range Query: sum of arr[l..r] — O(log N)
// node = current tree node, [start, end] = range it covers
// [l, r] = query range
int query(int node, int start, int end, int l, int r) {
    if (r < start || end < l) {
        // Case 1: Current segment completely outside query range
        return 0;   // identity for sum (use INT_MAX for min queries)
    }
    if (l <= start && end <= r) {
        // Case 2: Current segment completely inside query range
        return tree[node];   // ← KEY LINE: use this node directly!
    }
    // Case 3: Partial overlap — recurse into children
    int mid = (start + end) / 2;
    int leftSum  = query(2 * node, start, mid, l, r);
    int rightSum = query(2 * node + 1, mid + 1, end, l, r);
    return leftSum + rightSum;
}

// Usage: sum of arr[2..4]
int result = query(1, 0, n - 1, 2, 4);
cout << result << "\n";  // 5 + 7 + 9 = 21

Query trace for [2..4] on tree of [1,3,5,7,9,11]:

query(1, 0, 5, 2, 4):
  query(2, 0, 2, 2, 4): [0..2] partially overlaps [2..4]
    query(4, 0, 1, 2, 4): [0..1] outside [2..4] → return 0
    query(5, 2, 2, 2, 4): [2..2] inside [2..4] → return 5
    return 0 + 5 = 5
  query(3, 3, 5, 2, 4): [3..5] partially overlaps [2..4]
    query(6, 3, 4, 2, 4): [3..4] inside [2..4] → return 16
    query(7, 5, 5, 2, 4): [5..5] outside [2..4] → return 0
    return 16 + 0 = 16
  return 5 + 16 = 21 ✓

Only 4 nodes visited — O(log N)!

3.9.5 Point Update

Update arr[i] = x (change a single element):

// Point Update: set arr[idx] = val — O(log N)
void update(int node, int start, int end, int idx, int val) {
    if (start == end) {
        // Leaf: update the value
        arr[idx] = val;
        tree[node] = val;
    } else {
        int mid = (start + end) / 2;
        if (idx <= mid) {
            update(2 * node, start, mid, idx, val);      // update in left child
        } else {
            update(2 * node + 1, mid + 1, end, idx, val); // update in right child
        }
        // Update this internal node after child changes
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }
}

// Usage: set arr[2] = 10
update(1, 0, n - 1, 2, 10);

3.9.6 Complete Implementation

Here's the full, contest-ready segment tree:

// Solution: Segment Tree — O(N) build, O(log N) query/update
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
long long tree[4 * MAXN];

void build(int node, int start, int end, long long arr[]) {
    if (start == end) {
        tree[node] = arr[start];
        return;
    }
    int mid = (start + end) / 2;
    build(2 * node, start, mid, arr);
    build(2 * node + 1, mid + 1, end, arr);
    tree[node] = tree[2 * node] + tree[2 * node + 1];
}

long long query(int node, int start, int end, int l, int r) {
    if (r < start || end < l) return 0;
    if (l <= start && end <= r) return tree[node];
    int mid = (start + end) / 2;
    return query(2 * node, start, mid, l, r)
         + query(2 * node + 1, mid + 1, end, l, r);
}

void update(int node, int start, int end, int idx, long long val) {
    if (start == end) {
        tree[node] = val;
        return;
    }
    int mid = (start + end) / 2;
    if (idx <= mid) update(2 * node, start, mid, idx, val);
    else update(2 * node + 1, mid + 1, end, idx, val);
    tree[node] = tree[2 * node] + tree[2 * node + 1];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q;
    cin >> n >> q;
    long long arr[MAXN];
    for (int i = 0; i < n; i++) cin >> arr[i];

    build(1, 0, n - 1, arr);

    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            // Point update: set arr[i] = v
            int i; long long v;
            cin >> i >> v;
            update(1, 0, n - 1, i, v);
        } else {
            // Range query: sum of arr[l..r]
            int l, r;
            cin >> l >> r;
            cout << query(1, 0, n - 1, l, r) << "\n";
        }
    }

    return 0;
}

Sample Input:

6 5
1 3 5 7 9 11
2 2 4
1 2 10
2 2 4
2 0 5
1 0 0

Sample Output:

21
26
41

(第1次查询 [2,4] = 5+7+9 = 21；执行 update arr[2]=10 后，第2次查询 [2,4] = 10+7+9 = 26；第3次查询 [0,5] = 1+3+10+7+9+11 = 41；最后一条操作 update arr[0]=0 无输出)

3.9.7 Segment Tree vs. Fenwick Tree (BIT)

💡 Key Insight: If you need range sum with updates, a Fenwick tree is simpler. If you need range minimum, range maximum, or any other aggregate that isn't a prefix operation, use a segment tree.

3.9.8 Range Minimum Query Variant

Just change the aggregate from + to min:

// Range Minimum Segment Tree — same structure, different operation
void build_min(int node, int start, int end, int arr[]) {
    if (start == end) { tree[node] = arr[start]; return; }
    int mid = (start + end) / 2;
    build_min(2*node, start, mid, arr);
    build_min(2*node+1, mid+1, end, arr);
    tree[node] = min(tree[2*node], tree[2*node+1]);  // ← changed to min
}

int query_min(int node, int start, int end, int l, int r) {
    if (r < start || end < l) return INT_MAX;   // ← identity for min
    if (l <= start && end <= r) return tree[node];
    int mid = (start + end) / 2;
    return min(query_min(2*node, start, mid, l, r),
               query_min(2*node+1, mid+1, end, l, r));
}

⚠️ Common Mistakes

1. Array size too small: Always allocate tree[4 * MAXN]. Using 2 * MAXN will cause out-of-bounds for non-power-of-2 sizes.
2. Wrong identity for out-of-range: For sum queries, return 0. For min queries, return INT_MAX. For max queries, return INT_MIN.
3. Forgetting to update the parent node: After updating a child, you MUST recompute the parent: tree[node] = tree[2*node] + tree[2*node+1].
4. 0-indexed vs 1-indexed confusion: This implementation uses 0-indexed arrays but 1-indexed tree nodes. Be consistent.
5. Using segment tree when prefix sum suffices: If there are no updates, prefix sum (O(1) query) beats segment tree (O(log N) query). Use the simpler tool when appropriate.

Chapter Summary

📌 Key Takeaways

❓ FAQ

Q1: When to choose segment tree vs prefix sum?

A: Simple rule — if the array never changes, prefix sum is better (O(1) query vs O(log N)). If the array gets modified (point updates), use segment tree or BIT. If you need range updates (add a value to a range), use segment tree with lazy propagation.

Q2: Why does the tree array need size 4N?

A: A segment tree is a complete binary tree. When N is not a power of 2, the last level may be incomplete but still needs space. In the worst case, about 4N nodes are needed. Using 4*MAXN is a safe upper bound.

Q3: Which is better, Fenwick Tree (BIT) or Segment Tree?

A: BIT code is shorter (~15 lines vs 30 lines), has smaller constants, but can only handle "prefix-decomposable" operations (like sum). Segment Tree is more general (can do range min/max, GCD, etc.) and supports more complex operations (like lazy propagation). In contests: use BIT when possible, switch to Segment Tree when BIT is insufficient.

Q4: What types of queries can segment trees handle?

A: Any operation satisfying the associative law: sum (+), minimum (min), maximum (max), GCD, XOR, product, etc. The key is having an "identity element" (e.g., 0 for sum, INT_MAX for min, INT_MIN for max).

Q5: What is Lazy Propagation? When is it needed?

A: When you need to "add V to every element in range [L,R]" (range update), the naive approach updates every leaf from L to R (O(N)), which is too slow. Lazy Propagation stores updates "lazily" in internal nodes and only pushes them down when a child node actually needs to be queried, optimizing range updates to O(log N) as well.

🔗 Connections to Later Chapters

• Chapter 3.2 (Prefix Sums): the "simplified version" of segment trees — use prefix sums when there are no update operations
• Chapters 5.1–5.2 (Graphs): Euler Tour + segment tree can efficiently handle path queries on trees
• Chapters 6.1–6.3 (DP): some DP optimizations require segment trees to maintain range min/max of DP values
• Segment tree is a core data structure at USACO Gold level, mastering it solves a large number of Gold problems

Practice Problems

Problem 3.9.1 — Classic Range Sum 🟢 Easy Implement a segment tree. Handle N elements and Q queries: either update a single element or query the sum of a range.

Problem 3.9.2 — Range Minimum 🟡 Medium Same as above but query the minimum of a range. Handle point updates.

Problem 3.9.3 — Number of Inversions 🔴 Hard Count the number of pairs (i,j) where i < j and arr[i] > arr[j].

🏆 Challenge: USACO 2016 February Gold: Fencing the Cows A problem requiring range max queries with updates. Try solving it with both a Fenwick tree and a segment tree to understand the tradeoffs.

3.9.6 Lazy Propagation — Range Updates in O(log N)

The segment tree so far handles point updates (change one element). But what about range updates: "add V to all elements in [L, R]"?

Without lazy propagation, we'd need O(N) updates (one per element). With lazy propagation, we achieve O(log N) range updates.

💡 Key Insight: Instead of immediately updating all affected leaf nodes, we "lazily" defer the update — store it at the highest applicable node and only push it down when we actually need the children.

How Lazy Propagation Works

Each node now stores two values:

• tree[node]: the actual aggregated value (range sum) for this range
• lazy[node]: a pending update that hasn't been pushed to children yet

The push-down rule: When we visit a node with a pending lazy update, we:

1. Apply the lazy update to the node's value
2. Pass the lazy update to both children (push down)
3. Clear the lazy for this node

Example: Array = [1, 2, 3, 4, 5], update "add 10 to [1..3]"

Initial tree:
         [15]            ← sum of [0..4]
        /      \
     [6]        [9]      ← sum of [0..2], [3..4]
    /   \      /   \
  [3]  [3]  [4]   [5]   ← sum of [0..1], [2], [3], [4]
  / \
 [1] [2]

After update "add 10 to [1..3]" with lazy propagation:
We need to update indices 1, 2, 3 (0-indexed).

At node covering [0..2]:
  - Only partially inside [1..3], so recurse down
  
At node covering [0..1]:
  - Partially inside [1..3], so recurse down
  - At leaf [1]: update arr[1] += 10. tree = [1, 12, 3, 4, 5]
  
At leaf [2]:
  - Fully inside [1..3]: store lazy, don't recurse!
  - lazy[covering [2]] = +10
  - tree[node] += 10 × (length of [2]) = +10
  
At node covering [3..4]:
  - Partially inside, recurse to [3]
  - Leaf [3]: += 10

Complete Lazy Propagation Implementation

// Solution: Segment Tree with Lazy Propagation
// Supports: range add update, range sum query — O(log N) each
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAXN = 100005;

ll tree[4 * MAXN];   // tree[node] = sum of range
ll lazy[4 * MAXN];   // lazy[node] = pending add value (0 means no pending)

// ── PUSH DOWN: apply pending lazy to children ──
// Called before we recurse into children
void pushDown(int node, int start, int end) {
    if (lazy[node] == 0) return;  // no pending update, nothing to do
    
    int mid = (start + end) / 2;
    int left = 2 * node, right = 2 * node + 1;
    
    // Update left child's sum: add lazy * (number of elements in left child)
    tree[left]  += lazy[node] * (mid - start + 1);
    tree[right] += lazy[node] * (end - mid);
    
    // Pass lazy to children
    lazy[left]  += lazy[node];
    lazy[right] += lazy[node];
    
    // Clear current node's lazy (it's been pushed down)
    lazy[node] = 0;
}

// ── BUILD: construct tree from array ──
void build(int node, int start, int end, ll arr[]) {
    lazy[node] = 0;  // no pending updates initially
    if (start == end) {
        tree[node] = arr[start];
        return;
    }
    int mid = (start + end) / 2;
    build(2*node, start, mid, arr);
    build(2*node+1, mid+1, end, arr);
    tree[node] = tree[2*node] + tree[2*node+1];
}

// ── RANGE UPDATE: add val to all elements in [l, r] ──
void update(int node, int start, int end, int l, int r, ll val) {
    if (r < start || end < l) return;  // out of range: no-op
    
    if (l <= start && end <= r) {
        // Current segment fully inside [l, r]: apply lazy here, don't recurse
        tree[node] += val * (end - start + 1);  // ← KEY: multiply by range length
        lazy[node] += val;                        // store pending for children
        return;
    }
    
    // Partial overlap: push down existing lazy, then recurse
    pushDown(node, start, end);  // ← CRITICAL: push before recursing!
    
    int mid = (start + end) / 2;
    update(2*node,   start, mid, l, r, val);
    update(2*node+1, mid+1, end, l, r, val);
    
    // Update current node from children
    tree[node] = tree[2*node] + tree[2*node+1];
}

// ── RANGE QUERY: sum of elements in [l, r] ──
ll query(int node, int start, int end, int l, int r) {
    if (r < start || end < l) return 0;  // out of range
    
    if (l <= start && end <= r) {
        return tree[node];  // fully inside: return stored sum (already includes lazy!)
    }
    
    // Partial overlap: push down, then recurse
    pushDown(node, start, end);  // ← CRITICAL: push before recursing!
    
    int mid = (start + end) / 2;
    ll leftSum  = query(2*node,   start, mid, l, r);
    ll rightSum = query(2*node+1, mid+1, end, l, r);
    return leftSum + rightSum;
}

// ── COMPLETE EXAMPLE ──
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, q;
    cin >> n >> q;
    
    ll arr[MAXN];
    for (int i = 0; i < n; i++) cin >> arr[i];
    
    build(1, 0, n-1, arr);
    
    while (q--) {
        int type;
        cin >> type;
        
        if (type == 1) {
            // Range update: add val to [l, r]
            int l, r; ll val;
            cin >> l >> r >> val;
            update(1, 0, n-1, l, r, val);
        } else {
            // Range query: sum of [l, r]
            int l, r;
            cin >> l >> r;
            cout << query(1, 0, n-1, l, r) << "\n";
        }
    }
    
    return 0;
}

Visual Trace: Range Update with Lazy

Array: [1, 2, 3, 4, 5, 6]  (0-indexed)

Initial tree (sums):
tree[1]  = 21  [0..5]
tree[2]  =  6  [0..2]    tree[3]  = 15  [3..5]
tree[4]  =  3  [0..1]    tree[5]  =  3  [2..2]    tree[6]  =  7  [3..4]    tree[7]  =  6  [5..5]
tree[8]  =  1  [0..0]    tree[9]  =  2  [1..1]   tree[12]  =  4  [3..3]   tree[13]  =  3  [4..4]

update(1, 0, 5, 1, 4, +10):  (add 10 to indices 1..4)

  At node 1 [0..5]: partial overlap, pushDown(1)—no lazy. Recurse.
    At node 2 [0..2]: partial overlap, pushDown(2)—no lazy. Recurse.
      At node 4 [0..1]: partial overlap, pushDown(4)—no lazy. Recurse.
        At node 8 [0..0]: outside [1..4]. Return.
        At node 9 [1..1]: FULLY inside [1..4].
          tree[9] += 10×1 = 12. lazy[9] = 10. Return.
      tree[4] = tree[8] + tree[9] = 1 + 12 = 13.
      At node 5 [2..2]: FULLY inside [1..4].
        tree[5] += 10×1 = 13. lazy[5] = 10. Return.
    tree[2] = 13 + 13 = 26.
    At node 3 [3..5]: partial overlap. pushDown(3)—no lazy. Recurse.
      At node 6 [3..4]: FULLY inside [1..4].
        tree[6] += 10×2 = 27. lazy[6] = 10. Return.   ← lazy stored for later!
      At node 7 [5..5]: outside [1..4]. Return.
    tree[3] = 27 + 6 = 33.
  tree[1] = 26 + 33 = 59. ✓ (original 21 + 10×4 = 61... let me recheck)

query(1, 0, 5, 2, 3): sum of [2..3]
  At node 1 [0..5]: partial. pushDown(1)—no lazy. Recurse.
  At node 2 [0..2]: partial. pushDown(2)—no lazy. Recurse.
    At node 4 [0..1]: outside [2..3]. Return 0.
    At node 5 [2..2]: FULLY inside. Return tree[5] = 13. ✓ (arr[2] = 3+10 = 13)
  At node 3 [3..5]: partial. pushDown(3)—no lazy. Recurse.
    At node 6 [3..4]: partial. pushDown(6)! (lazy[6] = 10)
      tree[12] += 10×1 = 14, lazy[12] = 10.
      tree[13] += 10×1 = 13, lazy[13] = 10.
      lazy[6] = 0.
      At node 12 [3..3]: FULLY inside. Return tree[12] = 14. ✓ (arr[3] = 4+10 = 14)
      At node 13 [4..4]: outside. Return 0.
  Result = 13 + 14 = 27. ✓

Complexity Analysis

Why O(log N)? Each update/query visits at most O(log N) "fully covered" nodes (where we stop and apply lazy). Between two consecutive fully-covered nodes at the same level, there's at most one partially-covered node that requires descent.

⚠️ Lazy Propagation Common Mistakes

// BAD: This gives wrong answers!
void update(int node, int start, int end, int l, int r, ll val) {
    if (r < start || end < l) return;
    if (l <= start && end <= r) {
        tree[node] += val * (end - start + 1);
        lazy[node] += val;
        return;
    }
    // FORGOT: pushDown(node, start, end); ← BUG!
    int mid = (start + end) / 2;
    update(2*node,   start, mid, l, r, val);
    update(2*node+1, mid+1, end, l, r, val);
    tree[node] = tree[2*node] + tree[2*node+1];
}

// GOOD: Push pending lazy before going to children
void update(int node, int start, int end, int l, int r, ll val) {
    if (r < start || end < l) return;
    if (l <= start && end <= r) {
        tree[node] += val * (end - start + 1);
        lazy[node] += val;
        return;
    }
    pushDown(node, start, end);  // ← ALWAYS before recursing!
    int mid = (start + end) / 2;
    update(2*node,   start, mid, l, r, val);
    update(2*node+1, mid+1, end, l, r, val);
    tree[node] = tree[2*node] + tree[2*node+1];
}

Top 4 Lazy Propagation Bugs:

1. Forgetting pushDown before recursion — children receive parent's lazy on top of their own, giving wrong query results
2. Wrong size multiplier — tree[node] += val instead of tree[node] += val * (end - start + 1). The node stores a SUM, so adding val to each of (end-start+1) elements means adding val*(size) to the sum.
3. Not initializing lazy[] to 0 — use memset(lazy, 0, sizeof(lazy)) or initialize in build()
4. Mixing lazy for different operations — if you have both "range add" and "range multiply" lazy, the order matters. You need two separate lazy arrays and a careful push-down combining both.

Generalizing Lazy Propagation

The pattern works for any operation where:

• The aggregate is an associative operation (sum, min, max, XOR...)
• The update distributes over the aggregate (sum += k*n when adding k to n elements)

Common variants:

Chapter 3.10: Fenwick Tree (Binary Indexed Tree)

📝 Before You Continue: You should already know prefix sums (Chapter 3.2) and bitwise operations. This chapter complements Segment Tree (Chapter 3.9) — BIT code is shorter, with smaller constants, but supports fewer operations.

Fenwick Tree (also known as Binary Indexed Tree / BIT) is one of the most commonly used data structures in competitive programming: under 15 lines of code, yet supports point updates and prefix queries in O(log N) time.

3.10.1 The Core Idea: What Is lowbit?

Bitwise Principle of lowbit

For any positive integer x, lowbit(x) = x & (-x) returns the value of the lowest set bit in the binary representation of x.

x  =  6  →  binary: 0110
-x = -6  →  two's complement: 1010  (bitwise NOT + 1)
x & (-x) = 0010 = 2   ← lowest set bit corresponds to 2^1 = 2

Examples:

BIT Tree Index Intuition

The elegance of BIT: tree[i] does not store a single element, but stores the sum of a range, with length exactly lowbit(i).

BIT 树形结构示意（n=8）：

flowchart BT
    T1["tree[1]\nA[1]\n管理 1 个"]
    T2["tree[2]\nA[1..2]\n管理 2 个"]
    T3["tree[3]\nA[3]\n管理 1 个"]
    T4["tree[4]\nA[1..4]\n管理 4 个"]
    T5["tree[5]\nA[5]\n管理 1 个"]
    T6["tree[6]\nA[5..6]\n管理 2 个"]
    T7["tree[7]\nA[7]\n管理 1 个"]
    T8["tree[8]\nA[1..8]\n管理 8 个"]
    T1 --> T2
    T3 --> T4
    T2 --> T4
    T5 --> T6
    T7 --> T8
    T6 --> T8
    T4 --> T8
    style T8 fill:#dbeafe,stroke:#3b82f6
    style T4 fill:#e0f2fe,stroke:#0284c7
    style T2 fill:#f0f9ff,stroke:#38bdf8
    style T6 fill:#f0f9ff,stroke:#38bdf8

查询 prefix(7) 的跳转路径：

flowchart LR
    Q7["i=7\n加 tree[7]=A[7]"] -->|"7-lowbit(7)=6"| Q6
    Q6["i=6\n加 tree[6]=A[5..6]"] -->|"6-lowbit(6)=4"| Q4
    Q4["i=4\n加 tree[4]=A[1..4]"] -->|"4-lowbit(4)=0"| Q0
    Q0(["i=0 停止\n共 3 步 = O(log 7)"])
    style Q0 fill:#dcfce7,stroke:#16a34a

💡 跳转规律： 查询时 i -= lowbit(i)（向下跳），更新时 i += lowbit(i)（向上跳）。每次跳转消除最低位的 1，最多 log N 步。

Index i:  1    2    3    4    5    6    7    8
Range managed by tree[i]:
  tree[1] = A[1]            (length lowbit(1)=1)
  tree[2] = A[1]+A[2]       (length lowbit(2)=2)
  tree[3] = A[3]            (length lowbit(3)=1)
  tree[4] = A[1]+...+A[4]   (length lowbit(4)=4)
  tree[5] = A[5]            (length lowbit(5)=1)
  tree[6] = A[5]+A[6]       (length lowbit(6)=2)
  tree[7] = A[7]            (length lowbit(7)=1)
  tree[8] = A[1]+...+A[8]   (length lowbit(8)=8)

更新位置 3 的跳转路径：

flowchart LR
    U3["i=3\n更新 tree[3]"] -->|"3+lowbit(3)=4"| U4
    U4["i=4\n更新 tree[4]"] -->|"4+lowbit(4)=8"| U8
    U8["i=8\n更新 tree[8]"] -->|"8+lowbit(8)=16>n"| U_end
    U_end(["i>n 停止\n共 3 步 = O(log N)"])
    style U_end fill:#dcfce7,stroke:#16a34a

When querying prefix sum prefix(7), jump up via i -= lowbit(i):

• i=7: add tree[7] (manages A[7]), then 7 - lowbit(7) = 7 - 1 = 6
• i=6: add tree[6] (manages A[5..6]), then 6 - lowbit(6) = 6 - 2 = 4
• i=4: add tree[4] (manages A[1..4]), then 4 - lowbit(4) = 4 - 4 = 0, stop

Total 3 steps = O(log 7) ≈ 3 steps.

When updating position 3, jump up via i += lowbit(i):

• i=3: update tree[3], then 3 + lowbit(3) = 3 + 1 = 4
• i=4: update tree[4], then 4 + lowbit(4) = 4 + 4 = 8
• i=8: update tree[8], 8 > n, stop

3.10.2 Point Update + Prefix Query — Complete Code

// ══════════════════════════════════════════════════════════════
// Fenwick Tree (Binary Indexed Tree) — Classic Implementation
// Supports: Point Update O(log N), Prefix Sum Query O(log N)
// Arrays are 1-INDEXED (critical!)
// ══════════════════════════════════════════════════════════════
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 300005;

int n;
long long tree[MAXN];  // BIT array, 1-indexed

// ── lowbit: returns the value of the lowest set bit ──
// x & (-x) works because:
//   -x in two's complement = ~x + 1
//   The lowest set bit of x is preserved, all higher bits cancel out
// Example: x=6 (0110), -x=1010, x&(-x)=0010=2
inline int lowbit(int x) {
    return x & (-x);
}

// ── update: add val to position i ──
// Walk UP the tree: i += lowbit(i)
// Each ancestor that covers position i gets updated
void update(int i, long long val) {
    for (; i <= n; i += lowbit(i))
        tree[i] += val;
    // Time: O(log N) — at most log2(N) iterations
}

// ── query: return prefix sum A[1..i] ──
// Walk DOWN the tree: i -= lowbit(i)
// Decompose [1..i] into O(log N) non-overlapping ranges
long long query(int i) {
    long long sum = 0;
    for (; i > 0; i -= lowbit(i))
        sum += tree[i];
    return sum;
    // Time: O(log N) — at most log2(N) iterations
}

// ── build: initialize BIT from an existing array A[1..n] ──
// Method 1: N individual updates — O(N log N)
void build_slow(long long A[]) {
    fill(tree + 1, tree + n + 1, 0LL);
    for (int i = 1; i <= n; i++)
        update(i, A[i]);
}

// Method 2: O(N) build using the "direct parent" trick
void build_fast(long long A[]) {
    for (int i = 1; i <= n; i++) {
        tree[i] += A[i];
        int parent = i + lowbit(i);  // direct parent in BIT
        if (parent <= n)
            tree[parent] += tree[i];
    }
}

// ── Full Example ──
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int q;
    cin >> n >> q;

    long long A[MAXN] = {};
    for (int i = 1; i <= n; i++) cin >> A[i];
    build_fast(A);  // O(N) initialization

    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            // Point update: A[i] += val
            int i; long long val;
            cin >> i >> val;
            update(i, val);
        } else {
            // Prefix query: sum of A[1..r]
            int r;
            cin >> r;
            cout << query(r) << "\n";
        }
    }
    return 0;
}

3.10.3 Range Query = prefix(r) - prefix(l-1)

Range query sum(l, r) is identical to the prefix sum technique:

// Range sum query: sum of A[l..r]
// Time: O(log N) — two prefix queries
long long range_query(int l, int r) {
    return query(r) - query(l - 1);
    // query(r)   = A[1] + A[2] + ... + A[r]
    // query(l-1) = A[1] + A[2] + ... + A[l-1]
    // difference = A[l] + A[l+1] + ... + A[r]
}

// Example usage:
// A = [3, 1, 4, 1, 5, 9, 2, 6]  (1-indexed)
// range_query(3, 6) = query(6) - query(2)
//                  = (3+1+4+1+5+9) - (3+1)
//                  = 23 - 4 = 19
// Verify: A[3]+A[4]+A[5]+A[6] = 4+1+5+9 = 19 ✓

3.10.4 Comparison: Prefix Sum vs BIT vs Segment Tree

When to choose BIT?

• ✅ Only need prefix/range sum + point update
• ✅ Need extremely concise code (fewer bugs in contest)
• ✅ Counting inversions, merge sort counting problems
• ❌ Need range min/max → use Segment Tree
• ❌ Need complex range operations (range multiply, etc.) → use Segment Tree

3.10.5 Interactive Visualization: BIT Update Process

3.10.6 Range Update + Point Query (Difference BIT)

Standard BIT supports "point update + prefix query". Using the difference array technique, it can instead support "range update + point query".

Principle

Let difference array D[i] = A[i] - A[i-1] (D[1] = A[1]), then:

• A[i] = D[1] + D[2] + ... + D[i] (i.e., A[i] is the prefix sum of D)
• Adding val to all A[l..r] is equivalent to: D[l] += val; D[r+1] -= val

// ══════════════════════════════════════════════════════════════
// Difference BIT: Range Update + Point Query
// ══════════════════════════════════════════════════════════════
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 300005;
int n;
long long diff_bit[MAXN];  // BIT over difference array D[]

inline int lowbit(int x) { return x & (-x); }

// Update D[i] += val in the difference BIT
void diff_update(int i, long long val) {
    for (; i <= n; i += lowbit(i))
        diff_bit[i] += val;
}

// Query A[i] = sum of D[1..i] = prefix query on diff BIT
long long diff_query(int i) {
    long long s = 0;
    for (; i > 0; i -= lowbit(i))
        s += diff_bit[i];
    return s;
}

// Range update: add val to all A[l..r]
// Equivalent to: D[l] += val, D[r+1] -= val
void range_update(int l, int r, long long val) {
    diff_update(l, val);       // D[l] += val
    diff_update(r + 1, -val);  // D[r+1] -= val
}

// Point query: return current value of A[i]
// A[i] = D[1] + D[2] + ... + D[i] = prefix_sum(D, i)
long long point_query(int i) {
    return diff_query(i);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int q;
    cin >> n >> q;
    // Initialize: read A[i], build diff BIT
    for (int i = 1; i <= n; i++) {
        long long x; cin >> x;
        // D[i] = A[i] - A[i-1]: use two updates
        diff_update(i, x);
        if (i + 1 <= n) diff_update(i + 1, -x); // will be overridden by next iteration
        // Simpler: just set D[i] = A[i]-A[i-1] directly
    }
    // Better initialization using range_update for each element:
    // fill diff_bit with 0, then range_update(i, i, A[i]) for each i
    // Or: diff_update(1, A[1]); for i>=2: diff_update(i, A[i]-A[i-1])

    while (q--) {
        int type; cin >> type;
        if (type == 1) {
            int l, r; long long val;
            cin >> l >> r >> val;
            range_update(l, r, val);  // A[l..r] += val, O(log N)
        } else {
            int i; cin >> i;
            cout << point_query(i) << "\n";  // query A[i], O(log N)
        }
    }
    return 0;
}

Advanced: Range Update + Range Query (Dual BIT)

To support both range update + range query simultaneously, use two BITs:

// ══════════════════════════════════════════════════════════════
// Double BIT: Range Update + Range Query
// Formula: sum(1..r) = B1[r] * r - B2[r]
// where B1 is BIT over D[], B2 is BIT over (i-1)*D[i]
// ══════════════════════════════════════════════════════════════
long long B1[MAXN], B2[MAXN];  // Two BITs

inline int lowbit(int x) { return x & (-x); }

void add(long long* b, int i, long long v) {
    for (; i <= n; i += lowbit(i)) b[i] += v;
}
long long sum(long long* b, int i) {
    long long s = 0;
    for (; i > 0; i -= lowbit(i)) s += b[i];
    return s;
}

// Range update: add val to A[l..r]
void range_add(int l, int r, long long val) {
    add(B1, l, val);
    add(B1, r + 1, -val);
    add(B2, l, val * (l - 1));     // compensate for prefix formula
    add(B2, r + 1, -val * r);
}

// Prefix sum A[1..r]
long long prefix_sum(int r) {
    return sum(B1, r) * r - sum(B2, r);
}

// Range sum A[l..r]
long long range_sum(int l, int r) {
    return prefix_sum(r) - prefix_sum(l - 1);
}

3.10.7 USACO-Style Problem: Counting Inversions with BIT

Problem Statement

Counting Inversions (O(N log N))

Given an integer array A of length N (distinct elements, range 1..N), count the number of inversions.

Inversion: a pair of indices (i, j) where i < j but A[i] > A[j].

Constraints: N ≤ 3×10⁵, requires O(N log N) solution.

Sample Input:

5
3 1 4 2 5

Sample Output:

3

Explanation: Inversions are (3,1), (3,2), (4,2), total 3 pairs.

Solution: BIT Inversion Count

// ══════════════════════════════════════════════════════════════
// Counting Inversions using Fenwick Tree — O(N log N)
//
// Key Idea:
//   Process A[i] from left to right.
//   For each A[i], the number of inversions with A[i] as the
//   RIGHT element = count of already-processed values > A[i]
//                 = (elements processed so far) - (elements <= A[i])
//                 = i-1 - prefix_query(A[i])
//   Sum over all i gives total inversions.
//
// BIT role: track frequency of seen values.
//   After seeing value v: update(v, +1)
//   Query # of values <= x: query(x)
// ══════════════════════════════════════════════════════════════
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAXN = 300005;

int n;
int bit[MAXN];  // BIT for frequency counting; bit[v] tracks how many times v appeared

inline int lowbit(int x) { return x & (-x); }

// Add 1 to position v (we saw value v)
void update(int v) {
    for (; v <= n; v += lowbit(v))
        bit[v]++;
}

// Count how many values in [1..v] have been seen
int query(int v) {
    int cnt = 0;
    for (; v > 0; v -= lowbit(v))
        cnt += bit[v];
    return cnt;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    
    ll inversions = 0;
    
    for (int i = 1; i <= n; i++) {
        int a;
        cin >> a;
        
        // Count inversions where a is the RIGHT element:
        // # of already-seen values GREATER than a
        // = (i-1 elements seen so far) - (# of seen values <= a)
        int less_or_equal = query(a);         // # of seen values in [1..a]
        int greater = (i - 1) - less_or_equal; // # of seen values in [a+1..n]
        inversions += greater;
        
        // Mark that we've now seen value a
        update(a);
    }
    
    cout << inversions << "\n";
    return 0;
}

/*
Trace for A = [3, 1, 4, 2, 5]:

i=1, a=3: seen=[], query(3)=0, greater=0-0=0. inversions=0. update(3).
i=2, a=1: seen=[3], query(1)=0, greater=1-0=1. inversions=1. update(1).
           (3 > 1: that's 1 inversion: (3,1) ✓)
i=3, a=4: seen=[3,1], query(4)=2, greater=2-2=0. inversions=1. update(4).
           (no element > 4 was seen before)
i=4, a=2: seen=[3,1,4], query(2)=1, greater=3-1=2. inversions=3. update(2).
           (3>2 and 4>2: 2 inversions: (3,2),(4,2) ✓)
i=5, a=5: seen=[3,1,4,2], query(5)=4, greater=4-4=0. inversions=3. update(5).

Final: 3 ✓
*/

Complexity Analysis:

• Time: O(N log N) — N iterations, each O(log N) for update + query
• Space: O(N) for BIT

Extension: If array elements are not in range 1..N, first apply coordinate compression before using BIT:

// Coordinate compression for arbitrary values
vector<int> A(n);
for (int i = 0; i < n; i++) cin >> A[i];

// Step 1: sort and deduplicate
vector<int> sorted_A = A;
sort(sorted_A.begin(), sorted_A.end());
sorted_A.erase(unique(sorted_A.begin(), sorted_A.end()), sorted_A.end());

// Step 2: replace each value with its rank (1-indexed)
for (int i = 0; i < n; i++) {
    A[i] = lower_bound(sorted_A.begin(), sorted_A.end(), A[i]) - sorted_A.begin() + 1;
    // A[i] is now in [1..M] where M = sorted_A.size()
}
// Now use BIT with n = sorted_A.size()

3.10.8 Common Mistakes

// ❌ WRONG — common typo/confusion
int lowbit(int x) { return x & (x - 1); }  // This CLEARS the lowest bit, not returns it!
// x=6 (0110): x&(x-1) = 0110&0101 = 0100 = 4 (WRONG, should be 2)

int lowbit(int x) { return x % 2; }         // Only works for last bit, not lowbit value

// ✅ CORRECT
int lowbit(int x) { return x & (-x); }
// x=6: -6 = ...11111010 (two's complement)
// 0110 & 11111010 = 0010 = 2 ✓

// ❌ WRONG — 0-indexed causes infinite loop!
// If i = 0: query loop: i -= lowbit(0) = 0 - (0 & 0) = 0 - 0 = 0 → infinite loop!
// (Actually lowbit(0) = 0 & 0 = 0, so i never decreases)

void query_WRONG(int i) {  // i is 0-indexed
    int s = 0;
    for (; i > 0; i -= lowbit(i))  // if i=0 initially, loop doesn't execute but
        s += bit[i];               // if called with i=0 during calculation... disaster
    return s;
}

// ❌ WRONG — forgetting +1 when converting to 1-indexed
int arr[n]; // 0-indexed A[0..n-1]
for (int i = 0; i < n; i++) {
    update(i, arr[i]);    // BUG: should be update(i+1, arr[i])
}

// ✅ CORRECT — always shift to 1-indexed
for (int i = 0; i < n; i++) {
    update(i + 1, arr[i]);  // convert 0-indexed i to 1-indexed i+1
}
// And remember: query(r+1) - query(l) for 0-indexed range [l, r]

// ❌ WRONG — tree[] should be long long for large sums
int tree[MAXN];   // overflow if sum > 2^31

// ✅ CORRECT
long long tree[MAXN];

// Also: when counting inversions, inversions can be up to N*(N-1)/2 ≈ 4.5×10^10 for N=3×10^5
// Always use long long for the result counter!
long long inversions = 0;  // ✅ not int!

// ❌ WRONG — in problems with multiple test cases
int T; cin >> T;
while (T--) {
    // forgot to clear tree[]!
    // Old data from previous test case corrupts results
    solve();
}

// ✅ CORRECT — reset before each test case
int T; cin >> T;
while (T--) {
    fill(tree + 1, tree + n + 1, 0LL);  // clear BIT
    solve();
}

3.10.9 Chapter Summary

📋 Formula Quick Reference

❓ FAQ

Q1: Both BIT and Segment Tree support prefix sum + point update. Which should I choose?

A: Use BIT whenever possible. BIT code is only 10 lines, has smaller constants (empirically 2-3x faster), and lower error probability. Only choose Segment Tree when you need range min/max (RMQ), range coloring, or more complex range operations. In contests, BIT is the "default weapon", Segment Tree is "heavy artillery".

Q2: Can BIT support Range Minimum Query (RMQ)?

A: Standard BIT cannot support RMQ, because the min operation has no "inverse" (cannot "undo" a merged min value like subtraction). For range min/max, use Segment Tree or Sparse Table. There is a "static BIT for RMQ" technique, but it only works without updates and has limited practical use.

Q3: Can BIT support 2D (2D BIT)?

A: Yes! 2D BIT solves 2D prefix sum + point update problems, with complexity O(log N × log M). The code structure uses two nested loops:

// 2D BIT update
void update2D(int x, int y, long long v) {
    for (int i = x; i <= N; i += lowbit(i))
        for (int j = y; j <= M; j += lowbit(j))
            bit[i][j] += v;
}

Less common in USACO, but occasionally needed for 2D coordinate counting problems.

3.10.10 Practice Problems

💡 Chapter Connection: BIT and Segment Tree are the two most commonly paired data structures in USACO. BIT handles 80% of scenarios with 1/5 the code of Segment Tree. After mastering BIT, return to Chapter 3.9 to learn Segment Tree lazy propagation—the territory BIT cannot reach.

Chapter 3.11: Binary Trees

Binary trees are the foundation of some of the most important data structures in competitive programming — from Binary Search Trees (BST) to Segment Trees to Heaps. Understanding them deeply will make graph algorithms, DP on trees, and USACO Gold problems significantly more approachable.

3.11.1 Binary Tree Fundamentals

A binary tree is a hierarchical data structure where:

• Each node has at most 2 children: a left child and a right child
• There is exactly one root node (no parent)
• Each non-root node has exactly one parent

Visual Example

In this tree:

• Height = 2 (longest root-to-leaf path: A → B → D)
• Root = A, Leaves = D, E, F
• B is parent of D and E; D is left child of B, E is right child of B

C++ Node Definition

Throughout this chapter, we use a consistent struct TreeNode:

// Solution: Basic Binary Tree Node
#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    
    // Constructor: initialize with value, no children
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

💡 Why raw pointers? In competitive programming, we often manage memory manually for speed. nullptr (C++11) is always safer than uninitialized pointers — always initialize left = right = nullptr.

3.11.2 Binary Search Trees (BST)

A Binary Search Tree is a binary tree with a crucial ordering property:

BST Property: For every node v:

• All values in the left subtree are strictly less than v.val
• All values in the right subtree are strictly greater than v.val

       [5]          ← valid BST
      /    \
    [3]    [8]
   /   \   /  \
  [1] [4] [7] [10]

  left of 5 = {1, 3, 4} — all < 5  ✓
  right of 5 = {7, 8, 10} — all > 5  ✓

3.11.2.1 BST Search

// Solution: BST Search — O(log N) average, O(N) worst case
// Returns pointer to node with value 'target', or nullptr if not found
TreeNode* search(TreeNode* root, int target) {
    // Base case: empty tree or found the target
    if (root == nullptr || root->val == target) {
        return root;
    }
    // BST property: go left if target is smaller
    if (target < root->val) {
        return search(root->left, target);
    }
    // Go right if target is larger
    return search(root->right, target);
}

Iterative version (avoids stack overflow for large trees):

// Solution: BST Search Iterative
TreeNode* searchIterative(TreeNode* root, int target) {
    while (root != nullptr) {
        if (target == root->val) return root;       // found
        else if (target < root->val) root = root->left;   // go left
        else root = root->right;                     // go right
    }
    return nullptr;  // not found
}

3.11.2.2 BST Insert

// Solution: BST Insert — O(log N) average
// Returns the (potentially new) root of the subtree
TreeNode* insert(TreeNode* root, int val) {
    // If we've reached a null spot, create the new node here
    if (root == nullptr) {
        return new TreeNode(val);
    }
    if (val < root->val) {
        root->left = insert(root->left, val);   // recurse left
    } else if (val > root->val) {
        root->right = insert(root->right, val); // recurse right
    }
    // val == root->val: duplicate, ignore (or handle as needed)
    return root;
}

// Usage:
// TreeNode* root = nullptr;
// root = insert(root, 5);
// root = insert(root, 3);
// root = insert(root, 8);

3.11.2.3 BST Delete

Deletion is the trickiest BST operation. There are 3 cases:

1. Node has no children (leaf): simply delete it
2. Node has one child: replace node with its child
3. Node has two children: replace with inorder successor (smallest in right subtree), then delete the successor

// Solution: BST Delete — O(log N) average
// Helper: find minimum node in a subtree
TreeNode* findMin(TreeNode* node) {
    while (node->left != nullptr) node = node->left;
    return node;
}

// Delete node with value 'val' from tree rooted at 'root'
TreeNode* deleteNode(TreeNode* root, int val) {
    if (root == nullptr) return nullptr;  // value not found
    
    if (val < root->val) {
        // Case: target is in left subtree
        root->left = deleteNode(root->left, val);
    } else if (val > root->val) {
        // Case: target is in right subtree
        root->right = deleteNode(root->right, val);
    } else {
        // Found the node to delete!
        
        // Case 1: No children (leaf)
        if (root->left == nullptr && root->right == nullptr) {
            delete root;
            return nullptr;
        }
        // Case 2a: Only right child
        else if (root->left == nullptr) {
            TreeNode* temp = root->right;
            delete root;
            return temp;
        }
        // Case 2b: Only left child
        else if (root->right == nullptr) {
            TreeNode* temp = root->left;
            delete root;
            return temp;
        }
        // Case 3: Two children — replace with inorder successor
        else {
            TreeNode* successor = findMin(root->right);  // smallest in right subtree
            root->val = successor->val;                  // copy successor's value
            root->right = deleteNode(root->right, successor->val);  // delete successor
        }
    }
    return root;
}

3.11.2.4 BST Degeneration Problem

⚠️ Critical Issue: If you insert values in sorted order (1, 2, 3, 4, 5...), the BST becomes a linked list:

[1]
  \
  [2]
    \
    [3]        ← This is O(N) per operation, not O(log N)!
      \
      [4]
        \
        [5]

This is why balanced BSTs (AVL trees, Red-Black trees) exist. In C++, std::set and std::map are implemented as Red-Black trees — always O(log N).

3.11.3 Tree Traversals

Traversal = visiting every node exactly once. There are 4 fundamental traversals:

3.11.3.1 Preorder Traversal

// Solution: Preorder Traversal — O(N) time, O(H) space (H = height)
// Visit order: Root, Left subtree, Right subtree
void preorder(TreeNode* root) {
    if (root == nullptr) return;   // base case
    cout << root->val << " ";      // process ROOT first
    preorder(root->left);          // then left subtree
    preorder(root->right);         // then right subtree
}

// For the tree:    [5]
//                 /    \
//               [3]    [8]
//              /   \
//            [1]   [4]
// Preorder: 5 3 1 4 8

Iterative Preorder (using stack):

// Solution: Preorder Iterative
void preorderIterative(TreeNode* root) {
    if (root == nullptr) return;
    stack<TreeNode*> stk;
    stk.push(root);
    
    while (!stk.empty()) {
        TreeNode* node = stk.top(); stk.pop();
        cout << node->val << " ";    // process current
        
        // Push RIGHT first (so LEFT is processed first — LIFO!)
        if (node->right) stk.push(node->right);
        if (node->left)  stk.push(node->left);
    }
}

3.11.3.2 Inorder Traversal

// Solution: Inorder Traversal — O(N) time
// Visit order: Left subtree, Root, Right subtree
// KEY PROPERTY: Inorder traversal of a BST gives SORTED output!
void inorder(TreeNode* root) {
    if (root == nullptr) return;
    inorder(root->left);           // left subtree first
    cout << root->val << " ";      // then ROOT
    inorder(root->right);          // then right subtree
}

// For BST with values {1, 3, 4, 5, 8}:
// Inorder: 1 3 4 5 8  ← sorted! This is the most important BST property

🔑 Key Insight: Inorder traversal of any BST always produces a sorted sequence. This is why std::set can be iterated in sorted order — it uses inorder traversal internally.

Iterative Inorder (slightly trickier):

// Solution: Inorder Iterative
void inorderIterative(TreeNode* root) {
    stack<TreeNode*> stk;
    TreeNode* curr = root;
    
    while (curr != nullptr || !stk.empty()) {
        // Go as far left as possible
        while (curr != nullptr) {
            stk.push(curr);
            curr = curr->left;
        }
        // Process the leftmost unprocessed node
        curr = stk.top(); stk.pop();
        cout << curr->val << " ";
        
        // Move to right subtree
        curr = curr->right;
    }
}

3.11.3.3 Postorder Traversal

// Solution: Postorder Traversal — O(N) time
// Visit order: Left subtree, Right subtree, Root
// Used for: deleting trees, evaluating expression trees
void postorder(TreeNode* root) {
    if (root == nullptr) return;
    postorder(root->left);         // left subtree first
    postorder(root->right);        // then right subtree
    cout << root->val << " ";      // ROOT last
}

// For BST [1, 3, 4, 5, 8]:
// Postorder: 1 4 3 8 5  (root 5 is always last)

// ── Memory cleanup using postorder ──
void deleteTree(TreeNode* root) {
    if (root == nullptr) return;
    deleteTree(root->left);   // delete left first
    deleteTree(root->right);  // then right
    delete root;              // then this node (safe: children already deleted)
}

3.11.3.4 Level-Order Traversal (BFS)

// Solution: Level-Order Traversal (BFS) — O(N) time, O(W) space (W = max width)
// Uses a queue: process nodes level by level
void levelOrder(TreeNode* root) {
    if (root == nullptr) return;
    
    queue<TreeNode*> q;
    q.push(root);
    
    while (!q.empty()) {
        int levelSize = q.size();  // number of nodes at current level
        
        for (int i = 0; i < levelSize; i++) {
            TreeNode* node = q.front(); q.pop();
            cout << node->val << " ";
            
            if (node->left)  q.push(node->left);
            if (node->right) q.push(node->right);
        }
        cout << "\n";  // newline between levels
    }
}

// For the BST [5, 3, 8, 1, 4]:
// Level 0: 5
// Level 1: 3 8
// Level 2: 1 4

Traversal Summary Table

Tree:           [5]
               /    \
             [3]    [8]
            /   \   /
          [1]  [4] [7]

Preorder:   5 3 1 4 8 7
Inorder:    1 3 4 5 7 8    ← sorted!
Postorder:  1 4 3 7 8 5
Level-order: 5 | 3 8 | 1 4 7

3.11.4 Tree Height and Balance

3.11.4.1 Computing Tree Height

// Solution: Tree Height — O(N) time, O(H) space for recursion stack
// Height = length of longest root-to-leaf path
// Convention: height of null tree = -1, leaf node height = 0
int height(TreeNode* root) {
    if (root == nullptr) return -1;  // empty subtree has height -1
    
    int leftHeight  = height(root->left);   // height of left subtree
    int rightHeight = height(root->right);  // height of right subtree
    
    return 1 + max(leftHeight, rightHeight);  // +1 for current node
}
// Time: O(N) — visit every node exactly once
// Space: O(H) — recursion stack depth = tree height

// Alternative: some define height as number of nodes on longest path
// Then: leaf has height 1, and empty tree has height 0
// Be careful about which convention your problem uses!

3.11.4.2 Checking Balance

A balanced binary tree requires that for every node, the heights of its left and right subtrees differ by at most 1.

// Solution: Check Balanced BST — O(N) time
// Returns -1 if unbalanced, otherwise returns the height of subtree
int checkBalanced(TreeNode* root) {
    if (root == nullptr) return 0;  // empty is balanced, height 0
    
    int leftH = checkBalanced(root->left);
    if (leftH == -1) return -1;     // left subtree is unbalanced
    
    int rightH = checkBalanced(root->right);
    if (rightH == -1) return -1;    // right subtree is unbalanced
    
    // Check balance at current node: heights can differ by at most 1
    if (abs(leftH - rightH) > 1) return -1;  // unbalanced!
    
    return 1 + max(leftH, rightH);   // return height if balanced
}

bool isBalanced(TreeNode* root) {
    return checkBalanced(root) != -1;
}

3.11.4.3 Counting Nodes

// Solution: Count Nodes — O(N)
int countNodes(TreeNode* root) {
    if (root == nullptr) return 0;
    return 1 + countNodes(root->left) + countNodes(root->right);
}

// Count leaves specifically
int countLeaves(TreeNode* root) {
    if (root == nullptr) return 0;
    if (root->left == nullptr && root->right == nullptr) return 1;  // leaf!
    return countLeaves(root->left) + countLeaves(root->right);
}

3.11.5 Lowest Common Ancestor (LCA) — Brute Force

The LCA of two nodes u and v in a rooted tree is the deepest node that is an ancestor of both.

          [1]
         /    \
       [2]    [3]
      /   \      \
    [4]   [5]   [6]
   /
  [7]

LCA(4, 5) = 2     (both 4 and 5 are descendants of 2)
LCA(4, 6) = 1     (deepest common ancestor is the root 1)
LCA(2, 4) = 2     (node 2 is ancestor of 4 and ancestor of itself)

O(N) Brute Force LCA

// Solution: LCA Brute Force — O(N) per query
// Strategy: find path from root to each node, then find last common node

// Step 1: Find path from root to target node
bool findPath(TreeNode* root, int target, vector<int>& path) {
    if (root == nullptr) return false;
    
    path.push_back(root->val);  // add current node to path
    
    if (root->val == target) return true;  // found target!
    
    // Try left then right
    if (findPath(root->left, target, path)) return true;
    if (findPath(root->right, target, path)) return true;
    
    path.pop_back();  // backtrack: target not in this subtree
    return false;
}

// Step 2: Find LCA using two paths
int lca(TreeNode* root, int u, int v) {
    vector<int> pathU, pathV;
    
    findPath(root, u, pathU);   // path from root to u
    findPath(root, v, pathV);   // path from root to v
    
    // Find last common node in both paths
    int result = root->val;
    int minLen = min(pathU.size(), pathV.size());
    
    for (int i = 0; i < minLen; i++) {
        if (pathU[i] == pathV[i]) {
            result = pathU[i];  // still common
        } else {
            break;  // diverged
        }
    }
    return result;
}

💡 USACO Note: For USACO Silver problems, the O(N) brute force LCA is NOT always sufficient. With N ≤ 10^5 nodes and Q ≤ 10^5 queries, the total is O(NQ) = O(10^10) — too slow. Use it only when N, Q ≤ 5000. Chapter 5.3 covers O(log N) LCA with binary lifting for harder problems.