ADVANCED ALGORITHMS AND DATA STRUCTURES IN C++ FOR COMPETITIVE
PROGRAMMING
1. STANDARD TEMPLATE LIBRARY (STL) MASTERY
Efficiency in C++ competitive programming relies heavily on the STL.
- Vectors: Dynamic arrays. Key operations: push_back() is O(1) amortized. Resizing causes
a copy, so reserve() should be used if size is known.
- Maps & Sets: Implementations of Red-Black trees (Self-balancing BST). Insertion,
deletion, and lookup are O(log N).
- Unordered_map: Hash table implementation. Average case O(1), but worst case O(N) if
collisions are high. Custom hash functions are often needed for complex keys (like pairs) to
avoid collisions in adversarial test cases.
- Priority Queue: Implements a binary heap. Essential for Dijkstra’s algorithm and Prim’s
algorithm. By default, it is a max-heap. For a min-heap, use `priority_queue<int,
vector<int>, greater<int>>`.
2. GRAPH ALGORITHMS
- BFS (Breadth-First Search): Used for finding the shortest path in unweighted graphs. Time
complexity O(V+E). Implemented using a queue.
- DFS (Depth-First Search): Used for topological sorting, cycle detection, and connectivity
checks. Implemented using recursion or a stack.
- Dijkstra’s Algorithm: Finds shortest paths from a source to all other nodes in a graph with
non-negative edge weights. Using a priority queue, complexity is O(E log V).
- Bellman-Ford: Handles negative edge weights and can detect negative cycles. Complexity
O(V*E).
- Floyd-Warshall: All-pairs shortest path algorithm. Dynamic programming approach.
Complexity O(V^3).
- Disjoint Set Union (DSU): Essential for Kruskal’s Minimum Spanning Tree algorithm and
handling dynamic connectivity queries. Optimizations include Path Compression and
Union by Rank, achieving nearly O(1) time complexity (inverse Ackermann function).
2. DYNAMIC PROGRAMMING (DP)
DP solves complex problems by breaking them into overlapping subproblems and storing
the results (memoization or tabulation).
- 1D DP: Typical examples include the Fibonacci sequence, Climbing Stairs, and Longest
Increasing Subsequence (LIS), which can be optimized to O(N log N).
- Knapsack Problem: The 0/1 Knapsack is a classic 2D DP problem. State definition:
dp[i][w] = max value using first I items with weight limit w.
- Bitmask DP: Used when the constraints are small (N <= 20). The state represents a subset
of elements using bits. Useful for the Traveling Salesperson Problem (TSP) and Hamiltonian
paths.
4. ADVANCED DATA STRUCTURES
- Segment Tree: Allows range queries (sum, min, max) and point updates in O(log N) time.
Lazy propagation is used for range updates to maintain O(log N) complexity.
- Fenwick Tree (Binary Indexed Tree): simpler to code than Segment Trees for prefix sums
and point updates. Uses bitwise operations to traverse the tree structure.
- Trie (Prefix Tree): Efficient for string retrieval and prefix matching. Operations are O(L)
where L is the string length. Useful for autocomplete and maximum XOR pair problems.
5. NUMBER THEORY AND MATHEMATICS
- Sieve of Eratosthenes: Efficiently generates primes up to N. Complexity O(N log log N).
- Modular Arithmetic: Crucial for problems requiring answers modulo 10^9 + 7. Properties:
(a+b)%m = ((a%m)+(b%m))%m. Modular Inverse using Fermat’s Little Theorem is needed
for division modulo m (only if m is prime).
- Euclidean Algorithm: Computes GCD(a, b). Extended Euclidean Algorithm finds x, y such
that ax + by = gcd(a, b), which is useful for solving Linear Diophantine Equations.
6. OPTIMIZATION TECHNIQUES
- Two Pointers: Reduces O(N^2) loops to O(N) for sorted arrays or specific conditions (e.g.,
finding a subarray with a specific sum).
- Binary Search on Answer: Instead of finding the answer directly, check if a value X is
possible (monotonic function) and binary search the range of answers.
- Sliding Window: Optimizes problems involving fixed-size or variable-size subarrays.