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
Updated: Last month
Range Queries with Sweep Line
Not Frequent
Solving 2D grid problems using 1D range queries.
Updated: Last month
Range Update Range Query
Rare
Lazy updates on segment trees and two binary indexed trees in conjunction.
Updated: 5 days ago
Sparse Segment Trees
Rare
Querying big ranges.
Updated: Last month
2D Range Queries
Rare
Extending Range Queries to 2D (and beyond).
Updated: 2 weeks ago
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.
Updated: Last month
Trees
Binary Jumping
Somewhat Frequent
Efficiently finding ancestors of a node.
Updated: Last month
Small-To-Large Merging
Rare
A way to merge two sets efficiently.
Updated: Last month
Heavy-Light Decomposition
Rare
Path and subtree updates and queries.
Centroid Decomposition
Rare
Decomposing a tree to facilitate path computations.
Geometry
Geometry Primitives
Rare
Basic setup for geometry problems.
Updated: Last month
Sweep Line
Rare
Introduction to line sweep.
Updated: Last month
Convex Hull
Not Frequent
Smallest convex polygon containing a set of points on a grid.
Updated: Last month
Convex Hull Trick
Not Frequent
A way to find the maximum or minimum value of several convex functions at given points.
Updated: Last month
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.
Updated: Last month