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
It seems that no Platinum contest is complete without a segment tree ...
More Applications of Segment Tree
Somewhat Frequent
Walking on a Segment Tree, Non-Commutative Combiner Functions
Updated: 3 weeks ago
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: 4 days ago
Sparse Segment Trees
Rare
Querying big ranges.
Updated: Last month
2D Range Queries
Rare
Extending Range Queries to 2D (and beyond).
Updated: 4 days ago
Divide & Conquer - SRQ
Rare
Using Divide & Conquer to answer offline or online range queries on a static array.
Updated: Last month
Square Root Decomposition
Rare
Splitting up data into smaller chunks to speed up processing.
Updated: 4 days ago
Trees
... or a tree!
Binary Jumping
Somewhat Frequent
Introduces the problems of finding level ancestors in a tree and computing the lowest common ancestors.
Updated: 4 days ago
Small-To-Large Merging
Rare
A way to merge two sets efficiently.
Updated: 4 days ago
Heavy-Light Decomposition
Rare
Path and subtree updates and queries.
Updated: Last month
Centroid Decomposition
Rare
Decomposing a tree to facilitate path computations.
Updated: 4 days ago
Geometry
More advanced concepts in computational geometry.
Geometry Primitives
Rare
Basic setup for geometry problems.
Updated: 4 days ago
Sweep Line
Rare
Introduction to line sweep.
Updated: 4 days ago
Convex Hull
Not Frequent
Smallest convex polygon containing a set of points on a grid.
Updated: 4 days ago
Convex Hull Trick
Not Frequent
A way to find the maximum or minimum value of several convex functions at given points.
Updated: 4 days ago
Misc. Topics
Matrix Exponentiation
Rare
Repeatedly multiplying a square matrix by itself.
Updated: 4 days ago
(Optional) Bitsets
Rare
Examples of how bitsets give some unintended solutions on recent USACO problems.
Updated: 4 days ago
Divide & Conquer - DP
Rare
Using Divide & Conquer as a DP Optimization.
Updated: 4 days ago