Platinum
The topics below are not exhaustive for this division.
Contest problems may contain topics not covered in the guide, or topics listed under different divisions!
Some lower-frequency topics are included in "Advanced."
Modules Progress
Problems Progress
Range Queries
More Applications of Segment Tree
Somewhat Frequent
Walking on a Segment Tree, Non-Commutative Combiner Functions
Range Queries with Sweep Line
Not Frequent
Solving 2D grid problems using 1D range queries.
Range Update Range Query
Rare
Lazy updates on segment trees and two binary indexed trees in conjunction.
Sparse Segment Trees
Rare
Querying big ranges.
Updated: 2 weeks ago
2D Range Queries
Rare
Extending Range Queries to 2D (and beyond).
Divide & Conquer - SRQ
Rare
Using Divide & Conquer to answer offline or online range queries on a static array.
Square Root Decomposition
Rare
Splitting up data into smaller chunks to speed up processing.
Trees
Binary Jumping
Somewhat Frequent
Efficiently finding ancestors of a node.
Small-To-Large Merging
Rare
A way to merge two sets efficiently.
Heavy-Light Decomposition
Rare
Path and subtree updates and queries.
Centroid Decomposition
Rare
Decomposing a tree to facilitate path computations.
Virtual Tree
Has Not Appeared
Compressing a tree to only the necessary nodes.
Updated: 6 days ago
Kruskal Reconstruction Tree
Rare
Decomposing Kruskal's algorithm to solve problems about minimum/maximum edge weights.
Updated: 4 days ago
Geometry
Geometry Primitives
Rare
Basic setup for geometry problems.
Sweep Line
Rare
Introduction to line sweep.
Convex Hull
Not Frequent
Smallest convex polygon containing a set of points on a grid.
Convex Hull Trick
Not Frequent
A way to find the maximum or minimum value of several convex functions at given points.
Misc. Topics
Inclusion-Exclusion Principle
Rare
The inclusion-exclusion principle is a counting technique that generalizes the formula for computing the size of union of n finite sets.
Updated: Last month
Matrix Exponentiation
Rare
Repeatedly multiplying a square matrix by itself.
(Optional) Bitsets
Rare
Examples of how bitsets give some unintended solutions on recent USACO problems.
Divide & Conquer - DP
Rare
Using Divide & Conquer as a DP Optimization.
Sum over Subsets DP
Not Frequent
Solving subset sum problems efficiently with DP.